Complexity issues in color-preserving graph embeddings

DOI10.1016/J.TCS.2009.10.010MaRDI QIDQ846361zbMATH OpenOpenAlexFDO

Authors Gaëlle Brevier, Romeo Rizzi, Stéphane Vialette

Publication date 9 February 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.10.010

zbMATH Keywords

graph matchingprotein-protein interaction graph: color-preserving graph embedding

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90)

Review text

A graph based formalism is used to detect the preservation of a given protein complex in the protein-protein interaction graph of another species with respect to orthologous proteins. The authors 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 the authors prove a tight inapproximability result and give four approximation algorithms that deal with bounded degree graphs, small orthologous numbers, linear forests and very simple yet hard instances.

Recommendations

• Embedding Graphs into Colored Graphs
• Simultaneous embedding of colored graphs
• scientific article; zbMATH DE number 4142064
• On the complexity of graph embeddings
• Choosing Colors for Geometric Graphs Via Color Space Embeddings
• scientific article; zbMATH DE number 3487493
• The complexity of some graph colouring problems
• Graph color extensions: When Hadwiger's conjecture and embeddings help
• Coloring edges of embedded graphs
• The complexity of colouring problems on dense graphs

Cites work

• Approximating the 2-interval pattern problem
• Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 2086914 (Why is no real title available?)
• scientific article; zbMATH DE number 2119734 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2005
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• On double and multiple interval graphs
• On the computational complexity of 2-interval pattern matching problems
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Optimization, approximation, and complexity classes
• Probability and Computing
• Some APX-completeness results for cubic graphs

Cited in

(4)

• Finding occurrences of protein complexes in protein-protein interaction graphs
• Pattern Matching in Protein-Protein Interaction Graphs
• Mathematical Foundations of Computer Science 2005
• Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs

Describes a project that uses

Uses Software

• NetAlign

This page was built for publication: Complexity issues in color-preserving graph embeddings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q846361)