Almost exact matchings
From MaRDI portal
Publication:2429356
DOI10.1007/s00453-011-9519-0zbMath1236.68107OpenAlexW2174697474MaRDI QIDQ2429356
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
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (5)
Optimization problems with color-induced budget constraints ⋮ Integrality gaps for colorful matchings ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ Bi-criteria and approximation algorithms for restricted matchings ⋮ Optimization Problems with Color-Induced Budget Constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- An approach to the subgraph homeomorphism problem
- Matching is as easy as matrix inversion
- The analysis of a nested dissection algorithm
- Constructing a perfect matching is in random NC
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
- Maximum matchings in planar graphs via Gaussian elimination
- Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle
- A Separator Theorem for Planar Graphs
- Generalized Nested Dissection
- The complexity of restricted spanning tree problems
- A Separator Theorem for Nonplanar Graphs
- Faster scaling algorithms for general graph matching problems
- Dividing a Graph into Triconnected Components
- Nested Dissection of a Regular Finite Element Mesh
- The Factorization of Linear Graphs
This page was built for publication: Almost exact matchings
