A stronger lower bound on parametric minimum spanning trees

DOI10.1007/s00453-022-01024-9OpenAlexW3162222637WikidataQ114229320 ScholiaQ114229320MaRDI QIDQ6103526

David Eppstein

Publication date: 5 June 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-01024-9

zbMATH Keywords

parametric optimizationlower boundsminimum spanning treeparametric minimum spanning tree

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation schemes for the parametric knapsack problem
• Structural and algorithmic properties for parametric minimum cuts
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Stochastic spanning tree problem
• Geometric lower bounds for parametric matroid optimization
• Parametric optimization of sequence alignment
• 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
• Maximizing Classes of Two-Parameter Objectives Over Matroids
• Parametric Solution for Linear Bicriteria Knapsack Models
• A randomized linear-time algorithm to find minimum spanning trees
• Network pricing problem with unit toll
• A Fast Parametric Maximum Flow Algorithm and Applications
• Notes on computing peaks in k-levels and parametric spanning trees
• The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems
• Point sets with many \(k\)-sets

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