𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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


The maximum f-depth spanning tree proble
✍ JΓ©rΓ΄me Monnot πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 113 KB

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

On graphs with the maximum number of spa
✍ Alexander K. Kelmans πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 814 KB

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