• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
Kerivin.PDF (117.8Kb)
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
http://dx.doi.org/10.1016/j.endm.2010.05.114
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

Related items

Showing items related by title and author.

  • Thumbnail
    On the complexity of the Eulerian closed walk with precedence path constraints problem 
    Kerivin, Hervé; Lacroix, Mathieu; Mahjoub, Ali Ridha (2012) Article accepté pour publication ou publié
  • Thumbnail
    The capacitated vehicle routing problem with reloads 
    Kerivin, Hervé; Lacroix, Mathieu; Mahjoub, Ali Ridha; Quilliot, Alain (2006) Communication / Conférence
  • Thumbnail
    The splittable pickup and delivery problem with reloads 
    Kerivin, Hervé; Lacroix, Mathieu; Mahjoub, Ali Ridha; Quilliot, Alain (2008) Article accepté pour publication ou publié
  • Thumbnail
    Models for the single-vehicle preemptive pickup and delivery problem 
    Kerivin, Hervé; Lacroix, Mathieu; Mahjoub, Ali Ridha (2012) Article accepté pour publication ou publié
  • Thumbnail
    On the Polytope of the (1,2)-Survivable Network Design Problem 
    Mahjoub, Ali Ridha; Kerivin, Hervé; Didi Biha, Mohamed (2008) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo