The Steiner Tree Problem

By H. Prömel, Angelika Steger. 2002

851 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/7e648daf500efdbcc6617d4a8858d10f77b6a739

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

An improved LP-based approximation for steiner tree (2010, background): “This problem emerges in a number of contexts, such as the design of VLSI, optical and wireless communication systems, as well as transportation and distribution networks (see, e.g., [27]).”
Improved Steiner tree approximation in graphs (2000, background): “Steiner trees are important in various applications such as VLSI routing [14], wirelength estimation [6], phylogenetic tree reconstruction in biology [11], and network routing [12].”
The Algorithm Design Manual (2020, background): “STEINER TREE 617 Notes: Monographs on the Steiner tree problem include Hwang, Richards, and Winter [HRW92] and Prömel and Steger [PS02].”
Minimum-energy multicast in mobile ad hoc networks using network coding (2004, background): “The minimum (cost) Steiner tree problem has been studied extensively in the literature; a survey can be found in the book [ 20 ].”
Center-piece subgraphs: problem definition and fast solutions (2006, background): “The “connection” requirement is also related to Steiner tree [5, 25], where the goal is to find a tree of minimal weight which includes all query nodes.”
Tighter Bounds for Graph Steiner Tree Approximation (2005, background): “Steiner trees are important in various applications such as VLSI routing [14], wirelength estimation [7], phylogenetic tree reconstruction in biology [11], and network routing [12].”
Restoring habitat corridors in fragmented landscapes using optimization and percolation models (2005, background): “Hence, the critical threshold is a distinct transition point between a landscape that is largely connected and one that is largely disconnected.”
FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design (2008, positive): “The resulting algorithm runs in O ( n log n ) time, and produces better solution in slightly less runtime than the one in [8].”