| K连通图的k分割多项式算法 |
| |
| 引用本文： | 马军,马绍汉. K连通图的k分割多项式算法[J]. 山东大学学报(理学版), 1993, 0(1) |
| |
| 作者姓名： | 马军 马绍汉 |
| |
| 作者单位： | 山东大学计算机科学系，山东大学计算机科学系 |
| |
| 摘 要： | 图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分割多项式算法.
|
| 关 键 词： | 图的k分割 图的顶点连通度 图算法 |
A POLYNOMIAL ALGORITHM OF FINDING A K PARTITION FOR AN UNDIRECTED SIMPLE k CONNECTED GRAPH |
| |
| Ma Jun,Ma Shaohan Dept. of Computer Science,Shandong Unic.,Jinan. A POLYNOMIAL ALGORITHM OF FINDING A K PARTITION FOR AN UNDIRECTED SIMPLE k CONNECTED GRAPH[J]. Journal of Shandong University, 1993, 0(1) |
| |
| Authors: | Ma Jun Ma Shaohan Dept. of Computer Science Shandong Unic. Jinan |
| |
| Abstract: | |
| |
| Keywords: | k division of graph graph vertax connectivity graph algorithms |
| 本文献已被 CNKI 等数据库收录！ |
|
