查看文章

Given a class of graphs G, a graph G is a probe graph ofG if its vertices can be partitioned into two sets, P, the probes, and an independent set N, the nonprobes, such that G can be embedded into a graph of G by adding edges between certain vertices of N. If the partition of the vertices into probes and nonprobes is part of the input, then we call the graph a partitioned probe graph ofG. In this paper, we provide a recognition algorithm for partitioned probe permutation graphs with time complexity O(n²), where n is the number of vertices of the input graph. We show that a probe permutation graph has at most O(n⁴) minimal separators. As a consequence, for probe permutation graphs there exist polynomial-time algorithms solving problems like treewidth and minimum fill-in. We also characterize those graphs for which the probe graphs must be weakly chordal.