NP-completeness of the Eulerian walk problem for a multiple graph
DOI10.18255/1818-1015-2024-1-102-114MaRDI QIDQ6495489FDOQ6495489
Authors: A. V. Smirnov 
Publication date: 30 April 2024
Published in: Modelirovanie i Analiz Informatsionnykh Sistem (Search for Journal in Brave)
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
edge-disjoint pathsNP-completenessEulerian trailEulerian cycledivisible graphmultiple graphmultiple pathcovering trails
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?)
- On the complexity of the disjoint paths problem
- On the Computational Complexity of Combinatorial Problems
- Title not available (Why is that?)
- On tours that contain all edges of a hypergraph
- On non-intersecting Eulerian circuits
- The algorithms for the Eulerian cycle and Eulerian trail problems for a multiple graph
- Eulerian walks in temporal graphs
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)
