Improved approaches to solve the One-To-One SkewGraM problem
| Autor: | Ameur Soukhal, Emmanuel Neron, Hafedh Mohamed Babou, Ronan Bocquillon, Mohamed Lemine Ahmed Sidi, Mohamedade Farouk Nanne, Cheikh Dhib |
|---|---|
| Přispěvatelé: | Recherche Opérationnelle, Ordonnancement, Transport ERL 7002 (ROOT), Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Université de Nouakchott Al-Aasriya (UNA), Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL) |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
0303 health sciences
Theoretical computer science General Computer Science Computer science 02 engineering and technology [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Management Science and Operations Research Resolution (logic) Directed acyclic graph Telecommunications network Longest path problem Vertex (geometry) Set (abstract data type) 03 medical and health sciences Modeling and Simulation 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM] Integer programming Biological network ComputingMilieux_MISCELLANEOUS MathematicsofComputing_DISCRETEMATHEMATICS 030304 developmental biology |
| Zdroj: | Computers and Operations Research Computers and Operations Research, Elsevier, 2022, 138, pp.105584. ⟨10.1016/j.cor.2021.105584⟩ |
| ISSN: | 0305-0548 |
| Popis: | Network comparison is an essential issue in the analysis of biological, social, and communication networks, and recent network comparisons have required the simultaneous mining of several networks on a similar vertex set. In this work, we study the case where the input consists of a directed acyclic graph D and an undirected graph G on the same vertex set. The goal is then to find the longest path P in D whose vertices induce a connected subgraph of G . This problem is known to be NP -hard and has immediate applications in the analysis of biological networks and foreseeable applications in the analysis of social, information, and communication networks. We propose hereinafter improvements to an existing branch-and-bound method and different resolution approaches based on Integer Linear Programming. We also experimentally evaluate both simulated and real data. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect