Title: A New Algorithm to Recognize Path Graphs and Directed Path Graphs.
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).].
Publication Year: 2020
Publication Date: 2020-12-15
Language: en
Type: preprint
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot