𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Perfect matching for regular graphs is AC0-hard for the general matching problem

✍ Scribed by Elias Dahlhaus; Marek Karpinski

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
491 KB
Volume
44
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The complexity of the matching-cut probl
The complexity of the matching-cut problem for planar graphs and other graph classes
✍ Paul Bonsma 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB

## Abstract The Matching‐Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be ${\cal{NP}}$‐complete when restricted to graphs with maximum deg