A LINEAR ALGORITHM FOR ANALYSIS OF MINIMUM SPANNING AND SHORTEST-PATH TREES OF PLANAR GRAPHS

被引：19

作者：

BOOTH, H

WESTBROOK, J

机构：

[1] PRINCETON UNIV, DEPT COMP SCI, PRINCETON, NJ 08544 USA

[2] YALE UNIV, DEPT COMP SCI, NEW HAVEN, CT 06520 USA

[3] STANFORD UNIV, DEPT COMP SCI, STANFORD, CA 94305 USA

来源：

ALGORITHMICA | 1994年 / 11卷 / 04期

关键词：

SENSITIVITY ANALYSIS; MINIMUM SPANNING TREE; NETWORK OPTIMIZATION; PLANAR GRAPHS;

D O I：

10.1007/BF01187017

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：341 / 352

页数：12

共 19 条

[1] TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].