Constrained spanning, Steiner trees and the triangle inequality

Prabhu Manyem ()
Additional contact information
Prabhu Manyem: University of South Australia

Chapter Chapter 19 in Optimization, 2009, pp 355-367 from Springer

Abstract: Abstract We consider the approximation characteristics of constrained spanning and Steiner tree problems in weighted undirected graphs where the edge costs and delays obey the triangle inequality. The constraint here is in the number of hops a message takes to reach other nodes in the network from a given source. A hop, for instance, can be a message transfer from one end of a link to the other. A weighted hop refers to the amount of delay experienced by a message packet in traversing the link. The main result of this chapter shows that no approximation algorithm for a delay-constrained spanning tree satisfying the triangle inequality can guarantee a worst case approximation ratio better than Θ(log n) unless NP ⊂ DTIME(n log logn ). This result extends to the corresponding problem for Steiner trees which satisfy the triangle inequality as well.

Keywords: Minimum spanning tree; maximum spanning tree; triangle inequality; Steiner tree; APX; approximation algorithm; asymptotic worst case ratio (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-0-387-98096-6_19

Ordering information: This item can be ordered from
http://www.springer.com/9780387980966

DOI: 10.1007/978-0-387-98096-6_19

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().