Hitting All Maximal Independent Sets of a Bipartite Graph

被引:0
作者
Jean Cardinal
Gwenaël Joret
机构
[1] Université Libre de Bruxelles,Département d’Informatique
来源
Algorithmica | 2015年 / 72卷
关键词
Maximal independent set; Clique transversal; Fibre in posets;
D O I
暂无
中图分类号
学科分类号
摘要
We prove that given a bipartite graph G with vertex set V and an integer k, deciding whether there exists a subset of V of size at most k hitting all maximal independent sets of G is complete for the class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\varSigma_{2}^{\mathrm{P}}$\end{document}.
引用
收藏
页码:359 / 368
页数:9
相关论文
共 40 条
[1]  
Andreae T.(1998)On the clique-transversal number of chordal graphs Discrete Math. 191 3-11
[2]  
Andreae T.(1991)Clique-transversal sets of line graphs and complements of line graphs Discrete Math. 88 11-20
[3]  
Schughart M.(2004)Coloring the maximal cliques of graphs SIAM J. Discrete Math. 17 361-376
[4]  
Tuza Z.(1996)Clique transversal and clique independence on comparability graphs Inf. Process. Lett. 58 181-184
[5]  
Bacsó G.(1991)Fibres and ordered set coloring J. Comb. Theory, Ser. A 58 158-164
[6]  
Gravier S.(1991)Two-colouring all two-element maximal antichains J. Comb. Theory, Ser. A 57 109-116
[7]  
Gyárfás A.(2008)Algorithms for finding clique-transversals of graphs Ann. Oper. Res. 157 37-45
[8]  
Preissmann M.(2002)On clique-transversals and clique-independent sets Ann. Oper. Res. 116 71-77
[9]  
Sebö A.(1992)Covering the cliques of a graph with vertices Discrete Math. 108 279-289
[10]  
Balachandran V.(1978)Complexity of automaton identification from given data Inf. Control 37 302-320