论文标题
线性化部分搜索订单
Linearizing Partial Search Orders
论文作者
论文摘要
近年来，几位作者研究了有关给定图形搜索特殊订购的问题的问题。一方面，Corneil等人引入的所谓最终佛教问题。 2010年，要求以特殊顶点结尾的搜索订单。另一方面，Hagerup在1980年代已经引入了诱发给定搜索树的订单的问题，并在Beisegel等人最近受到了新的关注。在这里，我们通过研究是否有一个搜索顺序是图形顶点集上给定的部分顺序的线性扩展，从而介绍了其中一些问题的概括。我们表明，可以在LBF的弦核两分图上以多项式时间解决此问题，这也意味着最终Vertex问题的第一个多项式时间算法，以及对于图类类和搜索的这种组合的两个搜索树问题。此外，我们在拆分图上介绍了LBF和MC的多项式时间算法，这些算法概括了最终Vertex和搜索树问题的已知结果。
In recent years, questions about the construction of special orderings of a given graph search were studied by several authors. On the one hand, the so called end-vertex problem introduced by Corneil et al. in 2010 asks for search orderings ending in a special vertex. On the other hand, the problem of finding orderings that induce a given search tree was introduced already in the 1980s by Hagerup and received new attention most recently by Beisegel et al. Here, we introduce a generalization of some of these problems by studying the question whether there is a search ordering that is a linear extension of a given partial order on a graph's vertex set. We show that this problem can be solved in polynomial time on chordal bipartite graphs for LBFS, which also implies the first polynomial-time algorithms for the end-vertex problem and two search tree problems for this combination of graph class and search. Furthermore, we present polynomial-time algorithms for LBFS and MCS on split graphs which generalize known results for the end-vertex and search tree problems.
