Skip to Main content Skip to Navigation
Journal articles

Complexity Issues in Color-Preserving Graph Embeddings

Abstract : In the context of comparative analysis of protein-protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex (pattern graph) in the protein-protein interaction graph (target graph) of another species with respect to (w.r.t.) orthologous proteins. We give an efficient exponential-time randomized algorithm in case the Occurrence of the pattern graph in the target graph is required to be exact. For approximate occurrences, we prove a tight inapproximability result and give four approximation algorithms that deal with bounded degree graphs, small ortholog numbers, linear forests and very simple yet hard instances, respectively.
Document type :
Journal articles
Complete list of metadata

https://hal-upec-upem.archives-ouvertes.fr/hal-00619754
Contributor : Stéphane Vialette Connect in order to contact the contributor
Submitted on : Tuesday, September 6, 2011 - 5:37:20 PM
Last modification on : Friday, April 15, 2022 - 3:33:14 PM

Links full text

Identifiers

Citation

Gaëlle Brevier, Romeo Rizzi, Stéphane Vialette. Complexity Issues in Color-Preserving Graph Embeddings. Theoretical Computer Science, Elsevier, 2010, 411 (4-5), pp.716-729. ⟨10.1016/j.tcs.2009.10.010⟩. ⟨hal-00619754⟩

Share

Metrics

Record views

60