A stronger lower bound on parametric minimum spanning trees

DOI10.1007/978-3-030-83508-8_25OpenAlexMaRDI QIDQ832875FDO

Authors David Eppstein

Publication date 25 March 2022

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

Mathematics Subject Classification ID

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

Recommendations

• A stronger lower bound on parametric minimum spanning trees
• Lower and upper bounds for the degree-constrained minimum spanning tree problem
• Lower and upper bounds for the spanning tree with minimum branch vertices
• Lower bounds for testing Euclidean minimum spanning trees
• scientific article; zbMATH DE number 1002204
• Using sparsification for parametric minimum spanning tree problems
• Approximating minimum bounded degree spanning trees to within one of optimal
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• Lower bounds on treespan

Cites work

• scientific article; zbMATH DE number 1002204 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3717343 (Why is no real title available?)
• scientific article; zbMATH DE number 6297748 (Why is no real title available?)
• Algorithms for two bottleneck optimization problems
• An FPTAS for the parametric knapsack problem
• Approximation schemes for the parametric knapsack problem
• Finding the shortest bottleneck edge in a parametric minimum spanning tree
• Geometric lower bounds for parametric matroid optimization
• Improved bounds for planar \(k\)-sets and related problems
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• Network pricing problem with unit toll
• Notes on computing peaks in \(k\)-levels and parametric spanning trees
• Parametric Solution for Linear Bicriteria Knapsack Models
• Steiner trees, partial 2–trees, and minimum IFI networks
• The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems
• Two-phase algorithms for the parametric shortest path problem

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

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