Beyond Max-Cut: 位-extendible properties parameterized above the Poljak-Turz铆k bound
详细信息 查看全文
- 作者：Matthias Mnicha ; m.mnich@mmci.uni-saarland.de" class="auth_mail ; Geevarghese Philipb ; 1 ; gphilip@mpi-inf.mpg.de" class="auth_mail ; Saket Saurabhc ; 2 ; saket@imsc.res.in" class="auth_mail ; Ond艡ej Suchý ; d ; 3 ; ondrej.suchy@fit.cvut.cz" class="auth_mail
- 关键词：Algorithms and data structures ; Fixed-parameter tractable algorithms ; Above-guarantee parameterization ; Max-Cut ; 位-extendible properties
- 刊名：Journal of Computer and System Sciences
- 出版年：November 2014
- 年：2014
- 卷：80
- 期：7
- 页码：1384-1403
- 全文大小：492 K
文摘
- •
We derive fixed-parameter algorithms for a generalization of above-guarantee Max-Cut.
- •
The generalization also captures properties of oriented/edge-labelled graphs.
- •
Our results build on and generalize the work of Crowston et al. (ICALP 2012) on Max-Cut.
- •
As a corollary we solve an open question of Raman and Saurabh (Theor. Comput. Sci. 2006).