Exact perfect matching in complete graphs

DOI10.1145/3041402MaRDI QIDQ4973885zbMATH OpenOpenAlexWikidataFDO

Authors Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf

Publication date 6 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3041402

zbMATH Keywords

complete graphscomputational complexityexact perfect matchingperfect matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• Almost Exact Matchings
• Almost exact matchings
• Bicolored matchings in some classes of graphs
• The labeled perfect matching in bipartite graphs
• Matchings in colored bipartite networks

Cited in

(14)

• Perfect matching for regular graphs is AC^ 0-hard for the general matching problem
• Perfect matchings of cellular graphs
• Perfect matchings after vertex deletions
• Almost Exact Matchings
• Bipartite perfect matching is in quasi-NC
• Popular Matchings in Complete Graphs
• A weighted perfect matching with constraints on weights of its parts
• The ultimate categorical matching in a graph
• Polyhedral techniques in combinatorial optimization: matchings and tours
• Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs
• Partitioned matching games for international kidney exchange
• On the exact matching problem in dense graphs
• Exact matching: correct parity and FPT parameterized by independence number
• Killing a vortex

This page was built for publication: Exact perfect matching in complete graphs

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