Exact algorithms for the bottleneck Steiner tree problem

DOI10.1007/s00453-011-9553-yzbMath1230.68203OpenAlexW2144383545MaRDI QIDQ652535

Shin-ichi Tanigawa, Chunseok Lee, Sang Won Bae, Sung Hee Choi

Publication date: 14 December 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9553-y

zbMATH Keywords

optimizationcomputational geometryexact algorithmfixed-parameter tractabilitySteiner pointbottleneck Steiner tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Simplifying obstacles for Steiner network problems in the plane, Survivable minimum bottleneck networks, An exact algorithm for the bottleneck 2-connected \(k\)-Steiner network problem in \(L_p\) planes, Generalised \(k\)-Steiner tree problems in normed planes, On the restricted \(k\)-Steiner tree problem

Uses Software

• ISOLATE

Cites Work

• Parametric search made practical
• On exact solutions to the Euclidean bottleneck Steiner tree problem
• Voronoi diagram for services neighboring a highway
• Sorting in \(c \log n\) parallel steps
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• The upper envelope of Voronoi surfaces and its applications
• Solving zero-dimensional systems through the rational univariate representation
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Approximations for a bottleneck Steiner tree problem
• Optimal and approximate bottleneck Steiner trees
• An approximation algorithm for a bottleneck \(k\)-Steiner tree problem in the Euclidean plane
• Solving polynomial equations. Foundations, algorithms, and applications
• Research Problems in Discrete Geometry
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• The Kissing Numbers of Convex Bodies - A Brief Survey
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
• Slowing down sorting networks to obtain faster sorting algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item