A New Algorithm to Recognize Path Graphs.
Lorenzo Balzotti · arXiv (Cornell University) · 2020
A Path Graph is the intersection graph of vertex paths in an undirected tree. We present a new algorithm to recognize Path Graphs. It has the same worst-case time complexity as the faster recognition algorithm known so far [A.A. Schaffer, A faster algorithm to recognize undirected path graphs, Discrete Applied Mathematics, 43 (1993), pp. 261-295.] but it has an easier and more intuitive implementation based on a new characterization of Path Graphs [N. Apollonio and L. Balzotti, A New Characterization of Path Graphs, CoRR, abs/1911.09069, (2019).].