A path graph is the intersection graph of paths in a tree. A directed path graph is the intersection graph of paths in a directed tree. We present a new algorithm to recognize path graphs and directed path graphs. It has the same worst-case time complexity as the faster recognition algorithms known so far but it does not require complex data structures and it has an easy and intuitive implementation based on a new characterization of path graphs [N. Apollonio and L. Balzotti, A New Characterization of Path Graphs, arXiv:1911.09069, (2019).].
A New Algorithm to Recognize Path Graphs and Directed Path Graphs / Balzotti, Lorenzo. - (2021).
A New Algorithm to Recognize Path Graphs and Directed Path Graphs
Lorenzo Balzotti
Primo
2021
Abstract
A path graph is the intersection graph of paths in a tree. A directed path graph is the intersection graph of paths in a directed tree. We present a new algorithm to recognize path graphs and directed path graphs. It has the same worst-case time complexity as the faster recognition algorithms known so far but it does not require complex data structures and it has an easy and intuitive implementation based on a new characterization of path graphs [N. Apollonio and L. Balzotti, A New Characterization of Path Graphs, arXiv:1911.09069, (2019).].I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
