Journal article
Near-optimal bounded-degree spanning trees
Algorithmica, v 29(1-2)
01 Jan 2001
Abstract
Random costs C(i, j) are assigned to the area of a complete directed graph on n labeled vertices. Given the cost matrix C-n = (C(i, j)), let T-k* = T-k*(C-n) be the spanning tree that has minimum cost among spanning trees with in-degree less than or equal to k. Since it is NP-hard to find T-k(*) We instead consider an efficient algorithm that finds a near-optimal spanning tree T-k(a). If the edge costs are independent, with a common exponential(1) distribution, then, as n --> infinity,
E(Cost(T-k(a))) = E(Cost(T-k(*))) + o(1).
Upper and lower bounds for E(Cost(Tk*)) are also obtained for k greater than or equal to 2.
Metrics
Details
- Title
- Near-optimal bounded-degree spanning trees
- Creators
- J C Hansen - Heriot-Watt UniversityE Schmutz - Drexel University
- Publication Details
- Algorithmica, v 29(1-2)
- Publisher
- Springer Nature
- Number of pages
- 33
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000165410500008
- Scopus ID
- 2-s2.0-0013333371
- Other Identifier
- 991019168577204721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Software Engineering
- Mathematics, Applied