Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
SIAM Journal on ComputingPublished 1 November 1985
Greg N. Frederickson
Citations380
SJR quartileQ1
SJR score1.40
SNIP1.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph.
Abstract
Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph. For the case of a general graph, maintaining the data structure and updating the tree are shown to take $O(\sqrt m )$ time, where m is the number of edges in the graph. For the case of a planar graph, a data structure is presented which supports an update time of $O((\log m)^2 )$. These structures contribute to improved solutions for the on-line connected components problem and the problem of generating the K smallest spanning trees.
Keywords
Computer ScienceEngineering
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
Journal of Computer and System SciencesA data structure for dynamic trees
1,040 Citations1983Daniel D. Sleator, Robert E. Tarjan
Journal of Computer and System SciencesMaintenance of configurations in the plane
462 Citations1981Mark H. Overmars, Jan Van Leeuwen
A fully dynamic maintenance algorithm for convex hulls that can process insertions and deletions of single points in only O(log* n) steps per transaction, where n is the number of points currently in the set.
SIAM Journal on ComputingFinding Minimum Spanning Trees
425 Citations1976David R. Cheriton, Robert E. Tarjan
This paper studies methods for finding minimum spanning trees in graphs and results include relationships with other problems which might lead general lower bound for the complexity of the minimum spanning tree problem.
Journal of the ACMApplications of Path Compression on Balanced Trees
298 Citations1979Robert E. Tarjan
A method for computing functions defined on paths in trees based on tree manipulation techniques first used for efficiently representing equivalence relations, which has an almost-linear running time and is useful for solving certain kinds of pathfinding problems on reducible graphs.
Journal of the ACMAn On-Line Edge-Deletion Problem
283 Citations1981Yossi Shiloach, Shimon Even
An algorithm is presented which maintains a data structure in which each question is answered in constant time and for which the total time involved in answering q questions and maintaining the data structure is O(q + I VI) lED.
Journal of the ACMAdding range restriction capability to dynamic data structures
184 Citations1985Dan E. Willard, George S. Lueker
A transformation is presented that enables range restrictions to be added to an arbitrary dynamic data structure on n elements, provided that the problem satisfies a certain decomposability condition and that one is willing to allow increases by a factor of O in the worst-case time for an operation and in the space used.
Information Processing LettersAn 0(|E|loglog|V|) algorithm for finding minimum spanning trees
159 Citations1975Andrew Chi-Chih Yao
The algorithm is a modification of an algorithm by SoWn that works by successively enlarging, components al the MST, by shrinking each group of vertices to node, to obtain a new graph with at most odes.
SIAM Journal on ComputingTwo Algorithms for Generating Weighted Spanning Trees in Order
154 Citations1977Harold N. Gabow
Two algorithms for generating spanning trees of a connected graph in order of increasing weight are presented, one of which generates the K smallest weight trees, where K can be specified in advance or during execution of the algorithm.
Data structures for on-line updating of minimum spanning trees
141 Citations1983Greg N. Frederickson
Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph.
SIAM Journal on ComputingOn Finding and Updating Spanning Trees and Shortest Paths
139 Citations1975Philip M. Spira, Aimin Pan
The most notable result is that a spanning tree solution can be updated in $O(n)$ when a new node is added to an n-node graph whose minimum spanning tree is known.
Journal of Computer and System SciencesAlgorithms for updating minimal spanning trees
91 Citations1978F.P.S. Chin, David J. Houck
Another O(n) algorithm simpler than that presented by Spira and Pan for the insertion of a vertex is presented and labels the vertices of the graph in such a way that any vertex may be deleted from the graph and the minimal spanning tree can be updated in constant time.
SIAM Journal on ComputingAn Algorithm for Finding <i>K</i> Minimum Spanning Trees
86 Citations1981Naoki Katoh, Toshihide Ibaraki +1 more
This paper presents an algorithm for finding K minimum spanning trees in an undirected graph based on three subroutines which obtains the kth minimum spanning tree in $O(m)$ steps when the jthminimum spanning trees for $j = 1,2, \cdots ,k - 1$ are given.
Data structures for on-line updating of matroid intersection solutions
2 Citations1984Greg N. Frederickson, Mandayam A. Srinivas
Matroid intersection problems are considered in which one of the matroids is a partition matroid specifying that exactly q elements in the solution must be red, and the rest green, and a characterization is presented for how the solution changes when one element changes in cost.