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

DOI10.1016/0166-218X(93)E0172-UMaRDI QIDQ1893154zbMATH OpenFDO

Authors Lars Døvling Andersen, Herbert Fleischner

Publication date 3 July 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(93)E0172-U

zbMATH Keywords

Eulerian graphEulerian trailNP-complete

Mathematics Subject Classification ID

Trees (05C05) Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

This paper proves that it is NP-complete to decide whether a simple, 3- connected, plane Eulerian graph for which all face boundaries are 3- cycles or 4-cycles as an A-trail, that is, an Eulerian trail in which successive edges are always neighbours in the cyclic, clockwise ordering defined at each vertex of the graph by the given plane representation and a linear hypergraph which is regular of degree 3 has a spanning tree.

Recommendations

• Algorithms and outerplanar conditions for A-trails in plane Eulerian graphs
• On finding spanning eulerian subgraphs
• On non-intersecting Eulerian circuits
• NP-completeness and degree restricted spanning trees
• Eulerian disjoint paths problem in grid graphs is NP-complete

Cites work

• Algorithms and outerplanar conditions for A-trails in plane Eulerian graphs
• Degrees of acyclicity for hypergraphs and relational database schemes
• Efficient Planarity Testing
• Embedding Graphs in the Plane—Algorithmic Aspects
• Eulerian graphs and related topics. Part 1, Volume 1
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3208815 (Why is no real title available?)
• Matching, Euler tours and the Chinese postman
• On non-intersecting Eulerian circuits
• The importance of being Euler
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(14)

• Dominating sets whose closed stars form spanning trees
• Algorithms and outerplanar conditions for A-trails in plane Eulerian graphs
• DNA origami and the complexity of Eulerian circuits with turning costs
• On finding spanning eulerian subgraphs
• Minimally connected \(r\)-uniform hypergraphs
• \(A\)-trails of embedded graphs and twisted duals
• On Finding Hamiltonian Cycles in Barnette Graphs
• Design methods for 3D wireframe DNA nanostructures
• Generating functions and counting formulas for spanning trees and forests in hypergraphs
• NP-completeness of the Eulerian walk problem for a multiple graph
• Removing popular faces in curve arrangements
• Exact approaches for the connected vertex cover problem
• Spanning trees of 3-uniform hypergraphs
• Series parallel extensions of plane graphs to dual-Eulerian graphs

This page was built for publication: The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs

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