NP-completeness of the Eulerian walk problem for a multiple graph

DOI10.18255/1818-1015-2024-1-102-114MaRDI QIDQ6495489zbMATH OpenFDO

Authors A. V. Smirnov

Publication date 30 April 2024

Published in Modelirovanie i Analiz Informatsionnykh Sistem (Search for Journal in Brave)

zbMATH Keywords

edge-disjoint pathsNP-completenessEulerian trailEulerian cycledivisible graphmultiple graphmultiple pathcovering trails

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Recommendations

• The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
• Eulerian disjoint paths problem in grid graphs is NP-complete
• On the complexity of the Eulerian closed walk with precedence path constraints problem
• On the complexity of the Eulerian closed walk with precedence path constraints problem
• On non-intersecting Eulerian circuits

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• Eulerian walks in temporal graphs
• On non-intersecting Eulerian circuits
• On the Computational Complexity of Combinatorial Problems
• On the complexity of the disjoint paths problem
• On tours that contain all edges of a hypergraph
• The algorithms for the Eulerian cycle and Eulerian trail problems for a multiple graph

This page was built for publication: NP-completeness of the Eulerian walk problem for a multiple graph

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