Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
From MaRDI portal
Publication:5096337
DOI10.1007/3-540-59175-3_94zbMath1495.68167MaRDI QIDQ5096337
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
68W40: Analysis of algorithms
68R10: Graph theory (including graph drawing) in computer science
05C10: Planar graphs; geometric and topological aspects of graph theory
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Diameter, width, closest line pair, and parametric searching
- Sorting in \(c \log n\) parallel steps
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- A linear-time algorithm for finding a minimum spanning pseudoforest
- Infinite subgraphs as matroid circuits
- On matroids and hierarchical graphs
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- Multi-constrained matroidal knapsack problems
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Parametric Combinatorial Computing and a Problem of Program Module Distribution
- Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- An Optimal-Time Algorithm for Slope Selection
- Combinatorial Optimization with Rational Objective Functions
- A Separator Theorem for Planar Graphs
- Finding Minimum Spanning Trees
- Minimal ratio spanning trees
- Parametric Problems on Graphs of Bounded Tree-Width
- Slowing down sorting networks to obtain faster sorting algorithms
- A deterministic algorithm for the three-dimensional diameter problem
- Faster shortest-path algorithms for planar graphs
