Thèse de Doctorat
DOI
https://doi.org/10.11606/T.45.2004.tde-20210729-135334
Document
Auteur
Nom complet
Liliane Rose Benning Salgado
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2004
Directeur
Titre en portugais
Algoritmos de aproximação para partições conexas em grafos
Mots-clés en portugais
Combinatória
Resumé en portugais
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.
Titre en anglais
not available
Resumé en anglais
not available
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2021-07-29
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées
cliquant ici.