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

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

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

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 matching; combinatorial optimization problem; list homomorphism; evolutionary distance; genomic properties; otholog; protein-protein interaction graph

Mathematics Subject Classification ID

92D15: Problems related to evolution

05C90: Applications of graph theory

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

92D20: Protein sequences, DNA sequences

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

The complexity of locally injective homomorphisms, Complexity issues in color-preserving graph embeddings, Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs, Finding occurrences of protein complexes in protein-protein interaction graphs

Uses Software

• Chaff

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item