Algorithms for updating minimal spanning trees

DOI10.1016/0022-0000(78)90022-3zbMath0381.05025OpenAlexW2160907067WikidataQ56077963 ScholiaQ56077963MaRDI QIDQ1247334

K. Appert

Publication date: 1978

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(78)90022-3

Mathematics Subject Classification ID

Trees (05C05) Graph theory (05C99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (17)

An O(log n) algorithm for parallel update of minimum spanning trees ⋮ An incremental linear-time learning algorithm for the optimum-path forest classifier ⋮ A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges ⋮ Optimal parallel algorithms for multiple updates of minimum spanning trees ⋮ Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems ⋮ On handling vertex deletion in updating minimum spanning trees ⋮ An efficient parallel algorithm for updating minimum spanning trees ⋮ The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Extending single tolerances to set tolerances ⋮ The central limit theorem for Euclidean minimal spanning trees. I ⋮ Optimal algorithms for sensitivity analysis in associative multiplication problems ⋮ Incremental Network Design with Minimum Spanning Trees ⋮ Compact storage schemes for formatted files by spanning trees ⋮ Associative parallel algorithm for dynamic update of a minimum spanning tree after addition of a new node to a graph ⋮ Elder-Rule-Staircodes for Augmented Metric Spaces ⋮ Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree ⋮ Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• On Finding and Updating Spanning Trees and Shortest Paths
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• The traveling-salesman problem and minimum spanning trees: Part II
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Algorithms for updating minimal spanning trees