ISSN:
1432-0541
Keywords:
Sensitivity analysis
;
Minimum spanning tree
;
Network optimization
;
Planar graphs
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We give a linear time and space algorithm for analyzing trees in planar graphs. The algorithm can be used to analyze the sensitivity of a minimum spanning tree to changes in edge costs, to find its replacement edges, and to verify its minimality. It can also be used to analyze the sensitivity of a single-source shortest-path tree to changes in edge costs, and to analyze the sensitivity of a minimum-cost network flow. The algorithm is simple and practical. It uses the properties of a planar embedding, combined with a heap-ordered queue data structure.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01187017
Permalink
