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

DOI10.1016/J.TCS.2012.03.014zbMATH Open1280.68098OpenAlexW2053474594MaRDI QIDQ441867FDOQ441867

Authors: Hervé L. M. Kerivin, Mathieu Lacroix, A. R. Mahjoub 

Publication date: 8 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.014

Recommendations

• On the complexity of the Eulerian closed walk with precedence path constraints problem
• On the computational complexity of length- and neighborhood-constrained path problems
• scientific article; zbMATH DE number 3950169
• On the computational complexity of path cover problems
• The Complexity of Restricted Variants of the Stable Paths Problem
• On the complexity of dynamic programming for sequencing problems with precedence constraints
• scientific article; zbMATH DE number 6269059
• On the greedy walk problem
• Improved approximations for TSP with simple precedence constraints (extended abstract)
• Certain exact and approximate algorithms for solving precedence problems with constraints

zbMATH Keywords

NP-completenesspolynomial-time algorithmEulerian closed walkprecedence path constraints

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The General Pickup and Delivery Problem
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Combinatorial algorithms for DNA sequence assembly
• On the complexity of the Eulerian closed walk with precedence path constraints problem
• An Eulerian path approach to DNA fragment assembly
• Minimal Eulerian Circuit in a Labeled Digraph

Cited In (2)

• On the complexity of the Eulerian closed walk with precedence path constraints problem
• NP-completeness of the Eulerian walk problem for a multiple graph

This page was built for publication: On the complexity of the Eulerian closed walk with precedence path constraints problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q441867)