A note on the k-minimum spanning tree problem on circles

DOI10.1016/J.ORL.2015.12.019MaRDI QIDQ1785744zbMATH OpenOpenAlexFDO

Authors Thomas Knecht, Dieter Jungnickel

Publication date 1 October 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2015.12.019

zbMATH Keywords

dynamic programmingshortest path problem$k$-minimum spanning tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39)

Recommendations

• scientific article; zbMATH DE number 1003287
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• Publication:4952696
• On constructing minimum spanning trees in \(R_ 1^ k\)
• An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane

Cites work

• Spanning Trees—Short or Small
• Weighted k‐cardinality trees: Complexity and polyhedral structure

Cited in

(3)

• An Efficient Geometric Solution to the Minimum Spanning Circle Problem
• A Note on the Complexity of a Simple Transportation Problem
• scientific article; zbMATH DE number 447202 (Why is no real title available?)

This page was built for publication: A note on the $k$-minimum spanning tree problem on circles

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