Algoritmos de aproximação para partições conexas em grafos (2004)
- Authors:
- Autor USP: SALGADO, LILIANE ROSE BENNING - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: COMBINATÓRIA
- Language: Português
- Abstract: 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 usandocontraçõ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.
- Imprenta:
- Data da defesa: 12.03.2004
-
ABNT
SALGADO, Liliane Rose Benning. Algoritmos de aproximação para partições conexas em grafos. 2004. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2004. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-135334/. Acesso em: 09 out. 2024. -
APA
Salgado, L. R. B. (2004). Algoritmos de aproximação para partições conexas em grafos (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-135334/ -
NLM
Salgado LRB. Algoritmos de aproximação para partições conexas em grafos [Internet]. 2004 ;[citado 2024 out. 09 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-135334/ -
Vancouver
Salgado LRB. Algoritmos de aproximação para partições conexas em grafos [Internet]. 2004 ;[citado 2024 out. 09 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-135334/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
