×

A linear algorithm for bipartition of biconnected graphs. (English) Zbl 0696.68074

Summary: This paper presents a linear algorithm for partitioning a biconnected graph into a pair of disjoint connected subgraphs, each of which contains a specified vertex and has a specified number of vertices.

MSC:

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
68W99 Algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dyer, M. E.; Frieze, A. M., On the complexity of partitioning graph into connected subgraphs, Discrete Appl. Math., 10, 139-153 (1985) · Zbl 0562.68030
[2] Györi, E., On division of connected subgraphs, (Combinatorics. Combinatorics, Proc. 5th Hungarian Combinatorial Coll., 1976, Keszthely (1978), North-Holland: North-Holland Amsterdam), 485-494
[3] Imase, M.; Manabe, Y., Fault tolerant routings in a \(k\)-connected network, Tech. Rept. Inst. Elect. Commun. Eng. Japan, 95-105 (1987), COMP86-70
[4] Lovász, L., A homology theory for spanning trees of a graph, Acta math. Acad. Sci. Hunger., 30, 241-251 (1977) · Zbl 0403.05040
[5] Suzuki, H.; Takahashi, N.; Nishizeki, T.; Miyano, H.; Ueno, S., An algorithm for tripartitioning 3-connected graphs, Tech. Rept. Inf. Proc. Soc. Japan (1989), AL5-11
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.