A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs

DOI10.1007/BF01187017zbMath0804.68106OpenAlexW2078199146MaRDI QIDQ1322567

Jeffery Westbrook, Heather Booth

Publication date: 16 June 1994

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01187017

zbMATH Keywords

sensitivity analysisplanar graphsminimum spanning treenetwork optimizationlinear algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges ⋮ Optimal parallel verification of minimum spanning trees in logarithmic time ⋮ Finding the k smallest spanning trees ⋮ The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Distributed verification of minimum spanning trees ⋮ Efficient computation of tolerances in the weighted independent set problem for some classes of graphs ⋮ Finding best swap edges minimizing the routing cost of a spanning tree ⋮ Finding the \(k\) smallest spanning trees ⋮ Improved algorithms for replacement paths problems in restricted graphs ⋮ Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs ⋮ The cable trench problem: Combining the shortest path and minimum spanning tree problems ⋮ A new algorithm for the minimum spanning tree verification problem

Cites Work

• Unnamed Item
• Unnamed Item
• A linear algorithm for embedding planar graphs using PQ-trees
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Applications of Path Compression on Balanced Trees
• A note on Arc tolerances in sparse shortest-path and network flow problems
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• A Separator Theorem for Planar Graphs
• Arc tolerances in shortest path and network flow problems
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• Finding Dominators in Directed Graphs
• Efficient Planarity Testing
• Finding Minimum Spanning Trees
• The Two-Triangle Case of the Acquaintance Graph
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs