Approximating max-cut under graph-MSO constraints
2018
Abstract We consider the max-cut and max- k -cut problems under graph-based constraints. Our approach can handle any constraint specified using monadic second-order (MSO) logic on graphs of constant treewidth. We give a 1 2 -approximation algorithm for this class of problems.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
18
References
1
Citations
NaN
KQI