La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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 Approximabilité du problème d'ensemble indépendant de la distance sur les graphiques réguliers et les graphiques planaires

Hiroshi ETO, Takehiro ITO, Zhilong LIU, Eiji MIYANO

  • Vues en texte intégral

    0

  • Citer

Résumé:

Cet article étudie les variantes généralisées du ENSEMBLE INDÉPENDANT MAXIMUM problème, appelé le DISTANCE MAXIMALE-d ENSEMBLE INDÉPENDANT problème (MaxDdEST pour faire court). Pour un entier d≥2, une distance-d ensemble indépendant d'un graphique non pondéré G=(V, E) est un sous-ensemble SV de sommets tels que pour toute paire de sommets u, vS, le nombre d'arêtes dans n'importe quel chemin entre u et à la v Est au moins d in G. Étant donné un graphique non pondéré G, l'objectif de MaxDdIS consiste à trouver une distance de cardinalité maximale.d ensemble indépendant de G. Dans cet article, nous analysons l’(in)approximabilité du problème sur r-graphiques réguliers (r≥3) et les graphes planaires, comme suit : (1) Pour tout nombre entier fixe d≥3 et r≥3, MaxDdEst sur r-les graphiques réguliers sont APX-difficiles. (2) Nous concevons en temps polynomial O(rd-1)-approximation et O(rd-2/d)-algorithmes d'approximation pour MaxDdEst sur r-graphiques réguliers. (3) Nous affinons ce qui précède O(rd-2/d)-algorithmes d’approximation lorsqu’ils sont limités à d=r=3, et donne un algorithme de 2 approximations en temps polynomial pour MaxD3IS sur des graphes cubiques. (4) Enfin, nous montrons que MaxDdIS admet un schéma d'approximation en temps polynomial (PTAS) pour les graphes planaires.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.9 pp.1211-1222
Date de publication
2022/09/01
Publicisé
2022/03/09
ISSN en ligne
1745-1337
DOI
10.1587/transfun.2021DMP0017
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories
Algorithmes et structures de données, graphiques et réseaux

Auteurs

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

Mots-clés

Table des matières