论文标题
和弦图上的线性时间lexdfs
Linear Time LexDFS on Chordal Graphs
论文作者
论文摘要
词典深度首次搜索（LEXDFS）是深度第一次搜索（DFS）的特殊变体，Corneil和Krueger于2008年引入。尽管与其他图形搜索相比，该搜索已在各种应用中使用，但迄今未知一般的线性时间实现。 2014年，Köhler和Mouatadid达到了线性运行时间，以计算一些特殊的LEXDFS订单，以用于可可获得图。在本文中，我们介绍了用于和弦图的LEXDF的线性时间实现。我们的算法能够找到此图类别的任何LEXDFS订单。据我们所知，这是LexDF在非平凡的图类别上的第一个不受限制的线性时间实现。在算法中，我们使用了由词典广度首次搜索（LEXBFS）计算的搜索树。
Lexicographic Depth First Search (LexDFS) is a special variant of a Depth First Search (DFS), which was introduced by Corneil and Krueger in 2008. While this search has been used in various applications, in contrast to other graph searches, no general linear time implementation is known to date. In 2014, Köhler and Mouatadid achieved linear running time to compute some special LexDFS orders for cocomparability graphs. In this paper, we present a linear time implementation of LexDFS for chordal graphs. Our algorithm is able to find any LexDFS order for this graph class. To the best of our knowledge this is the first unrestricted linear time implementation of LexDFS on a non-trivial graph class. In the algorithm we use a search tree computed by Lexicographic Breadth First Search (LexBFS).
