Faster Scaling Algorithms for Network Problems
From MaRDI portal
DOI10.1137/0218069zbMATH Open0679.68079OpenAlexW1969357318MaRDI QIDQ4729348FDOQ4729348
Authors: 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
Recommendations
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
- Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
- Finding approximate patterns in undirected acyclic graphs
- Scaling Algorithms for the Shortest Paths Problem
- 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
- 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?)
- 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
- A filtering technique for all pairs approximate parameterized string matching
- 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
- Algorithms for the transportation problem in geometric settings
- New scaling algorithms for the assignment and minimum mean cycle problems
- The symmetry number problem for trees
- On a matching distance between rooted phylogenetic trees
- An efficient cost scaling algorithm for the assignment problem
- Abstracting and Verifying Strategy-Proofness for Auction Mechanisms
- Solving all-pairs shortest path by single-source computations: theory and practice
- Linear-time approximation for maximum weight matching
- The Scaling Network Simplex Algorithm
- A new approach to all-pairs shortest paths on real-weighted graphs
- A simple reduction from maximum weight matching to maximum cardinality matching
- A scaling algorithm for maximum weight matching in bipartite graphs
- 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
- Reducing rank-maximal to maximum weight matching
- 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
- An out-of-kilter method for the algebraic circulation problem
- The assignment problem revisited
- The algorithmic complexity of colour switching
- Generalized LCS
- Efficient algorithms for maximum weight matchings in general graphs with small edge weights
- An efficient scaling algorithm for the minimum weight bibranching problem
- AN EFFICIENT COST SCALING ALGORITHM FOR THE INDEPENDENT ASSIGNMENT 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
- Faster scaling algorithms for general graph matching problems
- Exact and approximation algorithms for weighted matroid intersection
- 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
- Mathematical models for stable matching problems with ties and incomplete lists
- 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
- Temporal clustering
- Improving man-optimal stable matchings by minimum change of preference lists
- 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?)
- AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗
- Understanding retiming through maximum average-delay cycles
- Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
- 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
- Weighted approximate parameterized string matching
- Title not available (Why is that?)
- 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
- Finding real-valued single-source shortest paths in \(o(n^3)\) expected time
- An improved upper bound on the expected regret of UCB-type policies for a matching-selection bandit problem
- A fast scaling algorithm for the weighted triangle-free 2-matching problem
- Near approximation of maximum weight matching through efficient weight reduction
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)
