Resumo: Seja F uma família de conjuntos. Podemos associar a F um grafo, G, da seguinte forma: cada conjunto de F corresponde a um vértice de G e existe uma aresta ligando dois vértices em G se, e somente se, os conjuntos correspondentes a esses vértices se intersectam. O grafo G é chamado Grafo Interseção da família F.

Considere duas retas paralelas e . Seja F uma família de segmentos de reta com extremos em e . O grafo interseção dos elementos de F é chamado Grafo Permutação. A classe dos Grafos Permutação foi generalizada por Corneil e Kamula, permitindo que a família F contenha triângulos com um lado em e um vértice em . O grafo interseção de uma família de triângulos entre duas retas paralelas, é chamado Grafo PI. Outra generalização, permite trapézios entre as duas retas paralelas. O grafo interseção dessa família de trapézios é denominado Grafo Trapezóide.

Uma conseqüência direta das definições é a relação de continência entre as classes: Permutação PI Trapezóide. São conhecidas caracterizações e algoritmos polinomiais para o reconhecimento tanto dos grafos Pemutação quanto dos grafos Trapezóide. Entretanto, esses problemas continuam abertos para os grafos PI.

Considerando os grafos PI, identificamos uma subclasse obtida restringindo os triângulos da família F a triângulos não obtusângulos. Essa subclasse recebeu o nome de PI-Especial. Outra subclasse dos grafos PI é a classe dos Grafos de Intervalos, definida com o classe dos grafos interseção de famílias de intervalos linearmente ordenados. Para essa classe, são conhecidas caracterizações e algoritmos de reconhecimento lineares. Provamos que PI-Especial e Intervalos são exatamente a mesma classe e que um grafo PI não é grafo de Intervalos se, e somente se, possui um como subgrafo induzido.

Um grafo para o qual existe uma orientação transitiva das arestas é chamado Grafo de Comparabilidade. Um grafo cujo complemento é grafo de Comparabilidade chama-se Grafo de Co-comparabilidade. Sabe-se que PI Co-comparabilidade. Os grafos de Comparabilidade foram caracterizados por Gallai através da família dos grafos proibidos para Comparabilidade, a Família de Gallai. Provamos que um grafo da Família de Gallai é grafo de Co-comparabilidade e não é PI se, e somente se, possui um , , como subgrafo induzido.

Abstract: We discuss the following conjecture:

If is a graph with vertices and maximum degree , then is 1-factorizable.

Abstract: Biologists gather many kinds of data for biodiversity studies; these data are managed by distinct types of information systems. GIS-based biodiversity systems support sophisticated spatial correlations on living beings and their habitats, and spatio-temporal ecosystem modeling. Image information systems allow content-based image retrieval, to help species identification based on similarity (e.g., shape and color characteristics). Different kinds of rule-based systems support species characterization. Unfortunately, these systems (and the underlying data) are independent of each other. This paper presents a solution that seamlessly combines these functionalities, supporting queries that merge textual descriptions, spatial correlations and content-based predicates. The solution is being implemented at Virginia Tech, for identification and data retrieval, supporting management of fish species. It takes advantage of innovations in Digital Library technology to combine networked collections of heterogeneous data under integrated management.

Abstract: This work exploits the resemblance between content-based image retrieval and image analysis with respect to the design of image descriptors and their effectiveness. In this context, two shape descriptors are proposed: contour saliences and segment saliences. Contour saliences revisits its original definition, where the location of concave points was a problem, and provides a robust approach to incorporate concave saliences. Segment saliences introduces salience values for contour segments, making it possible to use an optimal matching algorithm as distance function. The proposed descriptors are compared with convex contour saliences, curvature scale space, and beam angle statistics using a fish database with 11,000 images organized in 1,100 distinct classes. The results indicate segment saliences as the most effective descriptor for this particular application and confirm the improvement of the contour salience descriptor in comparison with convex contour saliences.

Resumo: Workflows interorganizacionais são processos de negócio executados por múltiplas organizações que atuam cooperativamente para atingir um objetivo comum de negócio. Embora eles sejam uma extensão de workflows tradicionais, os agora chamados workflows intraorganizacionais, existem vários pontos específicos - conceituais e tecnológicos - que precisam ser tratados para o estabelecimento de uma infra-estrutura propícia para que a cooperação entre os envolvidos seja bem sucedida. Este relatório técnico apresenta uma visão geral de workflows interorganizacionais e de seu gerenciamento, apresentando suas principais características e algumas das principais linhas pesquisa existentes.

Abstract: The vertex separator (VS) problem in a graph asks for a partition of into nonempty subsets , , such that there is no edge between and , and is minimized subject to a bound on . We give a mixed integer programming formulation of the problem and investigate the vertex separator polytope (VSP), the convex hull of incidence vectors of vertex separators. Necessary and sufficient conditions are given for the VSP to be full dimensional. Central to our investigation is the relationship between separators and dominators. Several classes of valid inequalities are investigated, along with the conditions under which they are facet defining for the VSP. Some of our proofs combine in new ways projection with lifting.

