|
|||||
|
|
Approximating max-cut under graph-MSO constraints |
|
| Authors: | Martin Koutecký Jon Lee Viswanath Nagarajan Xiangkun Shen |
| Affiliation: | 1. Faculty of IE&M, Technion, Haifa, Israel;2. Computer Science Institute, Charles University, Prague, Czech Republic;3. IOE Department, University of Michigan, Ann Arbor, MI 48109, USA |
| Abstract: | We consider the max-cut and max--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 -approximation algorithm for this class of problems. |
| Keywords: | Max cut Approximation algorithm Monadic second-order logic Treewidth Dynamic program |
| 本文献已被 ScienceDirect 等数据库收录！ | |