We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 9 Issue 1
January  1994
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Ma Jun, Ma Shaohan. An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph[J]. Journal of Computer Science and Technology, 1994, 9(1): 86-91.
Citation: Ma Jun, Ma Shaohan. An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph[J]. Journal of Computer Science and Technology, 1994, 9(1): 86-91.
shu

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

  • Department of Computer Science; Shandong University; Jinan 250100;

More Information
  • Published Date: January 09, 1994
    Abstract
  • 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|.
    • FullText(HTML)
    • References (3)
  • [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. ……….
    • Relative Articles

  • Related Articles

    [1]wang Zhenyu. ρ Graph: Rendezvous Ordering Graph forAda Concurrent Programs[J]. Journal of Computer Science and Technology, 1998, 13(6): 615-622.
    [2]Xue Jinyun. Formal Derivation of Graph AlgorithmicPrograms Using Partition-and-Recur[J]. Journal of Computer Science and Technology, 1998, 13(6): 553-561.
    [3]Fu Yuxi. Reaction Graph[J]. Journal of Computer Science and Technology, 1998, 13(6): 510-530.
    [4]Shen Enshao. Some Notes on Graph Automata, TilingSystems and Partition Logic[J]. Journal of Computer Science and Technology, 1998, 13(6): 483-489.
    [5]Chen Yangjun. Graph Traversal and Top-Down Evaluation of Logic Queries[J]. Journal of Computer Science and Technology, 1998, 13(4): 300-316.
    [6]Ma Jun, Ma Shaohan. Efficient Parallel Algorithms for Some Graph Theory Problems[J]. Journal of Computer Science and Technology, 1993, 8(4): 76-80.
    [7]Li Tianzhu. A Study of Optimization and Rule/Goal Graph for a Logical Query[J]. Journal of Computer Science and Technology, 1992, 7(4): 356-362.
    [8]Chen Fang, Shi Baile. A Conservative Multiversion Locking-Graph Scheduler Algorithm[J]. Journal of Computer Science and Technology, 1991, 6(2): 161-166.
    [9]Wang Dingxing, Zheng Weimin, Du Xiaoli, Guo Yike. On the Execution Mechanisms of Parallel Graph Reduction[J]. Journal of Computer Science and Technology, 1990, 5(4): 333-346.
    [10]Li Hao, Liu Qun. A Problem of Tree Graph[J]. Journal of Computer Science and Technology, 1989, 4(1): 61-66.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (36) PDF downloads (1274) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return