查看文章

Given a class of graphs , a graph G is a probe graph of if its vertices can be partitioned into two sets ℙ (the probes) and ℕ (nonprobes), where ℕ is an independent set, such that G can be embedded into a graph of by adding edges between certain vertices of ℕ. If the partition of the vertices into probes and nonprobes is part of the input, then we call the graph a partitioned probe graph of . We give the first polynomial-time algorithm for recognizing partitioned probe distance-hereditary graphs. By using a novel data structure for storing a multiset of sets of numbers, the running time of this algorithm is ${O}(\mathfrak\it{n}^2)$, where $\mathfrak\it{n}$ is the number of vertices of the input graph. We also show that the recognition of both partitioned and unpartitioned probe cographs can be done in ${O}(\mathfrak\it{n}^2)$ time.