Publication:3907583

zbMath0458.05027MaRDI QIDQ3907583

Ján Plesník

Publication date: 1981

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

zbMATH Keywords

polynomial algorithms; Steiner minimal tree; Steiner tree; minimal spanning tree

Mathematics Subject Classification ID

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

Related Items

A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes, Survivable networks, linear programming relaxations and the parsimonious property, Steiner problem in Halin networks, 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, Steiner's problem in graphs: Heuristic methods, Worst-case performance of some heuristics for Steiner's problem in directed graphs, A primal-dual approximation algorithm for the Steiner forest problem, A data structure for bicategories, with application to speeding up an approximation algorithm

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