| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427970 | Information Processing Letters | 2008 | 8 Pages |
Abstract
Given an arbitrary graph G=(V,E) and a proper interval graph H=(V,F) with E⊆F we say that H is a proper interval completion of G. The graph H is called a minimal proper interval completion of G if, for any sandwich graph H′=(V,F′) with E⊆F′⊂F, H′ is not a proper interval graph. In this paper we give a O(n+m) time algorithm computing a minimal proper interval completion of an arbitrary graph. The output is a proper interval model of the completion.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