In a companion paper we develop a branch-and-cut algorithm for the (VS) problem based on the inequalities discussed here, and report on computational experience with a wide variety of (VS) problems drawn from the literature and inspired by various applications.

Abstract: Given bins of size , non-negative values and , and a list of items, each item with size and class , we define a shelf as a subset of items packed inside a bin with total items size at most such that all items in this shelf have the same class. Two subsequent shelves must be separated by a shelf divisor of size . The size of a shelf is the total size of its items plus the size of the shelf divisor. The Class Constrained Shelf Bin Packing Problem consists to pack the items of into the minimum number of bins, such that, the items are divided into shelves and the total size of the shelves in a bin is at most . We present an asymptotic approximation scheme for this problem where the number of different classes is bounded by a constant . To our knowledge, this is the first approximation result where shelves of non-null size are used in packing problems.

Abstract: We present approximation algorithms for the following packing problems: the two-dimensional strip packing problem, the two-dimensional bin packing problem, the three-dimensional strip packing problem, and the three-dimensional bin packing problem. For all these problems, we consider orthogonal packings where ninety-degree rotations are allowed. The algorithms we show for these problems have asymptotic performance bounds 1.613, 2.64, 2.76 and 4.89, respectively. We also present an algorithm for the z-oriented three-dimensional strip packing problem with asymptotic performance bound 2.64. To our knowledge, these are the best bounds known for each problem.

Abstract: The concept of idealised fault-tolerant C2 component(iC2C) was introduced as a means for constructing dependable component-based software systems in the C2 architectural style out of existing software components. It is derived from the concept of idealised fault-tolerant component, which aims at providing a structuring for systems which minimizes the contribution of the fault-tolerance mechanisms to their overall complexity. The use of iC2Cs as architectural blocks from which a system is built simplifies the task of building component-based, dependable systems. In this work we present informal and formal specifications for the iC2C. The formal specification is based on a state-machine view of the iC2C which emphasizes the functioning of its internal protocol and makes it easy to specify and prove properties over it. Furthermore, we make some considerations relevant to the implementation of the iC2C.

Abstract: In this paper, we introduce a multiscale operator which, together with some morphological tools, can be used to reconnect broken components of an image. This operator extracts the orientation field from the image components and can be applied to both binary and gray-scale pictures. Although we illustrate its application in the fingerprint domain, the approach described here can be easily extended to images whose componentes exhibit well-defined directional information.

Abstract: Dias and Meidanis present, without a proof, an algorithm to sort the reverse permutation by prefix transpositions. In this report we present a new algorithm based on the previous one and show a complete formal proof of its correctness. From this result we establish a new proved upper bound of for the prefix transposition distance of .

Abstract: It is well known that, in general, the problem of determining the number of perfect matchings of a graph is NP-hard. Some graphs, called Pfaffian, have a special type of orientation that is also called Pfaffian. Given a Pfaffian orientation of a graph G, the number of perfect matchings of G may be evaluated in polynomial time. Two (not necessarily Pfaffian) orientations are similar if they differ by a cut. Similarity is an equivalence relation on the collection of orientations of a graph. If an orientation is Pfaffian then every similar orientation is also Pfaffian.

For any Pfaffian matching covered graph G, the number of similarity classes of Pfaffian orientations of G is equal to , where b denotes the number of bricks of the tight cut decomposition of G.

The following four problems are polynomially equivalent, that is, given a polynomial algorithm for any of the four problems it is then possible to find polynomial algorithms for the other three problems: (i) determine whether or not a graph is Pfaffian, (ii) determine whether or not a given orientation of a graph is Pfaffian, (iii) determine whether or not a graph is Pfaffian, in case it is Pfaffian, find a Pfaffian orientation for the graph, and (iv) determine the number of similarity classes of Pfaffian orientations of a graph.

Abstract: The development of modern component-based software systems usually needs to integrate autonomous component-systems which are developed independently from each other. Examples of such component-systems include COTS components, legacy software systems, and Web Services. For developing this new kind of software system, we need innovative software engineering approaches that rely on the system's software architecture to achieve the desired quality properties of the resulting system, such as fault tolerance. In this paper, we propose an architectural approach to the dependable composition of component-systems based on composition contracts and an exception handling scheme which considers the concurrent execution of architectural components.

Resumo: O número cromático total, , é o menor número de cores necessárias para colorir as arestas e os vértices de um grafo de maneira que não haja elementos adjacentes ou incidentes com a mesma cor. A conjetura da coloração total (TCC) estabelece que todo grafo simples possui . Neste trabalho verificamos a TCC para as potências de ciclo , par e , mostrando que existe, e pode ser construída em tempo polinomial, uma -coloração total para estes grafos.