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

DOI10.1016/j.tcs.2012.03.014zbMath1280.68098OpenAlexW2053474594MaRDI QIDQ441867

Hervé L. M. Kerivin, Mathieu Lacroix, Ali Ridha 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

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

Cites Work

• Unnamed Item
• Unnamed Item
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial algorithms for DNA sequence assembly
• Minimal Eulerian Circuit in a Labeled Digraph
• An Eulerian path approach to DNA fragment assembly
• The General Pickup and Delivery Problem

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