Thumbnail

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

Mahjoub, Ali Ridha; Lacroix, Mathieu; Kerivin, Hervé (2010), On the complexity of the Eulerian closed walk with precedence path constraints problem, ISCO International Symposium on Combinatorial Optimization, 2010-03, Hammamet, Tunisie

View/Open
Type
Communication / Conférence
Date
2010
Conference title
ISCO International Symposium on Combinatorial Optimization
Conference date
2010-03
Conference city
Hammamet
Conference country
Tunisie
Journal name
Electronic Notes in Discrete Mathematics
Volume
36
Publisher
Elsevier
Pages
899-906
8
Publication identifier
Metadata
Show full item record
Author(s)
Mahjoub, Ali Ridha
Lacroix, Mathieu cc
Kerivin, Hervé
Abstract (EN)
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 paths are arc-disjoint. We also give necessary and sufficient conditions for the existence of feasible solutions in this polynomial-time solvable case.
Subjects / Keywords
polynomial-time algorithm; Eulerian closed walk; precedence path constraints; NP-completeness