Beyond Max-Cut: λ-extendible properties parameterized above the Poljak–Turzík bound
作者：
Highlights：
• 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).
摘要
•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).
论文关键词：Algorithms and data structures,Fixed-parameter tractable algorithms,Above-guarantee parameterization,Max-Cut,λ-extendible properties
论文评审过程：Received 14 May 2013, Revised 18 February 2014, Accepted 4 April 2014, Available online 18 April 2014.
论文官网地址：https://doi.org/10.1016/j.jcss.2014.04.011
