Faster Scaling Algorithms for Network Problems
DOI10.1137/0218069zbMATH Open0679.68079OpenAlexW1969357318MaRDI QIDQ4729348FDOQ4729348
Harold N. Gabow, Robert E. 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)
Cited In (only showing first 100 items - show all)
- Min-Cost Flow in Unit-Capacity Planar Graphs
- Improving man-optimal stable matchings by minimum change of preference lists
- Finding approximate patterns in undirected acyclic graphs
- Optimum matchings in weighted bipartite graphs
- Optimal transport: discretization and algorithms
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Stable marriage with ties and bounded length preference lists
- Title not available (Why is that?)
- Fair matchings and related problems
- Minimum-cost flow algorithms: an experimental evaluation
- PERSISTENCE BARCODES FOR SHAPES
- Improved algorithm for the symmetry number problem on trees
- How to allocate review tasks for robust ranking
- Fixed-parameter algorithms for cluster vertex deletion
- Title not available (Why is that?)
- Single source shortest paths in \(H\)-minor free graphs
- Scaling algorithms for network problems
- Dual coordinate step methods for linear network flow problems
- A faster polynomial algorithm for the constrained maximum flow problem
- Faster algorithms for semi-matching problems
- Kaikoura tree theorems: Computing the maximum agreement subtree
- PTAS for \(p\)-means \(q\)-medoids \(r\)-given clustering problem
- Maximum weight bipartite matching in matrix multiplication time
- Edge-chromatic sum of trees and bounded cyclicity graphs
- Temporal stratification tests for linear and branching-time deductive databases
- Weighted approximate parameterized string matching
- The symmetry number problem for trees
- On a matching distance between rooted phylogenetic trees
- An efficient cost scaling algorithm for the assignment problem
- Title not available (Why is that?)
- Abstracting and Verifying Strategy-Proofness for Auction Mechanisms
- Solving all-pairs shortest path by single-source computations: theory and practice
- A new approach to all-pairs shortest paths on real-weighted graphs
- A simple reduction from maximum weight matching to maximum cardinality matching
- Algorithms for dense graphs and networks on the random access computer
- Approximate labelled subtree homeomorphism
- Computing the inertia from sign patterns
- Solving linear programs from sign patterns
- Finding minimum-cost flows by double scaling
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Parallel algorithms for the assignment and minimum-cost flow problems
- Algorithms for solving the symmetry number problem on trees
- Quantum algorithms for matching problems
- Interval graphs with side (and size) constraints
- A fast scaling algorithm for the weighted triangle-free 2-matching problem
- Reducing rank-maximal to maximum weight matching
- Title not available (Why is that?)
- Computing the agreement of trees with bounded degrees
- A weighted perfect matching with constraints on weights of its parts
- A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
- Minimum-cost flows in unit-capacity networks
- Weighted matching as a generic pruning technique applied to optimization constraints
- The assignment problem revisited
- Linear-Time Approximation for Maximum Weight Matching
- The algorithmic complexity of colour switching
- Generalized LCS
- An efficient scaling algorithm for the minimum weight bibranching problem
- Geometric algorithms for the minimum cost assignment problem
- Scaling: a canonical design problem for networks
- Using combinatorial optimization in model-based trimmed clustering with cardinality constraints
- An improved Dijkstra's shortest path algorithm for sparse network
- MuRoCo: a framework for capability- and situation-aware coalition formation in cooperative multi-robot systems
- Exact and approximation algorithms for weighted matroid intersection
- A Filtering Technique for All Pairs Approximate Parameterized String Matching
- A network flow algorithm for reconstructing binary images from discrete X-rays
- Shortest paths algorithms: Theory and experimental evaluation
- Scalable Algorithms for Data and Network Analysis
- Title not available (Why is that?)
- Mathematical models for stable matching problems with ties and incomplete lists
- Upper and lower degree-constrained graph orientation with minimum penalty
- Distribution-Free Consistent Independence Tests via Center-Outward Ranks and Signs
- A cost-scaling algorithm for \(0-1\) submodular flows
- Title not available (Why is that?)
- On the shortest path problem with negative cost cycles
- Finding real-valued single-source shortest paths in o(n 3) expected time
- A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
- Optimal Partial Tiling of Manhattan Polyominoes
- Title not available (Why is that?)
- Title not available (Why is that?)
- Covering a Tree by a Forest
- AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗
- Understanding retiming through maximum average-delay cycles
- Jacobi's bound: Jacobi's results translated in Kőnig's, Egerváry's and Ritt's mathematical languages
- Finding smallest supertrees
- Using geometry to solve the transportation problem in the plane
- A weight-scaling algorithm for \(f\)-factors of multigraphs
- Blocking trails for \(f\)-factors of multigraphs
- Title not available (Why is that?)
- Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers
- Combinatorics and algorithms for low-discrepancy roundings of a real sequence
- An improved upper bound on the expected regret of UCB-type policies for a matching-selection bandit problem
- Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths
- Title not available (Why is that?)
- Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors
- PTAS for problems of vector choice and clustering with different centers
- Computing the unrooted maximum agreement subtree in sub-quadratic time
- Tractable and intractable variations of unordered tree edit distance
- Repeatedly matching items to agents fairly and efficiently
- The dynamics of rank-maximal and popular matchings
- Repeatedly matching items to agents fairly and efficiently
This page was built for publication: Faster Scaling Algorithms for Network Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4729348)