✦ LIBER ✦

Efficient path and vertex exchange in steiner tree algorithms

✍ Scribed by Duin, Cees; Vo?, Stefan

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 349 KB
Volume: 29
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199703)29:2<89::aid-net3>3.0.co;2-7

No coin nor oath required. For personal study only.

✦ Synopsis

Steiner's problem in a weighted graph requires a tree of minimum total weight spanning a subset of special vertices. In this paper, we formulate efficient routines for greedy exchanges of paths as well as vertices. The heuristic proposed on the basis of these routines consists of three phases: an initialization providing shortest-path information, a module for the selection of Steiner vertices, and an improvement procedure. The latter procedure constitutes a general procedure executable after any heuristic. A spin-off from the second module is a decreased running time for a well-known 11/6 approximation algorithm. The first phase can be replaced by a shortest-path approximation method to obtain a running time order that is quadratic in the number of vertices.

📜 SIMILAR VOLUMES

Edge and vertex intersection of paths in

Edge and vertex intersection of paths in a tree

✍ Martin Charles Golumbic; Robert E. Jamison 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 572 KB

Efficient Parallel Algorithms for Optima

Efficient Parallel Algorithms for Optimally Locating a Path and a Tree of a Specified Length in a Weighted Tree Network

✍ Biing-Feng Wang 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 128 KB

In this paper, we propose efficient parallel algorithms on the EREW PRAM for optimally locating in a tree network a path-shaped facility and a tree-shaped facility of a specified length. Edges in the tree network have arbitrary positive lengths. Two optimization criteria are considered: minimum ecce

Experimental evaluation of a partitionin

Experimental evaluation of a partitioning algorithm for the steiner tree problem in R2 and R3

✍ Sivakumar Ravada; Alan T. Sherman 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 614 KB

## Abstract We experimentally evaluate sequential and distributed implementations of an approximation partitioning algorithm by Kalpakis and Sherman for the __Geometric Steiner Minimum Tree Problem (GSMT)__ in __R^d^__ for __d__ = 2,3. Our implementations incorporate an improved method for combinin

Efficient algorithms for finding depth-f

Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs

✍ C. Rhee; Y.Daniel Liang; S.K. Dhall; S. Lakshmivarahan 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 512 KB

Amer. inst. chem. eng. j.: Pho, T. K. an

Amer. inst. chem. eng. j.: Pho, T. K. and Lapidus, L. ‘Topics in c.a.d. Part. An optimum tearing algorithm for recycle systems’ Part 2. Synthesis of optimal heat exchanger networks by tree searching algorithms’ Vol 19, No 6 (November 1973) pp 1170–1189

📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 116 KB

The SAR70 program has been written as a tool within the SAR design method for supports. A support is a building in which a variety of floorplans for dwellings can hc made. The design method allows evaluation of such asupport. SAR7O can be used to generate all variations possible within a support str