𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of finding uniform sparsest cuts in various graph classes

✍ Scribed by Paul Bonsma; Hajo Broersma; Viresh Patel; Artem Pyatkin

Book ID
113699078
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
293 KB
Volume
14
Category
Article
ISSN
1570-8667

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