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

DOI10.1016/J.TCS.2012.03.014MaRDI QIDQ441867zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)