The computational complexity of the k-minimum spanning tree problem in graded matrices

DOI10.1016/S0898-1221(98)00150-3MaRDI QIDQ1806599zbMATH OpenOpenAlexFDO

Authors Bettina Klinz, Tibor Dudás, Gerhard J. Woeginger

Publication date 8 November 1999

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0898-1221(98)00150-3

zbMATH Keywords

undirected graph

Mathematics Subject Classification ID

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

Recommendations

• The computational complexity of Steiner tree problems in graded matrices
• The complexity of minimum ratio spanning tree problems
• A note on the complexity of the generalized minimum spanning tree problem
• Matroidal degree-bounded minimum spanning trees
• An algorithm for \(k^{\text{th}}\) minimum spanning tree
• The complexity of minimizing certain cost metrics for \(k\)-source spanning trees.
• On the complexity of the bilevel minimum spanning tree problem
• Approximating \(k\)-hop minimum-spanning trees
• Minimum spanning trees in d dimensions
• scientific article; zbMATH DE number 1436136

Cites work

• scientific article; zbMATH DE number 4027206 (Why is no real title available?)
• scientific article; zbMATH DE number 1263203 (Why is no real title available?)
• scientific article; zbMATH DE number 480527 (Why is no real title available?)
• Spanning Trees—Short or Small
• The computational complexity of Steiner tree problems in graded matrices
• The minimum latency problem
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey

Cited in

(4)

• Local search algorithms for the \(k\)-cardinality tree problem.
• An algorithm for \(k^{\text{th}}\) minimum spanning tree
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• The quadratic minimum spanning tree problem and its variations

This page was built for publication: The computational complexity of the \(k\)-minimum spanning tree problem in graded matrices

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