Please use this identifier to cite or link to this item:
Main Title: Finding Supported Paths in Heterogeneous Networks
Author(s): Fertin, Guillaume
Komusiewicz, Christian
Mohamed-Babou, Hafedh
Rusu, Irena
Type: Article
Language Code: en
Abstract: Subnetwork mining is an essential issue in the analysis of biological, social and communication networks. Recent applications require the simultaneous mining of several networks on the same or a similar vertex set. That is, one searches for subnetworks fulfilling different properties in each input network. We study the case that the input consists of a directed graph D and an undirected graph G on the same vertex set, and the sought pattern is a path P in D whose vertex set induces a connected subgraph of G. In this context, three concrete problems arise, depending on whether the existence of P is questioned or whether the length of P is to be optimized: in that case, one can search for a longest path or (maybe less intuitively) a shortest one. These problems have immediate applications in biological networks and predictable applications in social, information and communication networks. We study the classic and parameterized complexity of the problem, thus identifying polynomial and NP-complete cases, as well as fixed-parameter tractable and W[1]-hard cases. We also propose two enumeration algorithms that we evaluate on synthetic and biological data.
Issue Date: 9-Oct-2015
Date Available: 1-Aug-2019
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): NP-hard problems
directed acyclic graphs
longest path problem
shortest path problem
protein interaction networks
metabolic networks
Journal Title: Algorithms
Publisher: MDPI
Publisher Place: Basel
Volume: 8
Issue: 4
Publisher DOI: 10.3390/a8040810
Page Start: 810
Page End: 831
EISSN: 1999-4893
Appears in Collections:FG Algorithmik und Komplexitätstheorie » Publications

Files in This Item:
File Description SizeFormat 
algorithms-08-00810.pdf498.13 kBAdobe PDFThumbnail

This item is licensed under a Creative Commons License Creative Commons