None

An Efficient Inverse Line Graph Algorithm

Journal article (2014)
Department
Network Architectures & Services (NAS) (EEMCS) (TU Delft)
Copyright: © 2014 Springer
More Info
expand_more

Published Date

25-04-2014

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Source:

Journal of Mathematical Modelling and Algorithms in Operations Research (JMMA), April 2014; Pre-print

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Network Architectures & Services (NAS)

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.

Files

JMMA2014_ILIGRA.pdf
(pdf | 0.431 Mb)
Unknown license