• 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.2004.tde-20210729-135334
Document
Author
Full name
Liliane Rose Benning Salgado
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2004
Supervisor
 
Title in Portuguese
Algoritmos de aproximação para partições conexas em grafos
Keywords in Portuguese
Combinatória
Abstract in Portuguese
O estudo das propriedades de aproximação de problemas de otimização NP-difíceis é um tópico de interesse tanto da área de otimização quanto da teoria de comploexidade computacional. O tema desta tese insere-se neste contexdto, dando ênfase ao estudo de problemas de partição de grafos em subgrafos conexos satisfazendo certas especificações. Concentramo-nos no desenvolvimento e análise de algoritmos de aproximação, e questões relativas ao grau de (in)aproximabilidade desses problemas. Um dos problemas investigados, chamado Max 2-Partição Conexa Balanceada ('PCB IND. 2'), é o seguinte: dado um grafo conexo G=(V, E) com uma função peso w : V -> 'Z IND. +' definida sobre seus vértices, encontrar uma 2-partição ('V IND. 1', 'V IND. 2') de V tal que G['V IND. 1'] e G['V IND. 2'] sejam conexos e o peso do mais `leve¦ deles seja o maior possível. Mais formalmente, queremos encontrar uma tal partição que maximiza a função min {w('V IND. 1'), w('V IND. 2')}, onde w(S) denota o peso de um conjunto S. Exibimos resultados sobre complexidade computacional e inaproximabilidade. Também apresentamos uma releitura de um algoritmo (4/3)-aproximado desenvolvido por Chlebíková [Ch196]. A análise parametrizada que fizemos permite descrever classes de grafos para as quais as soluções devolvidas se aproximam assintoticamente do ótimo. Mostramos que a razão de aproximação desse algoritmo é justa mesmo para grafos 3-conexos. Além disto, elaboramos um algoritmo para grafos 3-conexos usando contrações de arestas, que pode produzir soluções de qualidade melhor do que o algoritmo (4/3)-aproximado. Também apresentamos um esquema de aproximação polinomial para uma classe especial de grafos. Provamos ainda que as versões com e sem pesos do Max 2-Partição Conexa Balanceada possuem o mesmo limiar de aproximação. Estudamos também uma generalização natural do problema 'PCB IND 2', denominado Max q-Partição Conexa Balanceada Continua. Continuação: ('PCB IND. q'), para q > 2. Para o problema 'PCB IND. 3' restrito a grafos 3-conexos exibimos dois algoritmos, sendo um deles uma 2-aproximação. Para 'PCB IND. 4' restrito a grafos 4-conexos exibimos também uma 2-aproximação, porém apenas sob certas hipóteses sobre os pesos dos vértices. Investigamos um outro problema, chamado Max Árvore Balanceada, que mostramos ser AP-redutível ao 'PCB IND. 2'. Também apresentamos algoritmos de aproximação para um outro problema correlato, denominado Max (p/k)-Bipartição Fracionária Conexa. Exibimos um algoritmo para 1/2 menor ou igual a p/k < 1 cuja razão de aproximação é 3p/(3p-k). Discutimos brevemente outros problemas correlatos, mencionando alguns resultados encontrados na literatura.
 
Title in English
not available
Abstract in English
not available
 
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.
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
© 2001-2024. Digital Library of Theses and Dissertations of USP.