Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Optimal Hypergraph Tree-Realization
verfasst von : Ephraim Korach, Margarita Razgon
Erschienen in: Graph-Theoretic Concepts in Computer Science
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
Consider a hyperstar
H
and a function
ω
assigning a non-negative weight to every unordered pair of vertices of
H
and satisfying the following restriction: for any three vertices
u
,
v
,
x
such that
u
and
v
belong to the same set of hyperedges,
ω
({
u
,
x
}) =
ω
({
v
,
x
}). We provide an efficient method that finds a tree-realization
T
of
H
which has the maximum weight subject to the minimum number of leaves.
We transform the problem to the construction of an optimal degree-constrained spanning arborescence of a non-negatively weighted directed acyclic graph (DAG). The latter problem is a special case of the weighted matroid intersection problem. We propose a faster method based on finding the maximum weighted bipartite matching.