An integer programming model for the minimum interval graph completion problem

Lopes, Isabel Cristina; Carvalho, J. M. Valerio de

http://hdl.handle.net/10400.22/5826

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
COM_IsabelLopes_2010_1.pdf		497.27 KB	Adobe PDF	Download

Send Feedback

Authors

Lopes, Isabel Cristina

Carvalho, J. M. Valerio de

Abstract(s)

The minimum interval graph completion problem consists of, given a graph G = ( V, E ), ﬁnding a supergraph H = ( V, E ∪ F ) that is an interval graph, while adding the least number of edges |F| . We present an integer programming formulation for solving the minimum interval graph completion problem recurring to a characteri- zation of interval graphs that produces a linear ordering of the maximal cliques of the solution graph.