Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
verfasst von : Serge Gaspers, Saket Saurabh, Alexey A. Stepanov
Erschienen in: Theory and Applications of Models of Computation
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
We consider the well studied
Full Degree Spanning Tree
problem, a NP-complete variant of the
Spanning Tree
problem, in the realm of moderately exponential time exact algorithms. In this problem, given a graph
G
, the objective is to find a spanning tree
T
of
G
which maximizes the number of vertices that have the same degree in
T
as in
G
. This problem is motivated by its application in fluid networks and is basically a graph-theoretic abstraction of the problem of placing flow meters in fluid networks. We give an exact algorithm for
Full Degree Spanning Tree
running in time
${\mathcal{O}(1.9172^n)}$
. This adds
Full Degree Spanning Tree
to a very small list of “non-local problems”, like
Feedback Vertex Set
and
Connected Dominating Set
, for which non-trivial (non brute force enumeration) exact algorithms are known.