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

DOI10.1016/S0898-1221(98)00150-3zbMATH Open0939.68091OpenAlexW1995291660MaRDI QIDQ1806599FDOQ1806599

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)

Cites Work

• Title not available (Why is that?)
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
• The minimum latency problem
• Title not available (Why is that?)
• Spanning Trees—Short or Small
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• The computational complexity of Steiner tree problems in graded matrices
• Title not available (Why is that?)

Cited In (3)

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

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎
• Title not available (Why is that?) 👍 👎

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)