Probabilistic partitioning algorithms for the rectilinear steiner problem

DOI10.1002/NET.3230150403MaRDI QIDQ3789373zbMATH OpenOpenAlexFDO

Authors János Komlós, Man-tak Shing

Publication date 1985

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230150403

zbMATH Keywords

approximate solutionpartitioning algorithmsrectilinear Steiner problemSteiner treeundirected graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Inventory, storage, reservoirs (90B05) Programming involving graphs or networks (90C35)

Recommendations

• Probabilistic analysis of an enhanced partitioning algorithm for the steiner tree problem in R^d
• scientific article; zbMATH DE number 426374
• A probably fast, provably optimal algorithm for rectilinear Steiner trees
• A practical algorithm for the minimum rectilinear Steiner tree
• Two probabilistic results on rectilinear Steiner trees

Cited in

(11)

• Two probabilistic results on rectilinear Steiner trees
• Fast heuristic algorithms for rectilinear Steiner trees
• Computing optimal rectilinear Steiner trees: A survey and experimental evaluation
• Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study
• The Steiner tree problem in orientation metrics
• Two-level rectilinear Steiner trees
• Probabilistic analysis of an enhanced partitioning algorithm for the steiner tree problem in R^d
• A probably fast, provably optimal algorithm for rectilinear Steiner trees
• Experimental evaluation of a partitioning algorithm for the steiner tree problem in R² and R³
• Practical Partitioning-Based Methods for the Steiner Problem
• Comments on Bern's probabilistic results on rectilinear Steiner trees

This page was built for publication: Probabilistic partitioning algorithms for the rectilinear steiner problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3789373)