Efficiently covering complex networks with cliques of similar vertices. (English) Zbl 1088.68013
Summary: We describe a polynomial time algorithm for covering graphs with cliques, prove its asymptotic optimality in a random intersection graph model and present experimental results on complex real-world networks.
MSC:
| 68M10 | Network design and communication in computer systems |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
Software:
COSMOSReferences:
| [1] | R. Albert, H. Jeong, A.-L. Barabási, Database of self-organized networks, \( \langle;\) http://www.nd.edu/\( \sim;\rangle;\); R. Albert, H. Jeong, A.-L. Barabási, Database of self-organized networks, \( \langle;\) http://www.nd.edu/\( \sim;\rangle;\) |
| [2] | M. Behrisch, Component evolution in random intersection graphs, November 2004, preprint.; M. Behrisch, Component evolution in random intersection graphs, November 2004, preprint. · Zbl 1114.05093 |
| [3] | Fill, J. A.; Scheinerman, E. R.; Singer-Cohen, K. B., Random intersection graphs when \(m = \omega(n)\): an equivalence theorem relating the evolution of the \(G(n, m, p)\) and \(G(n, p)\) models, Random Struct. Algorithms, 16, 2, 156-176 (2000) · Zbl 0951.05096 |
| [4] | Frömmel, C.; Gille, C.; Goede, A.; Gröpl, C.; Preissner, R.; Hougardy, S.; Nierhoff, T.; Thimm, M., Accelerating screening of 3D protein data with a graph theoretical approach, Bioinformatics, 19, 18, 2442-2447 (2003) |
| [5] | Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0411.68039 |
| [6] | E. Godehardt, J. Jaworski, Two models of random intersection graphs and their applications, Electronic Notes in Discrete Mathematics, Vol. 10, URL: \( \langle;\) http://www1.elsevier.com/gej-ng/31/29/24/49/27/61/endm10036.ps \(\rangle;\); E. Godehardt, J. Jaworski, Two models of random intersection graphs and their applications, Electronic Notes in Discrete Mathematics, Vol. 10, URL: \( \langle;\) http://www1.elsevier.com/gej-ng/31/29/24/49/27/61/endm10036.ps \(\rangle;\) · Zbl 1182.05108 |
| [7] | Goede, A.; Preissner, R.; Hougardy, S.; Thimm, M., Comparison of 2D similarity and 3D superposition. application to searching a conformational drug database, J. Chem. Inform. Comput. Sci., 44, 1816-1822 (2004) |
| [8] | R. Govindan, H. Tangmunarunkit, \( \operatorname{SCAN} + \operatorname{Lucent}\langle;\) http://www.isi.edu/div7/scan/mercator/maps.html \(\rangle;\); R. Govindan, H. Tangmunarunkit, \( \operatorname{SCAN} + \operatorname{Lucent}\langle;\) http://www.isi.edu/div7/scan/mercator/maps.html \(\rangle;\) |
| [9] | Guillaume, J.-L.; Latapy, M., Bipartite structure of all complex networks, Inform. Process. Lett., 90, 215-221 (2004) · Zbl 1178.68031 |
| [10] | Janson, S.; Łuczak, T.; Ruciński, A., Random Graphs (2000), Wiley: Wiley New York · Zbl 0968.05003 |
| [11] | Karoński, M.; Scheinerman, E. R.; Singer-Cohen, K. B., On random intersection graphs: the subgraph problem, Combinatorics, Probab. Comput., 8, 131-159 (1999) · Zbl 0924.05059 |
| [12] | M.E.J. Newman, S.H. Strogatz, D.J. Watts, Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E 64, URL: \( \langle;\) http://aps.arxiv.org/abs/cond-mat/\(0007235/ \rangle;\); M.E.J. Newman, S.H. Strogatz, D.J. Watts, Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E 64, URL: \( \langle;\) http://aps.arxiv.org/abs/cond-mat/\(0007235/ \rangle;\) |
| [13] | Scheinerman, E. R., Random interval graphs, Combinatorica, 8, 4, 357-371 (1988) · Zbl 0659.05078 |
| [14] | K.B. Singer, Random intersection graphs, Ph.D. Thesis, John Hopkins University, Baltimore, MA, 1995.; K.B. Singer, Random intersection graphs, Ph.D. Thesis, John Hopkins University, Baltimore, MA, 1995. |
| [15] | Stark, D., The vertex degree distribution of random intersection graphs, Random Struct. Algorithms, 24, 3, 249-258 (2004) · Zbl 1042.05091 |
| [16] | M. Behrisch, A. Taraz, M. Ueckerdt, Colouring random intersection graphs and complex networks, December 2005, preprint.; M. Behrisch, A. Taraz, M. Ueckerdt, Colouring random intersection graphs and complex networks, December 2005, preprint. · Zbl 1215.05054 |
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.
