The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
From MaRDI portal
Publication:1893154
DOI10.1016/0166-218X(93)E0172-UzbMath0823.68044MaRDI QIDQ1893154
Herbert Fleischner, Lars Døvling Andersen
Publication date: 3 July 1995
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)
Related Items (10)
On Finding Hamiltonian Cycles in Barnette Graphs ⋮ Dominating sets whose closed stars form spanning trees ⋮ Series parallel extensions of plane graphs to dual-Eulerian graphs ⋮ Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs ⋮ Design methods for 3D wireframe DNA nanostructures ⋮ Generating functions and counting formulas for spanning trees and forests in hypergraphs ⋮ The complexity of counting Eulerian tours in 4-regular graphs ⋮ DNA origami and the complexity of Eulerian circuits with turning costs ⋮ Unnamed Item ⋮ Spanning trees of 3-uniform hypergraphs
Cites Work
- Unnamed Item
- Unnamed Item
- On non-intersecting Eulerian circuits
- Eulerian graphs and related topics. Part 1, Volume 1
- The importance of being Euler
- Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs
- Degrees of acyclicity for hypergraphs and relational database schemes
- Embedding Graphs in the Plane—Algorithmic Aspects
- Efficient Planarity Testing
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Matching, Euler tours and the Chinese postman
This page was built for publication: The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
