School of Computer Science, Carleton University, Ottawa, K1S 5B6, Canada

摘要

Given a class of graphs S, a graph G is a probe graph of S if its vertices can be partitioned into two sets P (the probes) and N (non–probes), where N is an independent set, such that G can be embedded into a graph of S by adding edges between certain vertices of N. We show that the recognition problem of probe interval graphs, i.e., probe graphs of the class of interval graphs, is in P.