A linear-time approximation algorithm for weighted matchings in graphs
From MaRDI portal
Publication:2944492
DOI10.1145/1077464.1077472zbMath1321.05279OpenAlexW2028468530MaRDI QIDQ2944492
Doratha E. Vinkemeier, Stefan Hougardy
Publication date: 2 September 2015
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1077464.1077472
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)
Related Items
Approximating weighted matchings in parallel ⋮ Approximating the Metric TSP in Linear Time ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ Adaptive AMG with coarsening based on compatible weighted matching ⋮ Solving maximum weighted matching on large graphs with deep reinforcement learning ⋮ Weighted matching in the semi-streaming model ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems ⋮ Approximating the metric TSP in linear time ⋮ A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs ⋮ Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding ⋮ Efficient sub-5 approximations for minimum dominating sets in unit disk graphs ⋮ On two-machine flow shop scheduling ⋮ Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem ⋮ Unnamed Item ⋮ Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs ⋮ Relaxing the irrevocability requirement for online graph algorithms ⋮ Approximation algorithms in combinatorial scientific computing
