𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The computational complexity of Steiner tree problems in graded matrices

✍ Scribed by T. Dudás; B. Klinz; G.J. Woeginger

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
349 KB
Volume
10
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

✦ Synopsis

Communicated by M. Iri

Abstract--We investigate the computational complexity of the Steiner tree problem in graphs when the distance matrix is graded, i.e., has increasing, respectively, decreasing rows, or increasing, respectively, decreasing columns, or both. We exactly characterize polynomially solvable and NP-hard variants, and thus, establish a sharp borderline between easy and difficult cases of this optimization problem.

📜 SIMILAR VOLUMES

The computational complexity of the κ-mi
The computational complexity of the κ-minimum spanning tree problem in graded matrices
✍ T. Dudás; B. Klinz; G.J. Woeginger 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 524 KB

Given an undirected graph G = (V, E) where each edge e = (i,j) has a length dij >\_ O, the k-minimum spanning tree problem, k-MST for short, is to find a tree T in G which spans at least k vertices and has minimum length l(T) = ~'~(~,j)e T dij. We investigate the computational complexity of the k-mi

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

The communication complexity of several
The communication complexity of several problems in matrix computation
✍ Jeff I Chu; Georg Schnitger 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 747 KB

The communication complexity of a function f measures the communication resources required for computingf. In the design of VLSI systems, where savings on the chip area and computation time are desired, this complexity dictates an area x time\* lower bound. We investigate the communication complexit