加载中…
2012-08-28
Hitting all Maximal Independent Sets of a Bipartite Graph
Jean CardinalGwenaël Joret
文献摘要
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 k hitting all maximal independent sets of G is complete for the class Sigma_2^P.
讨论
0讲解博客
生成讲解博客的中文版本
AI智能校验
生成AI智能校验的中文版本