Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0938.90064
Krumke, Sven; Wirth, Hans-Christoph
On the minimum label spanning tree problem. (English)
[J] Inf. Process. Lett. 66, No.2, 81-85 (1998). ISSN 0020-0190

Summary: We study the minimum label spanning tree problem. In this problem we are given an undirected graph whose edges are labeled with colors. The goal is to find a spanning tree which uses as few different colors as possible. We present an approximation algorithm with logarithmic performance guarantee. On the other hand, our hardness results show that the problem cannot be approximated within a constant factor.

MSC 2000:: *90C35 Network programming
68W10 Parallel algorithms
68R10 Graph theory in connection with computer science

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]