Finding the root graph through minimum edge deletion

Martine Labbé, Alfredo Marín and Mercedes Pelegrín

European Journal of Operational Research, 2021, vol. 289, issue 1, 59-74

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.

Keywords: Line graphs; Discrete optimization; Haplotyping (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720306123
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:289:y:2021:i:1:p:59-74

DOI: 10.1016/j.ejor.2020.07.001

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().