Exact Perfect Matching in Complete Graphs
| Autor: | Rohit Gurjar, Thomas Thierauf, Jochen Messner, Arpita Korwar |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Factor-critical graph
Discrete mathematics Strong perfect graph theorem Astrophysics::Cosmology and Extragalactic Astrophysics 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics Trivially perfect graph Perfect graph 3-dimensional matching 0202 electrical engineering electronic engineering information engineering Bipartite graph Astrophysics::Solar and Stellar Astrophysics Perfect graph theorem 020201 artificial intelligence & image processing Cograph Astrophysics::Galaxy Astrophysics MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | ACM Transactions on Computation Theory. 9:1-20 |
| ISSN: | 1942-3462 1942-3454 |
| DOI: | 10.1145/3041402 |
| Popis: | A red-blue graph is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges. We show that for complete and bipartite complete graphs, the exact perfect matching problem is logspace equivalent to the perfect matching problem. Hence, an efficient parallel algorithm for perfect matching would carry over to the exact perfect matching problem for this class of graphs. We also report some progress in extending the result to arbitrary graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|