Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
DOI10.1007/3-540-59175-3_94zbMATH Open1495.68167OpenAlexW2690212491MaRDI QIDQ5096337FDOQ5096337
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
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.
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)
Cites Work
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- Title not available (Why is that?)
- A Separator Theorem for Planar Graphs
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Combinatorial Optimization with Rational Objective Functions
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Maximizing concave functions in fixed dimension
- Slowing down sorting networks to obtain faster sorting algorithms
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Sorting in \(c \log n\) parallel steps
- Parametric Combinatorial Computing and a Problem of Program Module Distribution
- Parametric Problems on Graphs of Bounded Tree-Width
- An Optimal-Time Algorithm for Slope Selection
- Minimal ratio spanning trees
- Faster shortest-path algorithms for planar graphs
- Finding Minimum Spanning Trees
- Diameter, width, closest line pair, and parametric searching
- A linear-time algorithm for finding a minimum spanning pseudoforest
- On matroids and hierarchical graphs
- Infinite subgraphs as matroid circuits
- Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs
- Multi-constrained matroidal knapsack problems
- A deterministic algorithm for the three-dimensional diameter problem
- Maximizing non-linear concave functions in fixed dimension
Cited In (9)
- A stronger lower bound on parametric minimum spanning trees
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Title not available (Why is that?)
- 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)
