Arboricity and bipartite subgraph listing algorithms. (English) Zbl 0813.68115
Summary: In graphs of bounded arboricity, the total complexity of all maximal complete bipartite subgraphs is \(O(n)\). We described a linear time algorithm to list such subgraphs. The arboricity bound is necessary: for any constant \(k\) and any \(n\) there exists an \(n\)-vertex graph with \(O(n)\) edges and \((n/\log n)^ k\) maximal complete bipartite subgraphs \(K_{k,l}\).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Agarwal, P.; Alon, N.; Aronov, B.; Suri, S., Can visibility graphs be represented compactly?, Proc. 9th ACM Symp. on Computational Geometry, 338-347 (1993) · Zbl 0819.68134 |
| [2] | Artymiuk, P. J.; Bath, P. A.; Grindley, H. M.; Pepperrell, C. A.; Poirrette, A. R.; Rice, D. W.; Thorner, D. A.; Wild, D. J.; Willett, P.; Allen, F. H.; Taylor, T., Similarity searching in databases of three-dimensional molecules and macromolecules, J. Chemical Inform. Comput. Sci., 32, 617-630 (1992) |
| [3] | Bern, M.; Eppstein, D., Mesh generation and optimal triangulation, (Hwang, F. K.; Du, D. Z., Computing in Euclidean Geometry (1992), World Scientific: World Scientific Singapore), 23-90 |
| [4] | Booth, K. S.; Lueker, G. S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13, 335-379 (1976) · Zbl 0367.68034 |
| [5] | Brown, A. D.; Thomas, P. R., Goal-oriented subgraph isomorphism technique for IC device recognition, IEE Proc. I (Solid-State and Electron Devices), 135, 141-150 (1988) |
| [6] | Chiba, N.; Nishizeki, T., Arboricity and subgraph listing algorithms, SIAM J. Comput., 14, 210-223 (1985) · Zbl 0572.68053 |
| [7] | Chrobak, M.; Eppstein, D., Planar orientations with low out-degree and compaction of adjacency matrices, Theoret. Comput. Sci., 86, 243-266 (1991) · Zbl 0735.68015 |
| [8] | Dillencourt, M. B.; Smith, W. D., A linear-time algorithm for testing the inscribability of trivalent polhedra, Proc. 8th ACM Symp. on Computational Geometry, 177-185 (1992) |
| [9] | Eppstein, D., Connectivity, graph minors, and subgraph multiplicity, J. Graph Theory, 17, 409-416 (1993) · Zbl 0781.05029 |
| [10] | Gabow, H. N.; Westermann, H. H., Foreses, frames. and games: algorithms for matroid sums and applications, Proc. 20th ACM Symp. on Theory of Computing, 407-421 (1988) |
| [11] | Guha, A., Optimizing codes or concurrent fault-detection in micro-programmed controllers, Proc. IEEE Internat. Conf. Computer Design: VLSI in Computers and Processors (ICCD ’87), 486-489 (1987) |
| [12] | Dong, Hong; Wu, Youshou; Ding, Xiaoqiag, An ARG representation for Chinese characters and a radical extraction based on the representation, Proc. 9th IEEE Internat. Conf. on Pattern Recognition, Vol. 2, 920-922 (1988) |
| [13] | Lang, S. Y.T.; Woag, A. K.C., A sensor model registration technique for mobile robot localization, Proc. 1991 IEEE Internat. Symp. on Intelligent Control, 298-305 (1991) |
| [14] | Levinson, R., Pattern associativity and the retrieval of semantic networks, Comput. Math. Appl., 23, 573-600 (1992) · Zbl 0800.68878 |
| [15] | Miller, G. L.; Teng, S.-H.; Vavasis, S. A., A unified geometric approach to graph separators, Proc. 32nd IEEE Symp. on Foundations of Computer Science, 538-547 (1991) |
| [16] | Nash-Williams, C. St. J., Edge-disjoint spanning trees of finite graphs, J. London Math. Soc., 36, 445-450 (1961) · Zbl 0102.38805 |
| [17] | Rose, D. J.; Tarjan, R. E.; Lueker, G. S., Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 266-283 (1976) · Zbl 0353.65019 |
| [18] | Schnyder, W., Embedding planar graphs on the grid, Proc. 1st ACM - SIAM Symp. on Discrete Algorithms, 138-148 (1990) · Zbl 0786.05029 |
| [19] | Stahs, T.; Wahl, F., Recognition of polyhedral objects under perspective views, Comput. Artificial Intelligence, 11, 155-172 (1992) · Zbl 0751.68080 |
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.
