论文部分内容阅读
图G的K分割问题可描述为:输入（Ⅰ）G=（V,E）,G为简单无向图,其中|V|=n,|E|= m;（Ⅱ）a1,a2,…,ak k个G中不同的顶点;（Ⅲ）n1,n2,…,nk k个正整数满足 n1+n2+…,+nk= n.输出（V1,V2,…,Vk）,对1≤i≤k,满足（Ⅰ）ai∈Vi;（Ⅱ）G[Vi]是连通图;（Ⅲ）|Vi|=ni.本文给出时间复杂性为O（knm）通用K连通图的k分割多项式算法.