标题:K连通图的k分割多项式算法
作者:马军;马绍汉;
作者机构:[马军;马绍汉] 山东大学计算机科学系,山东大学计算机科学系,
来源:山东大学学报(自然科学版)
出版年:1993
期:01
页码:45-51
关键词:图的k分割;图的顶点连通度;图算法
摘要:图G的K分割问题可描述为:输入(Ⅰ)G=(V,E),G为简单无向图,其中|V|=n,|E|= m;(Ⅱ)a_1,a_2,…,a_k k个G中不同的顶点;(Ⅲ)n_1,n_2,…,n_k k个正整数满足 n_1+n_2+…,+n_k= n.输出(V_1,V_2,…,V_k),对1≤i≤k,满足(Ⅰ)a_i∈V_i;(Ⅱ)G[V_i]是连通图;(Ⅲ)|V_i|=n_i.本文给出时间复杂性为O(knm)通用K连通图的k分割多项式算法.
资源类型:期刊论文
原文链接:http://kns.cnki.net/kns/detail/detail.aspx?FileName=SDDX199301008&DbName=CJFQ1993
TOP