Algorithms for updating minimal spanning trees

DOI10.1016/0022-0000(78)90022-3MaRDI QIDQ1247334zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Cites work

• A note on two problems in connexion with graphs
• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• On Finding and Updating Spanning Trees and Shortest Paths
• The traveling-salesman problem and minimum spanning trees: Part II

Cited in

(18)

• An O(log n) algorithm for parallel update of minimum spanning trees
• On handling vertex deletion in updating minimum spanning trees
• An efficient parallel algorithm for updating minimum spanning trees
• Optimal algorithms for sensitivity analysis in associative multiplication problems
• The central limit theorem for Euclidean minimal spanning trees. I
• Extending single tolerances to set tolerances
• 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
• An incremental linear-time learning algorithm for the optimum-path forest classifier
• Optimal parallel algorithms for multiple updates of minimum spanning trees
• The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems
• Associative parallel algorithm for dynamic update of a minimum spanning tree after addition of a new node to a graph
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Incremental network design with minimum spanning trees
• Compact storage schemes for formatted files by spanning trees
• Elder-rule-staircodes for augmented metric spaces
• A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges
• Efficient online sensitivity analysis for the injective bottleneck path problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1247334)