Skip to Main content Skip to Navigation
Journal articles

Finding the root graph through minimum edge deletion

Martine Labbé 1 Alfredo Marín 2 Mercedes Pelegrín 2, 3
1 INOCS - Integrated Optimization with Complex Structure
ULB - Université libre de Bruxelles, Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : The line graph of a graph G has one node per each edge of G, two of them being adjacent only when the corresponding edges have a node of G in common. In this work, we consider the problem of finding the minimum number of edges to delete so that the resulting graph is a line graph, which presents an interesting application in haplotyping of diploid organisms. We propose an Integer Linear Programming formulation for this problem. We compare our approach with the only other existing formulation for the problem and explore the possibility of combining both of them. Finally, we present a computational study to compare the different approaches proposed.
Document type :
Journal articles
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-03001376
Contributor : Martine Labbé Connect in order to contact the contributor
Submitted on : Thursday, November 12, 2020 - 12:56:39 PM
Last modification on : Wednesday, November 3, 2021 - 6:18:51 AM
Long-term archiving on: : Saturday, February 13, 2021 - 7:26:18 PM

File

last-revision.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Martine Labbé, Alfredo Marín, Mercedes Pelegrín. Finding the root graph through minimum edge deletion. European Journal of Operational Research, Elsevier, In press, ⟨10.1016/j.ejor.2020.07.001⟩. ⟨hal-03001376⟩

Share

Metrics

Record views

81

Files downloads

256