A carregar...
Publicação
An integer programming model for the minimum interval graph completion problem
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 497.27 KB | Adobe PDF |
Orientador(es)
Resumo(s)
The minimum interval graph completion problem consists of, given a graph G =
( V, E ), finding 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.
Descrição
Palavras-chave
Interval graph Minimum interval completion Minimum fill-in
Contexto Educativo
Citação
Editora
Elsevier Science BV