Linear-time algorithms for parametric minimum spanning tree problems on planar graphs

DOI10.1007/3-540-59175-3_94MaRDI QIDQ5096337zbMATH OpenOpenAlexFDO

Authors Giora Slutzki, David Fernández-Baca

Publication date 16 August 2022

Published in LATIN '95: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59175-3_94

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• scientific article; zbMATH DE number 1512690
• scientific article; zbMATH DE number 1002204
• Using sparsification for parametric minimum spanning tree problems
• Two linear time algorithms for MST on minor closed graph classes.

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A deterministic algorithm for the three-dimensional diameter problem
• A linear-time algorithm for finding a minimum spanning pseudoforest
• An Optimal-Time Algorithm for Slope Selection
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Combinatorial Optimization with Rational Objective Functions
• Diameter, width, closest line pair, and parametric searching
• Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Faster shortest-path algorithms for planar graphs
• Finding Minimum Spanning Trees
• Infinite subgraphs as matroid circuits
• Maximizing concave functions in fixed dimension
• Maximizing non-linear concave functions in fixed dimension
• Minimal ratio spanning trees
• Multi-constrained matroidal knapsack problems
• On matroids and hierarchical graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Parametric Combinatorial Computing and a Problem of Program Module Distribution
• Parametric Problems on Graphs of Bounded Tree-Width
• Slowing down sorting networks to obtain faster sorting algorithms
• Sorting in \(c \log n\) parallel steps
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths

Cited in

(9)

• A stronger lower bound on parametric minimum spanning trees
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• scientific article; zbMATH DE number 1107724 (Why is no real title available?)
• Notes on computing peaks in \(k\)-levels and parametric spanning trees
• On finding optimal and near-optimal lineal spanning trees
• A Linear Time Algorithm for the Minimum Spanning Caterpillar Problem for Bounded Treewidth Graphs
• A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
• Two linear time algorithms for MST on minor closed graph classes.
• Using sparsification for parametric minimum spanning tree problems

This page was built for publication: Linear-time algorithms for parametric minimum spanning tree problems on planar graphs

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