Path-based supports for hypergraphs
2012
A path-based support of a hypergraph H is a graph with the same vertex set as H in which each hyperedge induces a Hamiltonian subgraph. While it is NP-hard to decide whether a path-based support has a monotone drawing, to determine a path-based support with the minimum number of edges, or to decide whether there is a planar path-based support, we show that a path-based tree support can be computed in polynomial time if it exists.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
21
References
37
Citations
NaN
KQI