×

zbMATH — the first resource for mathematics

ILIGRA: an efficient inverse line graph algorithm. (English) Zbl 1347.05239
Summary: This paper presents a new and efficient algorithm, Iligra, for inverse line graph construction. Given a line graph \(H\), Iligra constructs its root graph \(G\) with the time complexity being linear in the number of nodes in \(H\). If Iligra does not know whether the given graph \(H\) is a line graph, it firstly assumes that \(H\) is a line graph and starts its root graph construction. During the root graph construction, Iligra checks whether the given graph \(H\) is a line graph and Iligra stops once it finds \(H\) is not a line graph. The time complexity of Iligra with line graph checking is linear in the number of links in the given graph \(H\). For sparse line graphs of any size and for dense line graphs of small size, numerical results of the running time show that Iligra outperforms all currently available algorithms.

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C76 Graph operations (line graphs, products, etc.)
68Q25 Analysis of algorithms and problem complexity
Software:
ILIGRA; LEDA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahn, YY; Bagrow, JP; Lehmann, S., Link communities reveal multiscale complexity in networks, Nature, 466, 761-764, (2010)
[2] Barabási, AL; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512, (1999) · Zbl 1226.05223
[3] Bollobás, B.: Random Graphs. Cambridge University Press, Cambridge (2001) · Zbl 0979.05003
[4] Cauchy, A.L.: Cours d’analyse de l’Ecole Royale Polytechnique, vol. 3 (1821). Imprimerie royale, Paris (reissued by Cambridge University Press), Cambridge (2009) · Zbl 1205.26006
[5] Cvetković, D., Rowlinson, P., Simić, S.: Spectral Generalizations of Line Graphs. Cambridge University Press, Cambridge (2004) · Zbl 1061.05057
[6] Degiorgi, D.G., Simon, K.: A dynamic algorithm for line graph recognition. In: Proceedings of 21st International Workshop on Graph-Theoretic Concepts in Computer Science (Lecture Notes in Computer Science 1017), pp. 37-48. Springer-Verlag (1995)
[7] Erdős, P.; Rényi, A., On random graphs, I, Publ. Math. (Debr.), 6, 290-297, (1959) · Zbl 0092.15705
[8] Evans, T., Lambiotte, R.: Line graphs, link partitions, and overlapping communities. Phys. Rev. E 80(1), 016105 (2009)
[9] Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities, 2nd edn. Cambridge University Press, Cambridge (1988)
[10] Krausz, J., Démonstration nouvelle d’un théorème de Whitney sur les réseaux, Mat. Fiz. Lapok, 50, 75-85, (1943) · Zbl 0061.41401
[11] Krawczyk, MJ; Muchnik, L.; Manka-Krason, A.; Kulakowski, K., Line graphs as social networks, Phys. A, 390, 2611-2618, (2011)
[12] Lehot, PGH, An optimal algorithm to detect a line graph and output its root graph, J. ACM, 21, 569-575, (1974) · Zbl 0295.05118
[13] Manka-Krason, A.; Kulakowski, K., Assortativity in random line graphs, Acta Phys. Pol. B Proc. Suppl., 3, 259-266, (2010)
[14] Manka-Krason, A.; Mwijage, A.; Kulakowski, K., Clustering in random line graphs, Comput. Phys. Commun., 181, 118-121, (2010) · Zbl 1202.05129
[15] Mehlhorn, K., Näher, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999) · Zbl 0976.68156
[16] Nacher, JC; Ueda, U.; Yamada, T.; Kanehisa, M.; Akutsu, T., Line graphs as social networks, BMC Bioinfo., 24, 2611-2618, (2004)
[17] Nacher, JC; Yamada, T.; Goto, S.; Kanehisa, M.; Akutsu, T., Two complementary representations of a scale-free network, Phys. A, 349, 349-363, (2005)
[18] Naor, J.; Novick, MB, An efficient reconstruction of a graph from its line graph in parallel, J. Algoritm., 11, 132-143, (1990) · Zbl 0715.68070
[19] Ore, O.: Theory of Graphs, vol. 21. American Mathematical Society Colloquium Publications (1962) · Zbl 0105.35401
[20] Roussopoulos, ND, A maxm,n algorithm for detecting the graph h from its line graph g, Info. Process. Lett., 2, 108-112, (1973) · Zbl 0274.05116
[21] Simić, S., An algorithm to recognize a generalized line graphs and ouput its root graph, Publ. Math. Inst. (Belgrade), 49, 21-26, (1990)
[22] Van Mieghem, P.: Graph Spectra for Complex Networks. Cambridge University Press, Cambridge (2011) · Zbl 1232.05128
[23] Rooij, ACM; Wilf, HS, The interchange graph of a finite graph, Acta Math. Acad. Sci. Hung., 16, 263-269, (1965) · Zbl 0139.17203
[24] Whitney, H., Congruent graphs and the connectivity of graphs, Am. J. Math., 54, 150-168, (1932) · Zbl 0003.32804
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.