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

Complexity of the Maximum k-Path Vertex Cover Problem Complexité du maximum k-Problème de couverture du sommet du chemin

Eiji MIYANO, Toshiki SAITOH, Ryuhei UEHARA, Tsuyoshi YAGITA, Tom C. van der ZANDEN

  • Vues en texte intégral

    0

  • Citer

Résumé:

Cet article présente la version de maximisation du k-problème de couverture des sommets du chemin, appelé MMAXIMUM K-PATH VERTEX COVER problème (MaxPkVC en abrégé) : Un chemin composé de k sommets, c'est-à-dire un chemin de longueur k-1 s'appelle un k-chemin. Si un k-chemin Pk comprend un sommet v dans un ensemble de sommets S, alors nous disons que v or S couvre Pk. Étant donné un graphique G=(V, E) et un entier s, le but de MaxPkVC consiste à trouver un sous-ensemble de sommets SV d'au plus s sommets tels que le nombre de k-les chemins parcourus par S est maximisée. Le problème MaxPkVC est généralement NP-difficile. Dans cet article, nous considérons la traitabilité/intraitabilité de MaxPkVC sur les sous-classes de graphiques. Nous prouvons que MaxP3VC reste NP-difficile même pour les graphiques fractionnés. De plus, si le graphique d'entrée est limité aux graphiques avec une largeur d'arbre délimitée constante, alors MaxP3VC peut être résolu en temps polynomial.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.10 pp.1193-1201
Date de publication
2020/10/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.2019DMP0014
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories
théorie de la complexité

Auteurs

Eiji MIYANO
  Kyushu Institute of Technology
Toshiki SAITOH
  Kyushu Institute of Technology
Ryuhei UEHARA
  Japan Advanced Institute of Science and Technology
Tsuyoshi YAGITA
  Kyushu Institute of Technology
Tom C. van der ZANDEN
  the Maastricht University

Mots-clés

Table des matières