| Author | dc.contributor.author | Rapaport Zimermann, Iván | es_CL |
| Author | dc.contributor.author | Suchan, Karol | es_CL |
| Author | dc.contributor.author | Todinca, Ioan | |
| Admission date | dc.date.accessioned | 2010-01-14T13:53:12Z | |
| Available date | dc.date.available | 2010-01-14T13:53:12Z | |
| Publication date | dc.date.issued | 2008-05-31 | |
| Cita de ítem | dc.identifier.citation | INFORMATION PROCESSING LETTERS, Volume: 106, Issue: 5, Pages: 195-202, 2008 | en_US |
| Identifier | dc.identifier.issn | 0020-0190 | |
| Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/125121 | |
| Abstract | dc.description.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. | en_US |
| Lenguage | dc.language.iso | en | en_US |
| Publisher | dc.publisher | ELSEVIER SCIENCE BV | en_US |
| Keywords | dc.subject | GRAPHS | en_US |
| Título | dc.title | Minimal Proper Interval Completions | en_US |
| Document type | dc.type | Artículo de revista | |
