[pt] São apresentadas várias das formulações encontradas na literatura para o problema de Despacho de Veículos. Dentro destas formulações são estudadas aquelas que utilizam o Princípio de Decomposição de Programas Lineares como ferramenta de resolução, com a finalidade de melhorar sua eficiência computacional. Mostra-se que os sub-problemas encontrados naquelas formulações consistem na localização de ciclos negativos em um grafo. Compara-se a eficiência computacional de métodos de determinação de ciclos negativos em um grafo usados na solução dos sub-problemas dos Programas Lineares decompostos estudados na solução dos sub-problemas de um Programa Linear decomposto que foi formulado para resolver um problema de Despacho de Veículos. / [en] Some of the formulations of the problem of Vehicle Dispatching found in the literature are presented. Among those formulations, those whitchuse the Principle of Decomposition of Linear Programs as the method of solution are studied in order to improve their computational efficiency. It is shown that the sub-problems found in those models reduce to the identifications of negative cycles in a graph. The computational methods to identify negative cycles in a graph are compared, in terms of efficiency, for the solution of the sub-problems of a decomposed Linear Program found in the model developed to solve a Vehicle Dispatching problem.

Both chordal and weakly chordal graphs have been topics of research in graph theory for many years. Upon reading their definitions it is clear that the weakly chordal class of graphs is a relaxation of the chordal condition for graphs. The question is then asked could we possibly find and study the properties if we, in turn, relaxed the weakly chordal condition for graphs? We start by providing the definitions and basic results needed later on. In the second chapter, we discuss perfect graphs, some of their properties, and some subclasses that were researched. The third chapter is focused on a new class of graphs, the definition of which relaxes the restrictions for chordal and weakly chordal graphs, and extends certain results from weakly chordal graphs to this class.

No description available.

No description available.

No description available.

No description available.

A new connection between combinatorics and noncommutative algebra is established by relating a certain class of directed graphs to noncommutative Koszul algebras. The directed graphs in this class are called full graphs and are defined by a set of criteria on the edges. The structural properties of full graphs are studied as they relate to the edge criteria. A method is introduced for generating a Koszul algebra Lambda from a full graph G. The properties of Lambda are examined as they relate to the structure of G, with special attention being given to the construction of a projective resolution of certain semisimple Lambda-modules based on the structural properties of G. The characteristics of the Koszul algebra Lambda that is derived from the product of two full graphs G' and G' are studied as they relate to the properties of the Koszul algebras Lambda' and Lambda' derived from G' and G'. / Ph. D.

As wireless communication systems continue to push the limits of energy and spectral efficiency, increased demands are placed on the capabilities of the receiver. At the same time, the computational resources available for processing received signals will continue to grow. This opens the door for iterative algorithms to play an increasing role in the next generation of communication receivers. In the context of receivers, the goal of iterative probabilistic processing is to approximate maximum a posteriori (MAP) symbol-by-symbol detection of the information bits and estimation of the unknown channel or signal parameters. The sum-product algorithm is capable of efficiently approximating the marginal posterior probabilities desired for MAP detection and provides a unifying framework for the development of iterative receiver algorithms. However, in some applications the sum-product algorithm is computationally infeasible. Specifically, this is the case when both continuous and discrete parameters are present within the model. Also, the complexity of the sum-product algorithm is exponential in the number of variables connected to a particular factor node and can be prohibitive in multi-user and multi-antenna applications. In this dissertation we identify three key problems which can benefit from iterative probabilistic processing, but for which the sum-product algorithm is too complex. They are (1) joint synchronization and detection in multipath channels with emphasis on frame timing, (2) detection in co-channel interference and non-Gaussian noise, and (3) joint channel estimation and multi-signal detection. This dissertation presents the advances we have made in iterative probabilistic processing in order to tackle these problems. The motivation behind the work is to (a) compromise as little as possible on the performance that is achieved while limiting the computational complexity and (b) maintain good theoretical justification to the algorithms that are developed. / Ph. D.

Automated analysis of networks of interactions between proteins has become pervasive in molecular biology. Each node in such a network represents a protein and each edge an interaction between two proteins. Nearly every publication that uses network analysis includes a visualization of a graph in which the nodes and edges are laid out in two dimensions. Several systems implement multiple types of graph layout algorithms and make them easily accessible to scientists. Despite the existence of these systems, interdisciplinary research teams in computational biology face several challenges in sharing computed networks and interpreting them. This thesis presents two systemsGraphSpace and GraphCrowdthat together enhance network-based collaboration. GraphSpace users can automatically and rapidly share richly- annotated networks, irrespective of the algorithms or software used to generate them. A user may search for networks that contain a specific node or edge, or a collection of nodes and edges. Users can manually modify a layout, save it, and share it with other users. Users can create private groups, invite other users to join groups, and share networks with group members. Upon publication, researchers may make networks public and provide a URL in the paper. GraphCrowd addresses the challenging posed by automated layout algorithms, which incorporate almost no knowledge of the biological information underlying the networks. These algorithms compel researchers to use their knowledge and intuition to modify the node and edge positions manually to bring out salient features. GraphCrowd focuses on signaling networks, which connect proteins that represent a cells response to external signals. Treating network layout as a design problem, GraphCrowd explores the feasibility of leveraging human computation via crowdsourcing to create simplified and meaningful visualizations. GraphCrowd provides a streamlined interface that enables crowd workers to easily manipulate networks to create layouts that follow a specific set of guidelines. GraphCrowd also implements an interface to allow a user (e.g., an expert or a crowd worker) to evaluate how well a layout conforms to the guidelines. We use GraphCrowd to address two research questions: (i) Can we harness the power of crowdsourcing to create simplified, biologically meaningful visualizations of signaling networks?(ii) Can crowd workers rate layouts similarly to how an expert with domain knowledge would rate them? We design two systematic experiments that enable us to answer both questions in the affirmative. This thesis establishes crowdsourcing as a powerful methodology for laying out complex signaling networks. Moreover, by developing appropriate domain-specific guidelines for crowd workers, GraphCrowd can be generalized to a variety of applications. / Master of Science

Graphs are a commonly used abstraction for diverse kinds of interactions, e.g., on Twitter and Facebook. Different kinds of topological properties of such graphs are computed for gaining insights into their structure. Computing properties of large real networks is computationally very challenging. Further, most real world networks are dynamic, i.e., they change over time. Therefore there is a need for efficient dynamic algorithms that offer good space-time trade-offs. In this thesis we study the problem of computing the reachability set size of a vertex, which is a fundamental problem, with applications in databases and social networks. We develop the first Giraph based algorithms for different dynamic versions of these problems, which scale to graphs with millions of edges. / Master of Science