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

Related Items (3)

A stronger lower bound on parametric minimum spanning trees ⋮ Decomposable multi-parameter matroid optimization problems. ⋮ A stronger lower bound on parametric minimum spanning trees

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
On the shortest spanning subtree of a graph and the traveling salesman problem
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
Searching among intervals and compact routing tables
Optimal Parametric Search on Graphs of Bounded Tree-Width
Efficient algorithms for a family of matroid intersection 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
A randomized linear-time algorithm to find minimum spanning trees
Slowing down sorting networks to obtain faster sorting algorithms
Weighted Multidimensional Search and Its Application to Convex Optimization
A deterministic algorithm for the three-dimensional diameter problem
On the Number of Stable States in a NOR Network
Faster shortest-path algorithms for planar graphs

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