An integer programming model for the minimum interval graph completion problem
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...
| Autor principal: | |
|---|---|
| Outros Autores: | |
| Formato: | conferenceObject |
| Idioma: | eng |
| Publicado em: |
2015
|
| Assuntos: | |
| Texto completo: | http://hdl.handle.net/10400.22/5826 |
| País: | Portugal |
| Oai: | oai:recipp.ipp.pt:10400.22/5826 |
| Resumo: | 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. |
|---|