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 ak-partition for ak-connected graphG=(V, E), wherek is the vertex connectivity ofG. In this paper, anO(k 2n2) general algorithm of finding ak-partition for ak-connected graph is proposed, wheren=|V|.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
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.
Dyer M E, Frieze A M. On the complexity of partitioning graphs into connected subgraphs. Discrete Appl Math, 1985, 10: 139–153.
Gyôri E. On division of graph to connected subgraphs, combinatorics. In: Proc Fifth Hungarian Combinatorial Coll, Keszthely, Bolyai: North-Holland, 1978, 485–494.
Lovász L. A homology theory for spanning trees of a graph. Acta Math Acad, 1977, 30: 241–251.
Hitoshi S, Naomi T, Takao N, Hiroshi M, Shuichi U. An algorithm for tripartitioning 3-connected graphs(in Japanese). J. of Information Processing, 1990, 30(5): 584–592.
Swamy N N S, Thulasiraman K. Graphs, networks and algorithms. John Wiley & Sons Inc, 1981, 143.
Even S. The max flow algorithm of Dinic and Karzanov, an exposition. MIT/LCS/TM-80, 1976.
Nagamochi H, Ibaraki T. A linear-time algorithm for finding a Sparsek-connected spanning subgraph of ak-connected graph. Algorithmica, 1992, 7: 583–596.
Author information
Authors and Affiliations
Additional information
The research was supported by National Natural Science Foundation of China.
Rights and permissions
About this article
Cite this article
Ma, J., Ma, S. AnO(k 2n2) algorithm to find ak-partition in ak-connected graph. J. of Compt. Sci. & Technol. 9, 86–91 (1994). https://doi.org/10.1007/BF02939489
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02939489