Minimal interval completion through graph exploration

Suchan, K; Todinca, I

Abstract

Given an arbitrary graph G = (V, E) and an interval graph H = (V, F) with E ? F we say that H is an interval completion of G. The graph H is called a minimal interval completion of G if, for any sandwich graph H' = (V, F') with E ? F' ? F, H' is not an interval graph. In this paper we give a O (n m) time algorithm computing a minimal interval completion of an arbitrary graph. The output is an interval model of the completion. © 2008 Elsevier B.V. All rights reserved.

Más información

Título según WOS: Minimal interval completion through graph exploration
Título según SCOPUS: Minimal interval completion through graph exploration
Título de la Revista: THEORETICAL COMPUTER SCIENCE
Volumen: 410
Número: 1
Editorial: Elsevier
Fecha de publicación: 2009
Página de inicio: 35
Página final: 43
Idioma: English
URL: http://linkinghub.elsevier.com/retrieve/pii/S030439750800707X
DOI:

10.1016/j.tcs.2008.09.053

Notas: ISI, SCOPUS