Print Email Facebook Twitter ILIGRA: An Efficient Inverse Line Graph Algorithm Title ILIGRA: An Efficient Inverse Line Graph Algorithm Author Liu, D. Trajanovski, S. Van Mieghem, P. Faculty Electrical Engineering, Mathematics and Computer Science Department Network Architectures & Services (NAS) Date 2014-04-25 Abstract 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. Subject graph algorithmline graphroot graph To reference this document use: http://resolver.tudelft.nl/uuid:aabe6d90-0681-4139-9a6d-201e70843ead Publisher Springer ISSN 2214-2487 Source Journal of Mathematical Modelling and Algorithms in Operations Research (JMMA), April 2014; Pre-print Other version https://doi.org/10.1007/s10852-014-9251-2 Part of collection Institutional Repository Document type journal article Rights (c) 2014 Springer Files PDF JMMA2014_ILIGRA.pdf 441.38 KB Close viewer /islandora/object/uuid:aabe6d90-0681-4139-9a6d-201e70843ead/datastream/OBJ/view