Using sparsification for parametric minimum spanning tree problems

DOI10.1007/3-540-61422-2_128zbMath1502.68224MaRDI QIDQ5054811

Giora Slutzki, David Eppstein, David Fernández Baca

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT'96 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61422-2_128

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C05: Trees

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

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Diameter, width, closest line pair, and parametric searching
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Stochastic spanning tree problem
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• Extremal polygon containment problems
• Multi-constrained matroidal knapsack problems
• A data structure for dynamic trees
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Parametric Combinatorial Computing and a Problem of Program Module Distribution
• Maximizing Classes of Two-Parameter Objectives Over Matroids
• Combinatorial Optimization with Rational Objective Functions
• Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
• Minimal ratio spanning trees
• An optimal algorithm for intersecting line segments in the plane
• Choosing Subsets with Maximum Weighted Average
• A randomized linear-time algorithm to find minimum spanning trees
• Slowing down sorting networks to obtain faster sorting algorithms
• Optimal parametric search on graphs of bounded tree-width
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• Separator based sparsification for dynamic planar graph algorithms
• A deterministic algorithm for the three-dimensional diameter problem