On the approximability of some maximum spanning tree problems
β Scribed by Giulia Galbiati; Angelo Morzenti; Francesco Maffioli
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 844 KB
- Volume
- 181
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
β¦ Synopsis
We study the approximability of some problems which aim at finding spanning trees in undirected graphs which maximize, rather than minimize, a single objective function representing a form of benefit or usefulness of the tree. We prove that the problem of finding a spanning tree which maximizes the number of paths which connect pairs of vertices and pass through a common arc can be polynomially approximated within 9/8. It is known that this problem can be solved exactly in polynomial time if the graph is 2-connected; we extend this result to graphs having at most two articulation points. We leave open whether in the general case the problem admits a polynomial time approximation scheme or is MAX-SNP hard and therefore not polynomially approximable within 1 + E, for any fixed E > 0, unless P = NP. On the other hand, we show that the problems of finding a spanning tree which has maximum diameter, or maximum height with respect to a specified root, or maximum sum of the distances between all pairs of vertices, or maximum sum of the distances from a specified root to all remaining vertices, are not polynomially approximable within any constant factor, unless P = NP. The same result holds for the problem of finding a lineal spanning tree with maximum height, and this solves a problem which was left open in .
π SIMILAR VOLUMES
This paper deals with the problem of constructing directed trees of optimal weight and root r with depth at most f (|V |) (called f -depthDSTP r ). We first prove that the maximization and the minimization versions are equal-approximable under the differential ratio, that measures how the value of a
Let 3:; denote the set of simple graphs with n vertices and m edges, t ( G ) the number of spanning trees of a graph G , and F 2 H if t(K,\E(F))?t(K,\E(H)) for every s? max{u(F), u ( H ) } . We give a complete characterization of >-maximal (maximum) graphs in 3:; subject to m 5 n . This result conta