𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Rectilinear steiner trees: Efficient special-case algorithms

✍ Scribed by A. V. Aho; M. R. Garey; F. K. Hwang

Publisher
John Wiley and Sons
Year
1977
Tongue
English
Weight
886 KB
Volume
7
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A minimal rectilinear Steiner tree for a set A of points in the plane is a tree which interconnects A using horizontal and vertical lines of shortest possible total length. Such trees have potential application to wire layout for printed circuits. Unfortunately, at present no practical algorithm is known for constructing these trees in general. We present two algorithms, each requiring a number of operations proportional to only a low degree polynomial in the number of points to be interconnected, for the special cases in which all the points of A lie on a small number of parallel lines or on the boundary of a rectangle.

πŸ“œ SIMILAR VOLUMES

A polynomial time algorithm for rectilin
A polynomial time algorithm for rectilinear Steiner trees with terminals constrained to curves
✍ Brazil, M.; Thomas, D. A.; Weng, J. F. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 168 KB πŸ‘ 2 views

The rectilinear Steiner problem is the problem of constructing the shortest rectilinear network in the plane connecting a given set of points, called terminals. The problem is known to be NP-complete in general. In this paper, we show that there is a polynomial time algorithm for solving the rectili

Efficient path and vertex exchange in st
Efficient path and vertex exchange in steiner tree algorithms
✍ Duin, Cees; Vo?, Stefan πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 349 KB

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 in

Efficient special case algorithms for th
Efficient special case algorithms for the n-line planar traveling salesman problem
✍ M. Cutler πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 482 KB

## Abstract The traveling salesman problem, path, or cycle is NP‐complete. All known exact solutions to this problem are exponential. In the __N‐line planar__ traveling salesman problem the points are on __N__ lines in the plane. In this paper, simple and efficient low‐degree polynomial solutions a