Exportar registro bibliográfico

Algoritmos de aproximação para partições conexas em grafos (2004)

  • Authors:
  • USP affiliated authors: SALGADO, LILIANE ROSE BENNING - IME
  • Unidades: IME
  • Sigla do Departamento: MAC
  • Subjects: 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

  • How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      SALGADO, Liliane Rose Benning; WAKABAYASHI, Yoshiko. Algoritmos de aproximação para partições conexas em grafos. 2004.Universidade de São Paulo, São Paulo, 2004.
    • APA

      Salgado, L. R. B., & Wakabayashi, Y. (2004). Algoritmos de aproximação para partições conexas em grafos. Universidade de São Paulo, São Paulo.
    • NLM

      Salgado LRB, Wakabayashi Y. Algoritmos de aproximação para partições conexas em grafos. 2004 ;
    • Vancouver

      Salgado LRB, Wakabayashi Y. Algoritmos de aproximação para partições conexas em grafos. 2004 ;

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

    Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2019