An integer programming model for the minimum interval graph completion problem
| Data(s) |
23/04/2015
23/04/2015
2010
|
|---|---|
| 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. |
| Identificador |
1571-0653 http://hdl.handle.net/10400.22/5826 doi:10.1016/j.endm.2010.05.074 |
| Idioma(s) |
eng |
| Publicador |
Elsevier Science BV |
| Relação |
Electronic Notes in Discrete Mathematics;36 http://www.sciencedirect.com/science/article/pii/S1571065310000752 |
| Direitos |
openAccess |
| Palavras-Chave | #Interval graph #Minimum interval completion #Minimum fill-in |
| Tipo |
conferenceObject |
