scientific article

zbMath0458.05027MaRDI QIDQ3907583

Ján Plesník

Publication date: 1981

Full work available at URL: https://eudml.org/doc/31674

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

polynomial algorithmsSteiner minimal treeSteiner treeminimal spanning tree

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

A primal-dual approximation algorithm for the Steiner forest problem, A data structure for bicategories, with application to speeding up an approximation algorithm, Steiner problem in Halin networks, A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes, Branch-and-bound as a higher-order function, Path-distance heuristic for the Steiner problem in undirected networks, Heuristics for the Steiner problem in graphs, Survivable networks, linear programming relaxations and the parsimonious property, Steiner's problem in graphs: Heuristic methods, A near linear time approximation scheme for Steiner tree among obstacles in the plane, Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation, Worst-case performance of some heuristics for Steiner's problem in directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Steiner Minimal Trees with Rectilinear Distance
• Rectilinear steiner trees: Efficient special-case algorithms
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• A Lower Bound for the Steiner Tree Problem
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• On Steiner’s Problem with Rectilinear Distance
• Steiner Minimal Trees
• Steiner's problem in graphs and its implications
• The steiner problem in graphs
• Depth-First Search and Linear Graph Algorithms