Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
From MaRDI portal
Publication:1086246
The authors use the Fibonacci heap to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. Both algorithms can be extended to allow a degree constraint at one vertex.
Recommendations
- scientific article; zbMATH DE number 3980506
- scientific article; zbMATH DE number 2201897
- A randomized linear-time algorithm to find minimum spanning trees
- An I/O efficient algorithm for minimum spanning trees
- Exact algorithms for finding constrained minimum spanning trees
- A new algorithm for minimum spanning tree using depth-first-search in an undirected graph
- An algorithm for \(k^{\text{th}}\) minimum spanning tree
- A randomized linear-time algorithm for finding minimum spanning trees (extended abstract)
- An optimal minimum spanning tree algorithm
Cites work
- A note on finding optimum branchings
- A simple derivation of edmonds' algorithm for optimum branchings
- Amortized Computational Complexity
- An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
- Applications of Path Compression on Balanced Trees
- Efficiency of a Good But Not Linear Set Union Algorithm
- Efficient algorithms for a family of matroid intersection problems
- Finding Minimum Spanning Trees
- Finding optimum branchings
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 3285076 (Why is no real title available?)
- scientific article; zbMATH DE number 3373559 (Why is no real title available?)
- Linear verification for spanning trees
- Optimum branchings
- Worst-case Analysis of Set Union Algorithms
Cited in
(only showing first 100 items - show all)- Combinatorial optimization in system configuration design
- The pairing heap: A new form of self-adjusting heap
- A linear-time algorithm for finding a minimum spanning pseudoforest
- A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
- On matroids and hierarchical graphs
- Facets of two Steiner arborescence polyhedra
- Finding the \(k\) smallest spanning trees
- An efficient algorithm for minimum-weight bibranching
- Modifying edges of a network to obtain short subgraphs
- Efficient associative algorithm to find the least spanning tree of a graph with a node degree constraint
- An efficient approximation algorithm for the survivable network design problem
- Worst-case performance of some heuristics for Steiner's problem in directed graphs
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- On spanning 2-trees in a graph
- Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
- Spanning trees and shortest paths in Monge graphs
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Arborescence optimization problems solvable by Edmonds' algorithm
- Fuzzy random bottleneck spanning tree problems using possibility and necessity measures
- An optimal PRAM algorithm for a spanning tree on trapezoid graphs.
- Lexicographic balanced optimization problems
- The expected complexity of Prim's minimum spanning tree algorithm
- Evolutionary local search for the edge-biconnectivity augmentation problem
- Increasing digraph arc-connectivity by arc addition, reversal and complement
- Consensus of nonlinear multi-agent systems with directed switching graphs: a directed spanning tree based error system approach
- 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
- Two variations of the minimum Steiner problem
- Counting minimum weight arborescences
- The minimum spanning tree problem on a planar graph
- The non-approximability of bicriteria network design problems
- A note on practical construction of maximum bandwidth paths.
- Balancing minimum spanning trees and shortest-path trees
- Combinatorial algorithms for DNA sequence assembly
- Constrained matroidal bottleneck problems
- Robustness of minimum cost arborescences
- Shortest bibranchings and valuated matroid intersection
- The weighted arborescence constraint
- Approximation algorithms for solving the line-capacitated minimum Steiner tree problem
- A greedy algorithm for finding maximum spanning trees in infinite graphs
- Approximate minimum directed spanning trees under congestion
- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- Containment control of directed networks with time-varying nonlinear multi-agents using minimum number of leaders
- Unsupervised representation learning with minimax distance measures
- Observer-based consensus for multi-agent systems with partial adaptive dynamic protocols
- Arithmetic and \(k\)-maximality of the cyclic free magma
- Optimal parallel verification of minimum spanning trees in logarithmic time
- Heuristics for planning with penalties and rewards formulated in logic and computed through circuits
- Compressing table data with column dependency
- Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
- A distributed algorithm for directed minimum-weight spanning tree
- Density-based O-means clustering algorithm using minimum spanning tree
- Generating good starting solutions for the \(p\)-median problem in the plane
- The complexity of the node capacitated in-tree packing problem
- A novel dynamic minimum spanning tree based clustering method for image mining
- On coefficients of the characteristic polynomial of the Laplace matrix of a weighted digraph and the all minors theorem
- Linear time approximation algorithms for~degree~constrained subgraph problems
- Building knowledge maps of web graphs
- The complexity of speedrunning video games
- New heuristic algorithms for solving the planar p-median problem
- Hollow Heaps
- An optimal parallel algorithm for minimum spanning trees in planar graphs
- scientific article; zbMATH DE number 3980506 (Why is no real title available?)
- Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs
- scientific article; zbMATH DE number 1069311 (Why is no real title available?)
- Distributed consensus for multiagent systems via directed spanning tree based adaptive control
- The saga of minimum spanning trees
- A new algorithm for minimum spanning tree using depth-first-search in an undirected graph
- Exact algorithms for the solution of the grey pattern quadratic assignment problem
- On finding optimal polytrees
- Fractional virus epidemic model on financial networks
- Using sparsification for parametric minimum spanning tree problems
- Finding the k smallest spanning trees
- On matroids and hierarchical graphs
- Integer Programming Formulations for Minimum Spanning Tree Interdiction
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- New local searches for solving the multi-source Weber problem
- Bribery and control in stable marriage
- Approximation algorithms for graph augmentation
- A fast minimum spanning tree algorithm based on \(K\)-means
- Improved similarity measure in neutrosophic environment and its application in finding minimum spanning tree
- EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
- scientific article; zbMATH DE number 2201897 (Why is no real title available?)
- An algorithm for the minimum spanning tree with a pivotal point in directed networks
- Fuzzy quadratic minimum spanning tree problem
- Robust Hierarchical Clustering for Directed Networks: An Axiomatic Approach
- Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin-Marsten bounding
- 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
- The multi-weighted spanning tree problem
- Exact and anytime approach for solving the time dependent traveling salesman problem with time windows
- From symmetry to asymmetry: generalizing TSP approximations by parametrization
- Algorithm for sequential construction of spanning minimal directed forests
- scientific article; zbMATH DE number 7692724 (Why is no real title available?)
- 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
- An efficient scaling algorithm for the minimum weight bibranching problem
- Efficiently computing directed minimum spanning trees
This page was built for publication: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1086246)
