Influence of the tie-break rule on the end-vertex problem

Pierre Charbit 1 Michel Habib 1 Antoine Mamcarz 1
1 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : End-vertices of a given graph search may have some nice properties, as for example it is well known that the last vertex of Lexicographic Breadth First Search (LBFS) in a chordal graph is simplicial, see Rose, Tarjan and Lueker 1976. Therefore it is interesting to consider if these vertices can be recognized in polynomial time or not, as first studied in Corneil, Köhler and Lanlignel 2010. A graph search is a mechanism for systematically visiting the vertices of a graph. At each step of a graph search, the key point is the choice of the next vertex to be explored. Graph searches only differ by this selection mechanism during which a tie-break rule is used. In this paper we study how the choice of the tie-break in case of equality during the search, for a given graph search including the classic ones such as BFS and DFS, can determine the complexity of the end-vertex problem. In particular we prove a counterintuitive NP-completeness result for Breadth First Search solving a problem raised in Corneil, Köhler and Lanlignel 2010.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 2 (in progress), pp.57-72
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01101514
Contributeur : Pierre Charbit <>
Soumis le : mercredi 4 novembre 2015 - 14:49:23
Dernière modification le : jeudi 11 janvier 2018 - 06:21:34
Document(s) archivé(s) le : vendredi 5 février 2016 - 11:12:28

Fichier

dmtcs-16-2-5.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01101514, version 1

Collections

Citation

Pierre Charbit, Michel Habib, Antoine Mamcarz. Influence of the tie-break rule on the end-vertex problem. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 2 (in progress), pp.57-72. 〈hal-01101514〉

Partager

Métriques

Consultations de la notice

359

Téléchargements de fichiers

105