Minimal proper interval completions

Rapaport, I; Suchan, K; Todinca, I

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. © 2007 Elsevier B.V. All rights reserved.

Más información

Título según WOS: Minimal proper interval completions
Título según SCOPUS: Minimal proper interval completions
Título de la Revista: INFORMATION PROCESSING LETTERS
Volumen: 106
Número: 5
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 2008
Página de inicio: 195
Página final: 202
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S0020019007003171
DOI:

10.1016/j.ipl.2007.11.013

Notas: ISI, SCOPUS