The bridge-connectivity augmentation problem with a partition constraint. (English) Zbl 1192.68477
Summary: We consider the augmentation problem of an undirected graph with \(k\) partitions of its vertices. The main issue is how to add a set of edges with the smallest possible cardinality so that the resulting graph is 2-edge-connected, i.e., bridge-connected, while maintaining the original partition constraint. To solve the problem, we propose a simple linear-time algorithm. To the best of our knowledge, the most efficient sequential algorithm runs in \(O(n(m+n \log n) \log n)\) time. However, we show that it can also run in \(O(\log n)\) parallel time on an EREW PRAM using a linear number of processors, where \(n\) is the number of vertices in the input graph. If a simple graph exists, our main algorithm ensures that it is as simple as possible.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Frank, A., Connectivity augmentation problems in network design, (Birge, J.; Murty, K., Mathematical Programming: State of the Art 1994 (1994), The University of Michigan), 34-63 |
| [2] | T.-s. Hsu, Graph augmentation and related problems: theory and practice, Ph.D. thesis, University of Texas at Austin, TX, USA, 1993.; T.-s. Hsu, Graph augmentation and related problems: theory and practice, Ph.D. thesis, University of Texas at Austin, TX, USA, 1993. |
| [3] | Nagamochi, H., Recent development of graph connectivity augmentation algorithms, IEICE Transactions on Information and Systems, 83, 3, 372-383 (2000) |
| [4] | Hsu, T.-s.; Kao, M.-Y., Optimal augmentation for bipartite componentwise biconnectivity in linear time, SIAM Journal on Discrete Mathematics, 19, 2, 345-362 (2005) · Zbl 1092.68076 |
| [5] | Bang-Jensen, J.; Gabow, H. N.; Jordán, T., Edge-connectivity augmentation with partition constraints, SIAM Journal on Discrete Mathematics, 12, 2, 160-207 (1999) · Zbl 0922.05034 |
| [6] | Kao, M.-Y., Linear-time optimal augmentation for componentwise bipartite-completeness of graphs, Information Processing Letters, 54, 1, 59-63 (1995) · Zbl 1004.68534 |
| [7] | Adam, N. R.; Worthmann, J. C., Security-control methods for statistical databases: a comparative study, ACM Computing Surveys, 21, 4, 515-556 (1989) |
| [8] | Chin, F. Y.; Ozsoyoglu, G., Auditing and inference control in statistical databases, IEEE Transactions Software Engineering, 8, 6, 574-582 (1982) · Zbl 0491.68102 |
| [9] | Cox, L. H., Suppression methodology and statistical disclosure control, Journal of the American Statistical Association, 75, 370, 377-385 (1980) · Zbl 0462.62087 |
| [10] | Denning, D. E.; Schlörer, J., Inference controls for statistical databases, IEEE Computer, 16, 69-82 (1983) |
| [11] | Kelly, B. L.G. J.P.; Assad, A. A., Cell suppression: disclosure protection for sensitive tabular data, Networks, 22, 4, 397-417 (1992) · Zbl 0825.90663 |
| [12] | Gusfield, D., A graph theoretic approach to statistical data security, SIAM Journal on Computing, 17, 3, 552-571 (1988) · Zbl 0653.90039 |
| [13] | Kao, M.-Y., Data security equals graph connectivity, SIAM Journal on Discrete Mathematics, 9, 1, 87-100 (1996) · Zbl 0841.68056 |
| [14] | Kao, M.-Y., Total protection of analytic-invariant information in cross-tabulated tables, SIAM Journal on Computing, 26, 1, 231-242 (1997) · Zbl 0870.68080 |
| [15] | Eswaran, K.; Tarjan, R., Augmentation problems, SIAM Journal on Computing, 5, 653-665 (1976) · Zbl 0346.05112 |
| [16] | Hsu, T.-s., Simpler and faster biconnectivity augmentation, Journal of Algorithms, 45, 1, 55-71 (2002) · Zbl 1030.68065 |
| [17] | Rosenthal, A.; Goldner, A., Smallest augmentations to biconnect a graph, SIAM Journal on Computing, 6, 55-66 (1977) · Zbl 0352.05048 |
| [18] | Watanabe, T.; Nakamura, A., A minimum 3-connectivity augmentation of a graph, Journal of Computer and System Science, 46, 1, 91-128 (1993) · Zbl 0768.68188 |
| [19] | Hsu, T.-s., On four-connecting a triconnected graph, Journal of Algorithm 35, 2, 202-234 (2000) · Zbl 0951.68114 |
| [20] | Huang, P.-C.; Wei, H.-W.; Lu, W.-C.; Shih, W.-K.; Hsu, T.-s., Smallest bipartite bridge-connectivity augmentation, Algorithmica, 54, 3, 353-378 (2009) · Zbl 1187.68345 |
| [21] | F. Harary, Graph Theory, in: Addison-Wesley Series in Mathematics, Reading, 1969.; F. Harary, Graph Theory, in: Addison-Wesley Series in Mathematics, Reading, 1969. · Zbl 0182.57702 |
| [22] | Chong, K.; Han, Y.; Lam, T., Concurrent threads and optimal parallel minimum spanning trees algorithm, Journal of the ACM, 48, 2, 297-323 (2001) · Zbl 1089.68665 |
| [23] | Cole, R.; Vishkin, U., Approximate parallel scheduling. Part II: Applications to logarithmic-time optimal graph algorithms, Information and Computation, 92, 1, 1-47 (1991) · Zbl 0724.68012 |
| [24] | Ramachandran, V., Parallel open ear decomposition with applications to graph biconnectivity and triconnectivity, (Reif, J., Synthesis of Parallel Algorithms (1993), Morgan-Kaufmann), 275-340 |
| [25] | Tarjan, R. E., Depth-first search and linear graph algorithms, SIAM Journal on Computing, 1, 146-160 (1972) · Zbl 0251.05107 |
| [26] | Tarjan, R.; Vishkin, U., An efficient parallel biconnectivity algorithm, SIAM Journal on Computing, 14, 4, 862-874 (1985) · Zbl 0575.68066 |
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.
