Embedding complexity and discrete optimization. II: A dynamical programming approach to the Steiner-tree problem

DOI10.1007/S000260200003zbMath1024.90053OpenAlexW2048389490MaRDI QIDQ1400781

Dietmar Cieslik, Vincent L. Moulton, Katharina T. Huber, Andreas W. M. Dress

Publication date: 14 August 2003

Published in: Annals of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitydynamic programmingtreewidthalgorithmic complexitydiscrete optimizationSteiner minimal treesstructural complexitydivide and conquerSteiner's problemembedding complexity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Extremal problems in graph theory (05C35) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Dynamic programming (90C39)

This page was built for publication: Embedding complexity and discrete optimization. II: A dynamical programming approach to the Steiner-tree problem