Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs

DOI10.1016/j.jda.2007.06.002zbMath1146.05313OpenAlexW2054374131WikidataQ114162513 ScholiaQ114162513MaRDI QIDQ935835

Gaëlle Lelandais, Stéphane Vialette, Isabelle Fagnot

Publication date: 8 August 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2007.06.002

zbMATH Keywords

graph matchingcombinatorial optimization problemlist homomorphismevolutionary distancegenomic propertiesothologprotein-protein interaction graph

Mathematics Subject Classification ID

Problems related to evolution (92D15) Applications of graph theory (05C90) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Protein sequences, DNA sequences (92D20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

On the ordered list subgraph embedding problems ⋮ Complexity issues in color-preserving graph embeddings ⋮ Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs ⋮ The complexity of locally injective homomorphisms ⋮ Finding occurrences of protein complexes in protein-protein interaction graphs

Uses Software

• Chaff

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• New worst-case upper bounds for SAT
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Algorithms for maximum independent sets
• The Complexity of Enumeration and Reliability Problems
• Finding a Maximum Independent Set
• Theory and Applications of Satisfiability Testing
• Mathematical Foundations of Computer Science 2005
• A Computing Procedure for Quantification Theory
• The complexity of theorem-proving procedures

This page was built for publication: Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs