Cobertura por circuitos em grafos mistos (1999)
- Authors:
- Autor USP: LEE, ORLANDO - IME
- Unidade: IME
- Sigla do Departamento: MAP
- Assunto: TEORIA DOS GRAFOS
- Language: Português
- Abstract: 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 (decasosespeciais) 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
- Imprenta:
- Data da defesa: 17.12.1999
-
ABNT
LEE, Orlando. Cobertura por circuitos em grafos mistos. 1999. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 1999. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-024308/. Acesso em: 10 out. 2024. -
APA
Lee, O. (1999). Cobertura por circuitos em grafos mistos (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-024308/ -
NLM
Lee O. Cobertura por circuitos em grafos mistos [Internet]. 1999 ;[citado 2024 out. 10 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-024308/ -
Vancouver
Lee O. Cobertura por circuitos em grafos mistos [Internet]. 1999 ;[citado 2024 out. 10 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-024308/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
