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

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

Aleksandr Valer'Evich Smirnov

Publication date: 30 April 2024

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

zbMATH Keywords

NP-completenessEulerian cycleedge-disjoint pathsEulerian traildivisible graphmultiple graphmultiple pathcovering trails

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• On tours that contain all edges of a hypergraph
• On non-intersecting Eulerian circuits
• On the complexity of the disjoint paths problem
• Eulerian walks in temporal graphs
• On the Computational Complexity of Combinatorial Problems
• 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