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 (only showing first 100 items - show all)
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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear verification for spanning trees
- An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
- Applications of Path Compression on Balanced Trees
- Efficient algorithms for a family of matroid intersection problems
- Amortized Computational Complexity
- Worst-case Analysis of Set Union Algorithms
- A note on finding optimum branchings
- Efficiency of a Good But Not Linear Set Union Algorithm
- Finding Minimum Spanning Trees
- Finding optimum branchings
- Optimum branchings
- A simple derivation of edmonds' algorithm for optimum branchings
This page was built for publication: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs