Complexity issues in color-preserving graph embeddings

DOI10.1016/j.tcs.2009.10.010zbMath1219.05180OpenAlexW2085373167MaRDI QIDQ846361

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

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

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

Uses Software

• NetAlign

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Approximating the 2-interval pattern problem
• Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• On the computational complexity of 2-interval pattern matching problems
• On double and multiple interval graphs
• 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
• Probability and Computing
• Mathematical Foundations of Computer Science 2005

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