
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érenceDate
2010Conference title
ISCO International Symposium on Combinatorial OptimizationConference date
2010-03Conference city
HammametConference country
TunisieJournal name
Electronic Notes in Discrete MathematicsVolume
36Publisher
Elsevier
Pages
899-906
8
Publication identifier
Metadata
Show full item recordAbstract (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-completenessRelated items
Showing items related by title and author.
-
Kerivin, Hervé; Lacroix, Mathieu; Mahjoub, Ali Ridha (2012) Article accepté pour publication ou publié
-
Kerivin, Hervé; Lacroix, Mathieu; Mahjoub, Ali Ridha; Quilliot, Alain (2006) Communication / Conférence
-
Kerivin, Hervé; Lacroix, Mathieu; Mahjoub, Ali Ridha; Quilliot, Alain (2008) Article accepté pour publication ou publié
-
Kerivin, Hervé; Lacroix, Mathieu; Mahjoub, Ali Ridha (2012) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; Kerivin, Hervé; Didi Biha, Mohamed (2008) Article accepté pour publication ou publié