A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Note on Approximating the Survivable Network Design Problem in Hypergraphs Uma nota sobre como aproximar o problema de design de rede de sobrevivência em hipergrafos

Liang ZHAO, Hiroshi NAGAMOCHI, Toshihide IBARAKI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Consideramos projetar algoritmos de aproximação para o problema de design de rede sobrevivente em hipergrafos (SNDPHG) baseado em algoritmos desenvolvidos para o problema de design de rede sobrevivente em gráficos (SNDP) ou o problema de conectividade de elementos em gráficos (ECP). Dada uma instância do SNDPHG, substituindo cada hiperaresta e={v1,・・・,vk} com um novo vértice we e k arestas {we, v1},・・・, {we, vk}, definimos um SNDP ou ECP no gráfico resultante. Mostramos que resolvendo aproximadamente o SNDP ou ECP assim definido, vários algoritmos de aproximação para o SNDPHG podem ser obtidos. Um dos nossos resultados é um dmax+-algoritmo de aproximação para o SNDPHG com dmax 3, onde dmax (resp. dmax+) é o grau máximo de hiperarestas (resp. hiperarestas com custo positivo). Outro é um dmax+(rmax)-algoritmo de aproximação para o SNDPHG, onde (i)=j = 1i(1/j) é a função harmônica e rmax é o requisito máximo de conectividade.

Publicação
IEICE TRANSACTIONS on Information Vol.E85-D No.2 pp.322-326
Data de publicação
2002/02/01
Publicitada
ISSN online
DOI
Tipo de Manuscrito
Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Categoria

autores

Palavra-chave