The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
type: Item
instance of: scholarly article
title: The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
zbMATH Open document ID: 0823.68044
DOI: 10.1016/0166-218X(93)E0172-U
author: Lars Døvling Andersen
author: Herbert Fleischner
published in: Discrete Applied Mathematics
publication date: 1995-07-03T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 769292
zbMATH Keywords: NP-complete
zbMATH Keywords: Eulerian graph
zbMATH Keywords: Eulerian trail
MaRDI profile type: Publication
cites work: Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs
cites work: On non-intersecting Eulerian circuits
cites work: Q5335885
cites work: Matching, Euler tours and the Chinese postman
cites work: Degrees of acyclicity for hypergraphs and relational database schemes
cites work: The importance of being Euler
cites work: Eulerian graphs and related topics. Part 1, Volume 1
cites work: Q4198056
cites work: The Planar Hamiltonian Circuit Problem is NP-Complete
cites work: Efficient Planarity Testing
cites work: Embedding Graphs in the Plane—Algorithmic Aspects
description: scientific article; zbMATH DE number 769292