Steiner Trees in Industry

Xiuzhen Cheng (), Yingshu Li (), Ding-Zhu Du () and Hung Q. Ngo ()
Additional contact information
Xiuzhen Cheng: George Washington University, Department of Computer Science
Yingshu Li: University of Minnesota, Department of Computer Science and Engineering
Ding-Zhu Du: University of Minnesota, Department of Computer Science and Engineering
Hung Q. Ngo: State University of New York, Department of Computer Science and Engineering

A chapter in Handbook of Combinatorial Optimization, 2004, pp 193-216 from Springer

Abstract: 4 Conclusion The following problems are worth studying: Open problems on the Steiner ratio, such as Chung-Gilbert’s conjecture, Graham-Hwang’s conjecture, and Cielick’s conjecture, etc.. Find better approximation for network Steiner trees and establish an explicit lower bound for the approximation performance ratio of network Steiner trees. Close the gap between the lower bound and the upper bound for the approximation performance ratio of Steiner minimum arborescence. Find more efficient approximation algorithms for on-line and dynamic Steiner minimum trees and various Steiner tree packing problems. Find good approximation algorithms for multi-weighted Steiner trees and multiphase Steiner trees and study close relationship between multi-weighted Steiner trees, multiphase Steiner trees, and phylogenetic trees. Make clear whether there exists a polynomial-time approximation scheme for class Steiner tree in the special case with the real world background and highway interconnection problem. Close the gap between the lower bound and the upper bound for the approximation performance ratio of bottleneck Steiner tree in the Euclidean plane and make clear whether there exists a polynomial-time approximation scheme for the Steiner tree with minimum number of Steiner points and bounded edge-length. Implement efficient approximation algorithms to meet the requests from industries. We believe that to attack these new and old open problems new techniques are still required and the Steiner tree is still an attractive topic for researchers in combinatorial optimization and computer science.

Keywords: Minimum Span Tree; Steiner Tree; Steiner Point; Steiner Tree Problem; Minkowski Plane (search for similar items in EconPapers)
Date: 2004
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:sprchp:978-0-387-23830-2_4

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

DOI: 10.1007/0-387-23830-1_4

Access Statistics for this chapter

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