论文标题
MCS的多项式时间算法，用于弦图上的部分搜索顺序
A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs
论文作者
论文摘要
我们研究了Scheffler [WG 2022]最近提出的部分搜索顺序问题（PSOP）。给定在$ g $的顶点上的图形$ g $以及部分订单，此问题确定是否存在$ \ nathcal {s} $ - 订购与给定的部分顺序一致的订购，其中$ \ mathcal {s} $是图形搜索范围，例如BFS，dfs，dfs，dfs，dfs，自然而然地classion-eart-eart-eart-eart-eart-eND-END-ENER-ENED-ENER-END-ENER-END-ENER-END-VERSECES，可以验证过时的问题。它还概括了所谓的$ {\ mathcal {f}} $ - 树识别问题，该问题最近在文献中刚刚研究过。我们的主要贡献是一种限于弦图的最大基数搜索（MCS）PSOP的多项式动态编程算法。这解决了Schefller [WG 2022]工作中最有趣的开放问题之一。为了获得我们的结果，我们提出了层结构的概念，并研究了可能具有独立感兴趣的许多相关结构特性。
We study the partial search order problem (PSOP) proposed recently by Scheffler [WG 2022]. Given a graph $G$ together with a partial order over the set of vertices of $G$, this problem determines if there is an $\mathcal{S}$-ordering that is consistent with the given partial order, where $\mathcal{S}$ is a graph search paradigm like BFS, DFS, etc. This problem naturally generalizes the end-vertex problem which has received much attention over the past few years. It also generalizes the so-called ${\mathcal{F}}$-tree recognition problem which has just been studied in the literature recently. Our main contribution is a polynomial-time dynamic programming algorithm for the PSOP of the maximum cardinality search (MCS) restricted to chordal graphs. This resolves one of the most intriguing open questions left in the work of Scheffler [WG 2022]. To obtain our result, we propose the notion of layer structure and study numerous related structural properties which might be of independent interest.
