Minimal interval completions

We study the problem of adding edges to a graph in order to obtain an interval graph. Our goal is to add an inclusion-minimal set of edges, in which case the resulting graph is called a minimal interval completion of the input. We give in this paper the first polynomial time algorithm solving the minimal interval completion problem.

Data and Resources

Minimal interval completionsHTML
Explore
- More information
- Go to resource

Additional Info

Field	Value
Source	13th Annual European Symposium on Algorithms (ESA 2005)
Author	Heggernes, Pinar, Suchan, Karol, Todinca, Ioan, Villanger, Yngve
Maintainer	CCSD
Last Updated	May 9, 2026, 23:04 (UTC)
Created	May 9, 2026, 23:04 (UTC)
Identifier	hal-00085564
Language	en
contributor	Laboratoire d'Informatique Fondamentale d'Orléans (LIFO) ; Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges
creator	Heggernes, Pinar
date	2005-05-09T00:00:00
harvest_object_id	375699a2-1536-4385-a2f8-2c042b92ea28
harvest_source_id	3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title	test moissonnage SELUNE
metadata_modified	2025-02-04T00:00:00
set_spec	type:COMM