• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Doctoral Thesis
DOI
https://doi.org/10.11606/T.45.1999.tde-20210729-024308
Document
Author
Full name
Orlando Lee
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 1999
Supervisor
Title in Portuguese
Cobertura por circuitos em grafos mistos
Keywords in Portuguese
Teoria Dos Grafos
Abstract in Portuguese
Neste trabalho estudamos vários tipos de problemas envolvendo circuitos em grafos mistos. Tais grafos generalizam a noção de grafos orientados e não-orientados, no sentido de poderem conter tanto arcos como arestas. O seguinte problema é tratadoextensivamente em nosso trabalho: dado um grafo misto M com pesos inteiros não-negativos p(e) associados a cada arco/aresta e de M, decidir se existe uma coleção de circuitos de M tal que cada arco/aresta e de M pertence a exatamente p(e)circuitos dessa coleção. Apresentamos uma boa caracterização para o problema assim como um algoritmo polinomial, baseado no método dos elipsóides, para o caso em que M é um grafo misto série-paralelo. Além disso, mostramos que esse problema éNP-difícil para grafos mistos planares. Consideramos também uma relaxação linear desse problema e descrevemos resultados de polinomialidade/complexidade similares. Resultados sobre dois problemas combinatórios bem conhecidos, o problema dedetectar/encontrar circuitos negativos e o problema de encontrar caminhos mínimos, também são apresentados. Seu estudo foi motivado pelas implicações algorítmicas para os problemas mencionados acima. Mostramos que esses problemas são NP-difíceispara grafos mistos planares. Estudamos também o problema de cobrir os arcos e as arestas de um grafo misto com circuitos de modo a minimizar a soma dos comprimentos dos circuitos. Discutimos vários resultados sobre a complexidade (de casosespeciais) do problema, algoritmos de aproximação e sua relação com o problema do carteiro chinês. Descrevemos algoritmos polinomiais para o problema em grafos mistos com largura arbórea limitada. Por fim, estudamos uma famosa conjectura deWoodall que relaciona circuitos e transversais em grafos orientados planares. Provamos que a conjectura é verdadeira para grafos orientados série-paralelos
Title in English
not available
Abstract in English
We study several problems on circuits in mixed graphs. These graphs generalise the notion of undirected graphs, in the sense that they may contain edges as well as arcs. The following problem is extensively studied in our work: given a mixedgraph M with non-negative integer weights p(e) associated with each arc/edge e of M, decide whether there exists a collection of circuits of M such that each arc/edge e of M is contained in exactly p(e) circuits from this collection. We give agood caracterization for the problem and describe a polynomial (ellipsoid based) algorithm for the case in which M is a series-parallel mixed graph. Furthermore, we show that the problem is NP-hard for planar mixed graphs. We also consider alinear relaxation of the problem and describe similar results on complexity and polinomiality. Results on two well-known combinatorial problems, the problem of detecting negative circuits and the problem of finding shortest paths, are alsopresented. This study was motivated by the algorithmic consequences for the problems above mentioned. We prove that these problems are NP-hard for planar mixed graphs. We also study the problem of covering the arcs and the edges of a mixed graphwith circuits so as to minimize the sum of the lenghts of the circuits. We discuss results on the complexity of (special cases of) this problem, approximation algorithms and its relationship with the Chinese Postman problem. We describepolynomial algorithms for the problem restricted to mixed graphs of bounded tree-width. Finally, we study a famous conjecture of Woodall which relates circuits and transversals in planar directed graphs. We show that this conjecture holds forseries-parallel directed graphs
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
LeeOrlando.pdf (15.83 Mbytes)
Publishing Date
2021-07-29
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2024. All rights reserved.