• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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

Thumbnail
View/Open
onTheComplexityOfTheECWPPCP_ISCO.pdf (122.0Kb)
Date
2012
Dewey
Recherche opérationnelle
Sujet
Eulerian closed walk; Precedence path constraints; NP-completeness; Polynomial-time algorithm
Journal issue
Theoretical Computer Science
Volume
439
Publication date
06-2012
Article pages
16-29
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.tcs.2012.03.014
URI
https://basepub.dauphine.fr/handle/123456789/11610
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
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é
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 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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.