Using sparsification for parametric minimum spanning tree problems

DOI10.1007/3-540-61422-2_128MaRDI QIDQ5054811zbMATH OpenOpenAlexFDO

Authors 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

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 1002204
• scientific article; zbMATH DE number 1512690
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• A practical minimum spanning tree algorithm using the cycle property

Cites work

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

Cited in

(8)

• A stronger lower bound on parametric minimum spanning trees
• Decomposable multi-parameter matroid optimization problems.
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• Finding the shortest bottleneck edge in a parametric minimum spanning tree
• scientific article; zbMATH DE number 4051021 (Why is no real title available?)
• A survey of exact and approximation algorithms for linear-parametric optimization problems
• Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint
• Parametric matroid interdiction

This page was built for publication: Using sparsification for parametric minimum spanning tree problems

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