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

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

0.00 Avg rating0 Votes
Article ID: iaor1997997
Country: Netherlands
Volume: 59
Issue: 3
Start Page Number: 203
End Page Number: 214
Publication Date: May 1995
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: computational analysis
Abstract:

Samuel W. Bent and Udi Manber have shown that it is NP-complete to decide whether a simple, 2-connected, plane Eulerian graph has an A-trial, that is, an Eulerian trial in which successive edges are always neighbours in the cyclic, clockwise ordering defined at each vertex of the graph by the given plane representation. The authors prove, by a different reduction, tha the problem remains NP-complete for simple, 3-connected, plane Eulerian graphs for which all face boundaries are 3-cycles or 4-cycles. They then apply this result to show that it is NP-complete to decide whether a linear hypergraph which is regular of degree 3 has a spanning tree.

Reviews

Required fields are marked *. Your email address will not be published.