Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
复制标题
用于识别单极图和 2 次着色图的参数化算法
DOI：
10.1016/j.jcss.2017.08.002
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
und E. J. van Leeuwen
中科院分区：
文献类型：
--
作者：
I. A. Kanj;C. Komusiewicz;M. Sorge;und E. J. van Leeuwen
一个图G是一个（A，B）-图，如果V（G）可以被二分划成A和B，使得G [A]满足性质A，G [B]满足性质B.（A，B B）-识别问题是识别一个给定的图是否是（A，B B）-图。有许多（图A，图B）-识别问题，包括二部图，分裂图和单极图的识别问题。我们提出了有效的算法，许多情况下（A，B B）-识别的基础上的技术，我们杜B归纳识别。特别地，我们给出了两个NP-难的（NP-A，NP-B）-识别问题，单极识别和2-子着色的固定参数算法，参数化的最大团的数量在G [A]。我们补充我们的算法结果与几个硬度的结果（A，B B）-识别。
A graph G is a (Π A, Π B)-graph if V (G) can be bipartitioned into A and B such that G [A] satisfies property Π A and G [B] satisfies property Π B. The (Π A, Π B)-Recognition problem is to recognize whether a given graph is a (Π A, Π B)-graph. There are many (Π A, Π B)-Recognition problems, including the recognition problems for bipartite, split, and unipolar graphs. We present efficient algorithms for many cases of (Π A, Π B)-Recognition based on a technique which we dub inductive recognition. In particular, we give fixed-parameter algorithms for two NP-hard (Π A, Π B)-Recognition problems, Monopolar Recognition and 2-Subcoloring, parameterized by the number of maximal cliques in G [A]. We complement our algorithmic results with several hardness results for (Π A, Π B)-Recognition.
登录
查看更多内容
DOI：
10.1016/j.disc.2011.08.022
发表时间：
2012
期刊：
Discret. Math.
影响因子：
--
作者：
Ross Churchley;Jing Huang
通讯作者：
Jing Huang
DOI：
10.1016/j.dam.2008.01.026
发表时间：
2008
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
T. Ekim;P. Hell;J. Stacho;D. Werra
通讯作者：
D. Werra
与图3可着色性相关的一些问题的复杂性
DOI：
10.1016/s0166-218x(98)00116-4
发表时间：
1998
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
A. Brandstädt;V. B. Le;T. Szymczak
通讯作者：
T. Szymczak
图的子着色：复杂性和算法
影响因子：
2.3
作者：
J. Fiala;K. Jansen;V. B. Le;Eike Seidel
通讯作者：
Eike Seidel
有关底色的更多信息
影响因子：
3.7
作者：
H. Broersma;F. Fomin;J. Nesetril;G. Woeginger
通讯作者：
G. Woeginger