Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

From MaRDI portal
Publication:1086246

DOI10.1007/BF02579168zbMath0608.05027OpenAlexW1982512167WikidataQ56077911 ScholiaQ56077911MaRDI QIDQ1086246

Harold N. Gabow, Robert Endre Tarjan, Zvi Galil, Thomas H. Spencer

Publication date: 1986

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579168



Related Items

An Additive Branch-and-Bound Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO or FIFO Loading, An efficient mixed integer linear programming model for the minimum spanning tree problem, A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem, Steiner problems on directed acyclic graphs, Increasing digraph arc-connectivity by arc addition, reversal and complement, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Optimal parallel verification of minimum spanning trees in logarithmic time, On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\), The complexity of the node capacitated in-tree packing problem, The pairing heap: A new form of self-adjusting heap, On coefficients of the characteristic polynomial of the Laplace matrix of a weighted digraph and the all minors theorem, Semi-preemptive routing on a linear and circular track, A novel dynamic minimum spanning tree based clustering method for image mining, Hollow Heaps, From symmetry to asymmetry: generalizing TSP approximations by parametrization, Using sparsification for parametric minimum spanning tree problems, Finding the k smallest spanning trees, A linear-time algorithm for finding a minimum spanning pseudoforest, Building knowledge maps of web graphs, Balancing minimum spanning trees and shortest-path trees, On spanning 2-trees in a graph, An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs, Combinatorial algorithms for DNA sequence assembly, Heuristics for planning with penalties and rewards formulated in logic and computed through circuits, New heuristic algorithms for solving the planar \(p\)-median problem, Containment control of directed networks with time-varying nonlinear multi-agents using minimum number of leaders, Minimum spanning trees in networks with varying edge weights, A matroid algorithm and its application to the efficient solution of two optimization problems on graphs, Distributed Consensus for Multiagent Systems via Directed Spanning Tree Based Adaptive Control, Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm, Constrained matroidal bottleneck problems, Integer Programming Formulations for Minimum Spanning Tree Interdiction, The complexity of speedrunning video games, Spanning trees and shortest paths in Monge graphs, Minimax regret spanning arborescences under uncertain costs, Robustness of minimum cost arborescences, Shortest bibranchings and valuated matroid intersection, Solving the planar \(p\)-Median problem by variable neighborhood and concentric searches, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, The multi-weighted spanning tree problem, Exact and anytime approach for solving the time dependent traveling salesman problem with time windows, Learning extended tree augmented naive structures, Arborescence optimization problems solvable by Edmonds' algorithm, Algorithm for sequential construction of spanning minimal directed forests, Consensus of nonlinear multi-agent systems with directed switching graphs: a directed spanning tree based error system approach, A distributed algorithm for directed minimum-weight spanning tree, Fuzzy random bottleneck spanning tree problems using possibility and necessity measures, Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems, k-sum optimization problems, Unnamed Item, The saga of minimum spanning trees, Unsupervised representation learning with minimax distance measures, An efficient scaling algorithm for the minimum weight bibranching problem, Efficient verification of distributed real-time systems with broadcasting behaviors, An optimal PRAM algorithm for a spanning tree on trapezoid graphs., Lexicographic balanced optimization problems, On matroids and hierarchical graphs, Facets of two Steiner arborescence polyhedra, Exact algorithms for the solution of the grey pattern quadratic assignment problem, An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs, 1-Approximation algorithm for bottleneck disjoint path matching, Compressing table data with column dependency, On finding optimal polytrees, Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation, Fractional virus epidemic model on financial networks, Bribery and Control in Stable Marriage, New local searches for solving the multi-source Weber problem, Finding the \(k\) smallest spanning trees, A fast minimum spanning tree algorithm based on \(K\)-means, Risk-control approach for a bottleneck spanning tree problem with the total network reliability under uncertainty, An LP-based heuristic algorithm for the node capacitated in-tree packing problem, The weighted arborescence constraint, Approximating optimum branchings in linear time, Fuzzy quadratic minimum spanning tree problem, From symmetry to asymmetry: generalizing TSP approximations by parametrization, Two variations of the minimum Steiner problem, On matroids and hierarchical graphs, Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\), Minimum-weight spanning tree algorithms. A survey and empirical study, Approximation algorithms for graph augmentation, Counting minimum weight arborescences, The minimum spanning tree problem on a planar graph, Observer-based consensus for multi-agent systems with partial adaptive dynamic protocols, An efficient algorithm for minimum-weight bibranching, Modifying edges of a network to obtain short subgraphs, Combinatorial optimization in system configuration design, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Density-based O-Means clustering algorithm using minimum spanning tree, Arithmetic and \(k\)-maximality of the cyclic free magma, The non-approximability of bicriteria network design problems, Efficient associative algorithm to find the least spanning tree of a graph with a node degree constraint, Generating good starting solutions for the p-median problem in the plane, An efficient approximation algorithm for the survivable network design problem, Approximation algorithms for solving the line-capacitated minimum Steiner tree problem, A note on practical construction of maximum bandwidth paths., Robust Hierarchical Clustering for Directed Networks: An Axiomatic Approach, Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin–Marsten bounding, Worst-case performance of some heuristics for Steiner's problem in directed graphs, The expected complexity of Prim's minimum spanning tree algorithm, Evolutionary local search for the edge-biconnectivity augmentation problem, A linear time algorithm for the maximum capacity path problem, Approximate minimum directed spanning trees under congestion, Improved similarity measure in neutrosophic environment and its application in finding minimum spanning tree



Cites Work