Almost exact matchings

DOI10.1007/S00453-011-9519-0MaRDI QIDQ2429356zbMATH OpenOpenAlexFDO

Authors Raphael Yuster

Publication date 26 April 2012

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-011-9519-0

zbMATH Keywords

matchingapproximationexact matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Almost Exact Matchings
• scientific article; zbMATH DE number 795216
• scientific article; zbMATH DE number 6863588
• Tight bound for matching
• On compatible matchings
• On Compatible Matchings
• Overlap matching
• scientific article; zbMATH DE number 6863589
• Approximating Matches Made in Heaven
• Algorithms – ESA 2004

Cites work

• scientific article; zbMATH DE number 3517179 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• A Separator Theorem for Nonplanar Graphs
• A Separator Theorem for Planar Graphs
• An approach to the subgraph homeomorphism problem
• Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle
• Constructing a perfect matching is in random NC
• Dividing a Graph into Triconnected Components
• Faster scaling algorithms for general graph matching problems
• Generalized Nested Dissection
• Matching is as easy as matrix inversion
• Matrix multiplication via arithmetic progressions
• Maximum matching in graphs with an excluded minor
• Maximum matchings in planar graphs via Gaussian elimination
• NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
• Nested Dissection of a Regular Finite Element Mesh
• On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
• The Factorization of Linear Graphs
• The analysis of a nested dissection algorithm
• The complexity of restricted spanning tree problems

Cited in

(14)

• Exact perfect matching in complete graphs
• Exact arborescences, matchings and cycles
• Optimization problems with color-induced budget constraints
• Almost similar configurations
• Integrality gaps for colorful matchings
• Overlap matching
• Bi-criteria and approximation algorithms for restricted matchings
• The precise complexity of finding rainbow even matchings
• Randomized and Approximation Algorithms for Blue-Red Matching
• Almost Exact Matchings
• Optimization problems with color-induced budget constraints
• Polyhedral techniques in combinatorial optimization: matchings and tours
• Almost semi-correspondence
• Maximum matching in graphs with an excluded minor

This page was built for publication: Almost exact matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429356)