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 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.
展开▼
