Approximating the degree-bounded minimum diameter spanning tree problem

被引：17

作者：

Könemann, J

Levin, A

Sinha, A

机构：

[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[2] Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel

[3] Univ Michigan, Sch Business, Ann Arbor, MI 48103 USA

[4] Carnegie Mellon Univ, Tepper Sch Business, Pittsburgh, PA 15213 USA

来源：

ALGORITHMICA | 2005年 / 41卷 / 02期

关键词：

approximation algorithms; spanning trees; bicriteria approximation; degree-bounded spanning trees;

D O I：

10.1007/s00453-004-1121-2

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We consider the problem of finding a minimum diameter spanning tree with maximum node degree B in a complete undirected edge-weighted graph. We provide an O(rootlog(B) n)-approximation algorithm for the problem. Our algorithm is purely combinatorial. and relies on a combination of filtering and divide and conquer.

引用

页码：117 / 129

页数：13

共 20 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

Arkin EM, 2002, SIAM PROC S, P568

[3]

ARKIN EM, 2003, P 15 ANN ACM S PAR A, P295

[4]

Bartal Y., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P161, DOI 10.1145/276698.276725

[5] Probabilistic approximation of metric spaces and its algorithmic applications [J].

Bartal, Y .

37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, :184-193

[6]

BAUER F, 1995, IEEE INFOCOM SER, P369, DOI 10.1109/INFCOM.1995.515897

[7] TREE SPANNERS [J].

CAI, LZ ;

CORNEIL, DG .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1995, 8 (03) :359-387

[8]

Chu Y., 2001, P ACM SIGCOMM, P55

[9] MULTICAST ROUTING IN DATAGRAM INTERNETWORKS AND EXTENDED LANS [J].

DEERING, SE ;

CHERITON, DR .

ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1990, 8 (02) :85-110

[10] APPROXIMATING THE MINIMUM-DEGREE STEINER TREE TO WITHIN ONE OF OPTIMAL [J].

FURER, M ;

RAGHAVACHARI, B .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1994, 17 (03) :409-423

← 1 2 →