• Articles • Previous Articles     Next Articles

An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph

Ma Jun; Ma Shaohan;   

  1. Department of Computer Science; Shandong University; Jinan 250100;
  • Online:1994-01-10 Published:1994-01-10

Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively, there is no general algorithm of finding a k-partition for a k-connected graph G = (V, E), where k is the vertex connectivity of G. In this paper, an O(k2n2) general algorithm of finding a k-partition for a k-connected graph is proposed, where n = |V|.

Key words: data-flow analysis; interprocedural analysis and optimization; automatic generator;



[1] Manabe I. Building networks with some fixed routing and the ability to resist some obstacles. Electronic Information Communication Research Materials (in Japanese), COMP 86-70, 1987:95-105.

[2] Dyer.M.E, Frieze.A.M. On the complexity of partitioning graphs into connected subgraphs. Discrete Appl Math, 1985, 10: 139-153.

[3] Gyori E. On division of graph to connected subgraphs, combinatorics. In:Proc Fifth Hungarian Combinatorial Coll, Keszthely, Bolyai: North-Holland, 1978, 485-494. ……….
[1] SHAN JinHui (单锦辉), WANG Ji (王 戟), QI ZhiChang (齐治昌) and WU JianPing (吴建平). Improved Method to Generate Path-Wise Test Data [J]. , 2003, 18(2): 0-0.
[2] LIAN Ruiqi (连瑞琦), ZHANG Zhaoqing (张兆庆) and QIAO Ruliang (乔如良). Automatic Generation of Interprocedural Data-Flow Analyzers and Optimizers [J]. , 2002, 17(6): 0-0.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[10] Qiao Xiangzhen;. An Efficient Parallel Algorithm for FFT[J]. , 1987, 2(3): 174 -190 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved