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

From MaRDI portal
Revision as of 00:58, 31 January 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 LoadingAn efficient mixed integer linear programming model for the minimum spanning tree problemA branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problemSteiner problems on directed acyclic graphsIncreasing digraph arc-connectivity by arc addition, reversal and complementTrans-dichotomous algorithms for minimum spanning trees and shortest pathsOptimal parallel verification of minimum spanning trees in logarithmic timeOn 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 problemThe pairing heap: A new form of self-adjusting heapOn coefficients of the characteristic polynomial of the Laplace matrix of a weighted digraph and the all minors theoremSemi-preemptive routing on a linear and circular trackA novel dynamic minimum spanning tree based clustering method for image miningHollow HeapsFrom symmetry to asymmetry: generalizing TSP approximations by parametrizationUsing sparsification for parametric minimum spanning tree problemsFinding the k smallest spanning treesA linear-time algorithm for finding a minimum spanning pseudoforestBuilding knowledge maps of web graphsBalancing minimum spanning trees and shortest-path treesOn spanning 2-trees in a graphAn Optimal Parallel Algorithm for Minimum Spanning Trees in Planar GraphsCombinatorial algorithms for DNA sequence assemblyHeuristics for planning with penalties and rewards formulated in logic and computed through circuitsNew heuristic algorithms for solving the planar \(p\)-median problemContainment control of directed networks with time-varying nonlinear multi-agents using minimum number of leadersMinimum spanning trees in networks with varying edge weightsA matroid algorithm and its application to the efficient solution of two optimization problems on graphsDistributed Consensus for Multiagent Systems via Directed Spanning Tree Based Adaptive ControlDynamic trees as search trees via Euler tours, applied to the network simplex algorithmConstrained matroidal bottleneck problemsInteger Programming Formulations for Minimum Spanning Tree InterdictionThe complexity of speedrunning video gamesSpanning trees and shortest paths in Monge graphsMinimax regret spanning arborescences under uncertain costsRobustness of minimum cost arborescencesShortest bibranchings and valuated matroid intersectionSolving the planar \(p\)-Median problem by variable neighborhood and concentric searchesLinear-time algorithms for parametric minimum spanning tree problems on planar graphsThe multi-weighted spanning tree problemExact and anytime approach for solving the time dependent traveling salesman problem with time windowsLearning extended tree augmented naive structuresArborescence optimization problems solvable by Edmonds' algorithmAlgorithm for sequential construction of spanning minimal directed forestsConsensus of nonlinear multi-agent systems with directed switching graphs: a directed spanning tree based error system approachA distributed algorithm for directed minimum-weight spanning treeFuzzy random bottleneck spanning tree problems using possibility and necessity measuresLinear Time Approximation Algorithms for Degree Constrained Subgraph Problemsk-sum optimization problemsUnnamed ItemThe saga of minimum spanning treesUnsupervised representation learning with minimax distance measuresAn efficient scaling algorithm for the minimum weight bibranching problemEfficient verification of distributed real-time systems with broadcasting behaviorsAn optimal PRAM algorithm for a spanning tree on trapezoid graphs.Lexicographic balanced optimization problemsOn matroids and hierarchical graphsFacets of two Steiner arborescence polyhedraExact algorithms for the solution of the grey pattern quadratic assignment problemAn O(log n) parallel algorithm for constructing a spanning tree on permutation graphs1-Approximation algorithm for bottleneck disjoint path matchingCompressing table data with column dependencyOn finding optimal polytreesRobust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulationFractional virus epidemic model on financial networksBribery and Control in Stable MarriageNew local searches for solving the multi-source Weber problemFinding the \(k\) smallest spanning treesA fast minimum spanning tree algorithm based on \(K\)-meansRisk-control approach for a bottleneck spanning tree problem with the total network reliability under uncertaintyAn LP-based heuristic algorithm for the node capacitated in-tree packing problemThe weighted arborescence constraintApproximating optimum branchings in linear timeFuzzy quadratic minimum spanning tree problemFrom symmetry to asymmetry: generalizing TSP approximations by parametrizationTwo variations of the minimum Steiner problemOn matroids and hierarchical graphsFinding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)Minimum-weight spanning tree algorithms. A survey and empirical studyApproximation algorithms for graph augmentationCounting minimum weight arborescencesThe minimum spanning tree problem on a planar graphObserver-based consensus for multi-agent systems with partial adaptive dynamic protocolsAn efficient algorithm for minimum-weight bibranchingModifying edges of a network to obtain short subgraphsCombinatorial optimization in system configuration designLinear-time algorithms for parametric minimum spanning tree problems on planar graphsDensity-based O-Means clustering algorithm using minimum spanning treeArithmetic and \(k\)-maximality of the cyclic free magmaThe non-approximability of bicriteria network design problemsEfficient associative algorithm to find the least spanning tree of a graph with a node degree constraintGenerating good starting solutions for the p-median problem in the planeAn efficient approximation algorithm for the survivable network design problemApproximation algorithms for solving the line-capacitated minimum Steiner tree problemA note on practical construction of maximum bandwidth paths.Robust Hierarchical Clustering for Directed Networks: An Axiomatic ApproachImproving dynamic programming for travelling salesman with precedence constraints: parallel Morin–Marsten boundingWorst-case performance of some heuristics for Steiner's problem in directed graphsThe expected complexity of Prim's minimum spanning tree algorithmEvolutionary local search for the edge-biconnectivity augmentation problem




Cites Work




This page was built for publication: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs