Faster Scaling Algorithms for Network Problems
From MaRDI portal
Publication:4729348
DOI10.1137/0218069zbMath0679.68079OpenAlexW1969357318MaRDI QIDQ4729348
Harold N. Gabow, Robert Endre Tarjan
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0218069
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Optimum matchings in weighted bipartite graphs ⋮ Distribution-Free Consistent Independence Tests via Center-Outward Ranks and Signs ⋮ Fair matchings and related problems ⋮ A new approach to all-pairs shortest paths on real-weighted graphs ⋮ Edge-chromatic sum of trees and bounded cyclicity graphs ⋮ The assignment problem revisited ⋮ Quantum algorithms for matching problems ⋮ Computing the unrooted maximum agreement subtree in sub-quadratic time ⋮ Improved algorithm for the symmetry number problem on trees ⋮ Generalized LCS ⋮ Using geometry to solve the transportation problem in the plane ⋮ Understanding retiming through maximum average-delay cycles ⋮ Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers ⋮ A network flow algorithm for reconstructing binary images from discrete X-rays ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ Algorithms for solving the symmetry number problem on trees ⋮ A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching ⋮ AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗ ⋮ Dual coordinate step methods for linear network flow problems ⋮ TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE ⋮ An efficient cost scaling algorithm for the assignment problem ⋮ An improved Dijkstra's shortest path algorithm for sparse network ⋮ Solving all-pairs shortest path by single-source computations: theory and practice ⋮ Algorithms for dense graphs and networks on the random access computer ⋮ Shortest paths algorithms: Theory and experimental evaluation ⋮ Computing the inertia from sign patterns ⋮ Weighted approximate parameterized string matching ⋮ A fast scaling algorithm for the weighted triangle-free 2-matching problem ⋮ Minimum-cost flow algorithms: an experimental evaluation ⋮ Geometric algorithms for the minimum cost assignment problem ⋮ A weighted perfect matching with constraints on weights of its parts ⋮ Blocking trails for \(f\)-factors of multigraphs ⋮ A weight-scaling algorithm for \(f\)-factors of multigraphs ⋮ The dynamics of rank-maximal and popular matchings ⋮ Interval graphs with side (and size) constraints ⋮ Computing the agreement of trees with bounded degrees ⋮ Repeatedly matching items to agents fairly and efficiently ⋮ Minimum-cost flows in unit-capacity networks ⋮ PTAS for \(p\)-means \(q\)-medoids \(r\)-given clustering problem ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ Jacobi's bound: Jacobi's results translated in Kőnig's, Egerváry's and Ritt's mathematical languages ⋮ Unnamed Item ⋮ A Filtering Technique for All Pairs Approximate Parameterized String Matching ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ A simple reduction from maximum weight matching to maximum cardinality matching ⋮ An efficient scaling algorithm for the minimum weight bibranching problem ⋮ Solving linear programs from sign patterns ⋮ Weighted matching as a generic pruning technique applied to optimization constraints ⋮ On a matching distance between rooted phylogenetic trees ⋮ Improving man-optimal stable matchings by minimum change of preference lists ⋮ Finding minimum-cost flows by double scaling ⋮ Mathematical models for stable matching problems with ties and incomplete lists ⋮ Optimal transport: discretization and algorithms ⋮ Reducing rank-maximal to maximum weight matching ⋮ Near Approximation of Maximum Weight Matching through Efficient Weight Reduction ⋮ A cost-scaling algorithm for \(0-1\) submodular flows ⋮ Finding real-valued single-source shortest paths in o(n 3) expected time ⋮ The algorithmic complexity of colour switching ⋮ Using combinatorial optimization in model-based trimmed clustering with cardinality constraints ⋮ A faster polynomial algorithm for the constrained maximum flow problem ⋮ MuRoCo: a framework for capability- and situation-aware coalition formation in cooperative multi-robot systems ⋮ Combinatorics and algorithms for low-discrepancy roundings of a real sequence ⋮ How to allocate review tasks for robust ranking ⋮ Planar graphs, negative weight edges, shortest paths, and near linear time ⋮ Single source shortest paths in \(H\)-minor free graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fixed-parameter algorithms for cluster vertex deletion ⋮ Abstracting and Verifying Strategy-Proofness for Auction Mechanisms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An improved upper bound on the expected regret of UCB-type policies for a matching-selection bandit problem ⋮ Finding approximate patterns in undirected acyclic graphs ⋮ Faster Algorithms for Semi-Matching Problems ⋮ On the shortest path problem with negative cost cycles ⋮ Unnamed Item ⋮ Min-Cost Flow in Unit-Capacity Planar Graphs ⋮ PERSISTENCE BARCODES FOR SHAPES ⋮ Approximate labelled subtree homeomorphism ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems ⋮ Upper and lower degree-constrained graph orientation with minimum penalty ⋮ Stable marriage with ties and bounded length preference lists ⋮ Exact and approximation algorithms for weighted matroid intersection ⋮ Optimal Partial Tiling of Manhattan Polyominoes ⋮ Unnamed Item ⋮ Maximum weight bipartite matching in matrix multiplication time ⋮ Covering a Tree by a Forest ⋮ Temporal stratification tests for linear and branching-time deductive databases ⋮ On universally consistent and fully distribution-free rank tests of vector independence ⋮ Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Kaikoura tree theorems: Computing the maximum agreement subtree ⋮ The symmetry number problem for trees ⋮ Parallel algorithms for the assignment and minimum-cost flow problems
