论文标题
路径图和有向路径图的简单和统一识别算法
Simpler and Unified Recognition Algorithm for Path Graphs and Directed Path Graphs
论文作者
论文摘要
路径图是树中路径的交点图。有向路径图是有向树中路径的相交图。即使路径图和有向路径图的表征非常相似，它们的识别算法也有很大差异。我们通过介绍两个路径图和有向路径图的第一个识别算法来进一步统一这两个图类类。我们深入使用路径图的最新表征，并将其扩展到有向路径图。我们的算法不需要复杂的数据结构，并且具有简单且直观的实现，从而简化了两个图类类的识别算法。
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. Even if path graphs and directed path graphs are characterized very similarly, their recognition algorithms differ widely. We further unify these two graph classes by presenting the first recognition algorithm for both path graphs and directed path graphs. We deeply use a recent characterization of path graphs, and we extend it to directed path graphs. Our algorithm does not require complex data structures and has an easy and intuitive implementation, simplifying recognition algorithms for both graph classes.
