Faster scaling algorithms for general graph matching problems
From MaRDI portal
Publication:4302856
DOI10.1145/115234.115366zbMath0799.68145OpenAlexW2091299439WikidataQ127782667 ScholiaQ127782667MaRDI QIDQ4302856
Harold N. Gabow, Robert Endre Tarjan
Publication date: 6 October 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/115234.115366
linear programmingscalingtravelling salesmannetwork optimizationaugmenting pathblossomminimum-cost matching
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)
Related Items
Approximation Algorithms for the Traveling Salesman Problem with Range Condition, Maximum matchings in planar graphs via Gaussian elimination, Approximation algorithms for the TSP with sharpened triangle inequality, Adaptive paired comparison design, An extension of Hall's theorem for partitioned bipartite graphs, Node-Balancing by Edge-Increments, Improved algorithm for the symmetry number problem on trees, Paths and trails in edge-colored graphs, Stochastic approximation versus sample average approximation for Wasserstein barycenters, Approximating the Metric TSP in Linear Time, Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers, 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, Two dimensional maximum weight matching using Manhattan topology, On equistable, split, CIS, and related classes of graphs, Improved bounds for vehicle routing solutions, Incremental assignment problem, Dual coordinate step methods for linear network flow problems, Graph factors and factorization: 1985--2003: a survey, Clique-perfectness and balancedness of some graph classes, Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching, On the Power of Tree-Depth for Fully Polynomial FPT Algorithms, A fast scaling algorithm for the weighted triangle-free 2-matching problem, Speeding up Graph Algorithms via Switching Classes, A 4/3-approximation for TSP on cubic 3-edge-connected graphs, 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, Maximum skew-symmetric flows, An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach, Approximate shortest paths in weighted graphs, Bayesian locally optimal design of knockout tournaments, Non-aligned Drawings of Planar Graphs, Almost exact matchings, Variations of maximum-clique transversal sets on graphs, (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings, Solving mean-payoff games via quasi dominions, A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs, Maximum matching in regular and almost regular graphs, Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems, Pareto optimality in coalition formation, The power of linear-time data reduction for maximum matching, A simple reduction from maximum weight matching to maximum cardinality matching, Approximating the metric TSP in linear time, Fork-forests in bi-colored complete bipartite graphs, An efficient scaling algorithm for the minimum weight bibranching problem, Equistable simplicial, very well-covered, and line graphs, Bi-criteria and approximation algorithms for restricted matchings, A model for minimizing active processor time, Weighted matching as a generic pruning technique applied to optimization constraints, Research on solution space of bipartite graph vertex-cover by maximum matchings, Core influence mechanism on vertex-cover problem through leaf-removal-core breaking, Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version), Approximating Edge Dominating Set in Dense Graphs, Near Approximation of Maximum Weight Matching through Efficient Weight Reduction, Processor efficient parallel matching, Diverse Pairs of Matchings, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Cluster editing with locally bounded modifications, Unnamed Item, Unnamed Item, On the anti-Kekulé problem of cubic graphs, Approximating the smallest 2-vertex connected spanning subgraph of a directed graph, Paths and Trails in Edge-Colored Graphs, A simple approximation algorithm for the weighted matching problem, A genetic-based framework for solving (multi-criteria) weighted matching problems., Efficient Matching for Column Intersection Graphs, Edges and switches, tunnels and bridges, Approximating edge dominating set in dense graphs, Exact and approximation algorithms for weighted matroid intersection, Approximate minimum weight matching on points in k-dimensional space, The Power of Linear-Time Data Reduction for Maximum Matching, Recomputing causality assignments on lumped process models when adding new simplification assumptions, Paths and trails in edge-colored weighted graphs, Fully Dynamic Maximal Matching in $O(\log n)$ Update Time, Output sensitive fault tolerant maximum matching, Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths, Unnamed Item, Unnamed Item, Unnamed Item, Fast and Simple Algorithms for Weighted Perfect Matching, Strong cliques and equistability of EPT graphs, Fast algorithms for the undirected negative cost cycle detection problem
