| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652474 | Electronic Notes in Discrete Mathematics | 2009 | 9 Pages |
Abstract
We present one more proof of the fact that the class of proper interval graphs is precisely the class of unit interval graphs. The proof leads to a new and efficient O(n) time and space algorithm that transforms a proper interval model of the graph into a unit model, where all the extremes are integers in the range 0 to O(n2), solving a problem posed by Gardi (Discrete Math., 307 (22), 2906–2908, 2007).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
