On the complexity of the Eulerian closed walk with precedence path constraints problem

Thumbnail
Ouvrir
Date
2012
Indexation documentaire
Recherche opérationnelle
Subject
Eulerian closed walk; Precedence path constraints; NP-completeness; Polynomial-time algorithm
Nom de la revue
Theoretical Computer Science
Volume
439
Date de publication
06-2012
Pages article
16-29
Nom de l'éditeur
Elsevier
DOI
http://dx.doi.org/10.1016/j.tcs.2012.03.014
URI
https://basepub.dauphine.fr/handle/123456789/11610
Collections
Métadonnées
Afficher la notice complète
Auteur
Kerivin, Hervé
162731 Clemson Univ
Lacroix, Mathieu
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mahjoub, Ali Ridha
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
Résumé en anglais
The Eulerian closed walk problem in a digraph is a well-known polynomial-time solvable problem. In this paper, we show that if we impose the feasible solutions to fulfill some precedence constraints specified by paths of the digraph, then the problem becomes NP-complete. We also present a polynomial-time algorithm to solve this variant of the Eulerian closed walk problem when the set of paths does not contain some forbidden structure. This allows us to give necessary and sufficient conditions for the existence of feasible solutions in this polynomial-time solvable case.