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

Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs Aproximabilidade do problema do conjunto independente de distância em gráficos regulares e gráficos planares

Hiroshi ETO, Takehiro ITO, Zhilong LIU, Eiji MIYANO

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Este artigo estuda variantes generalizadas do CONJUNTO INDEPENDENTE MÁXIMO problema, denominado DISTÂNCIA MÁXIMA-d CONJUNTO INDEPENDENTE problema (MaxDdÉ para abreviar). Para um número inteiro d≥2, uma distânciad conjunto independente de um gráfico não ponderado G=(V, E) é um subconjunto SV de vértices tal que para qualquer par de vértices u, vS, o número de arestas em qualquer caminho entre u e v é pelo menos d in G. Dado um gráfico não ponderado G, o objetivo do MaxDdIS é encontrar uma distância de cardinalidade máxima-d conjunto independente de G. Neste artigo, analisamos a (in)aproximabilidade do problema em r-gráficos regulares (r≥3) e gráficos planares, como segue: (1) Para cada número inteiro fixo d≥3 e r≥3, MáxDdEstá ativado r-gráficos regulares são difíceis de APX. (2) Projetamos tempo polinomial O(rd-1)-aproximação e O(rd-2/d)-algoritmos de aproximação para MaxDdEstá ativado r-gráficos regulares. (3) Nós aprimoramos o acima O(rd-2/d)-algoritmos de aproximação quando restritos a d=r=3, e fornece um algoritmo de aproximação 2 em tempo polinomial para MaxD3IS em gráficos cúbicos. (4) Finalmente, mostramos que MaxDdIS admite um esquema de aproximação em tempo polinomial (PTAS) para grafos planares.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.9 pp.1211-1222
Data de publicação
2022/09/01
Publicitada
2022/03/09
ISSN online
1745-1337
DOI
10.1587/transfun.2021DMP0017
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria
Algoritmos e Estruturas de Dados, Gráficos e Redes

autores

Hiroshi ETO
  Tohoku University
Takehiro ITO
  Tohoku University
Zhilong LIU
  Kyushu Insitute of Technology
Eiji MIYANO
  Kyushu Insitute of Technology

Palavra-chave