The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs (Q1893154)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 769292
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs |
scientific article; zbMATH DE number 769292 |
Statements
The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs (English)
0 references
3 July 1995
0 references
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.
0 references
NP-complete
0 references
Eulerian graph
0 references
Eulerian trail
0 references
0.8279317617416382
0 references
0.8093007206916809
0 references
0.7807633876800537
0 references
0.7722691893577576
0 references
0.7706080079078674
0 references
