On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results

DOI10.1007/s004539910005zbMath0951.68101OpenAlexW2066933505MaRDI QIDQ1969944

Michael Kaufmann, Ulrich Fößmeier

Publication date: 12 December 2000

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s004539910005

zbMATH Keywords

algorithmsdynamic programmingRectilinear Steiner trees

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology, The number of tree stars is \(O^{*}(1.357^k)\), Definition and algorithms for reliable Steiner tree problem, Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees, The number of tree stars is O*(1.357k)