Approximation Algorithms for Min–Max Tree Partition

We consider the problem of partitioning the node set of a graph intopequal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded error ratio can be given for the problem unless P=NP. We presen...

Full description

Saved in:
Bibliographic Details
Published in:Journal of algorithms 1997-08, Vol.24 (2), p.266-286
Main Authors: Guttmann-Beck, Nili, Hassin, Refael
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Information retrieval. Graph
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of partitioning the node set of a graph intopequal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded error ratio can be given for the problem unless P=NP. We present anO(n2) time algorithm for the problem, wherenis the number of nodes in the graph. Assuming that the edge lengths satisfy the triangle inequality, its error ratio is at most 2p−1. We also present an improved algorithm that obtains as an input a positive integerx. It runs inO(2(p+x)pn2) time, and its error ratio is at most (2−x/(x+p−1))p.
ISSN:0196-6774
1090-2678
DOI:10.1006/jagm.1996.0848