A polynomial time recognition algorithm for probe interval graphs
Julie L. Johnson, Jeremy Spinrad · Symposium on Discrete Algorithms · 2001
Probe interval graphs were introduced to model a problem arising in a form of DNA sequencing. This paper presents an O(n2) algorithm for recognizing probe interval graphs. This is the first polynomial time recognition algorithm for this class.