作者
Gerard Jennhwa Chang, Antonius JJ Kloks, Jiping Liu, Sheng-Lung Peng
发表日期
2005/2/24
图书
Annual Symposium on Theoretical Aspects of Computer Science
页码范围
521-532
出版商
Springer Berlin Heidelberg
简介
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 ℕ (non–probes), where ℕ is an independent set, such that G can be embedded into a graph of by adding edges between certain vertices of ℕ. We show that the recognition problem of probe interval graphs, i.e., probe graphs of the class of interval graphs, is in P.
引用总数
学术搜索中的文章
GJ Chang, AJJ Kloks, J Liu, SL Peng - Annual Symposium on Theoretical Aspects of …, 2005