A stronger lower bound on parametric minimum spanning trees

DOI10.1007/978-3-030-83508-8_25OpenAlexW3196452198MaRDI QIDQ832875

David Eppstein

Publication date: 25 March 2022

Full work available at URL: https://arxiv.org/abs/2105.05371

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation schemes for the parametric knapsack problem
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Geometric lower bounds for parametric matroid optimization
• Improved bounds for planar \(k\)-sets and related problems
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• An FPTAS for the parametric knapsack problem
• Two-phase algorithms for the parametric shortest path problem
• Steiner trees, partial 2–trees, and minimum IFI networks
• The Parametric Closure Problem
• Algorithms for two bottleneck optimization problems
• Parametric Solution for Linear Bicriteria Knapsack Models
• Network pricing problem with unit toll
• Notes on computing peaks in k-levels and parametric spanning trees
• The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems

This page was built for publication: A stronger lower bound on parametric minimum spanning trees