2011 | OriginalPaper | Buchkapitel
Path-Based Supports for Hypergraphs
verfasst von : Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, Arnaud Sallaberry
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\mathcal N\mathcal P$
-complete to compute 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.