Approximating max-cut under graph-MSO constraints
| Autor: | Xiangkun Shen, Martin Koutecký, Jon Lee, Viswanath Nagarajan |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Applied Mathematics
Maximum cut Approximation algorithm 0102 computer and information sciences 010501 environmental sciences Management Science and Operations Research 01 natural sciences Industrial and Manufacturing Engineering Graph Treewidth Combinatorics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES 010201 computation theory & mathematics Computer Science::Logic in Computer Science Software MathematicsofComputing_DISCRETEMATHEMATICS 0105 earth and related environmental sciences Mathematics |
| Zdroj: | Operations Research Letters. 46:592-598 |
| ISSN: | 0167-6377 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect