The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs

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)

zbMATH Keywords

Eulerian graphNP-completeEulerian trail

Mathematics Subject Classification ID

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