Show simple item record

hal.structure.identifierClemson Univ
dc.contributor.authorKerivin, Hervé*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLacroix, Mathieu
HAL ID: 741352
ORCID: 0000-0001-8385-3890
*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMahjoub, Ali Ridha*
dc.date.accessioned2013-09-04T14:30:15Z
dc.date.available2013-09-04T14:30:15Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11610
dc.language.isoenen
dc.subjectEulerian closed walken
dc.subjectPrecedence path constraintsen
dc.subjectNP-completenessen
dc.subjectPolynomial-time algorithmen
dc.subject.ddc003en
dc.titleOn the complexity of the Eulerian closed walk with precedence path constraints problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe 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.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol439en
dc.relation.isversionofjnldate2012-06
dc.relation.isversionofjnlpages16-29en
dc.relation.isversionofdoi10.1016/j.tcs.2012.03.014en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01497107*
hal.version1*
hal.update.actionupdateMetadata*
hal.update.actionupdateFiles*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record