2012/01/16 by Mathieu Blanchette, Ethan Kim, Adrian Vetta · 15 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · Physics and Astronomy · #1-planar graph #Advanced Graph Theory Research #Algorithm #Bioinformatics and Genomic Networks #Bounded function #Chordal graph #Clique #Clique percolation method #Clique-sum #Combinatorics #Complex Network Analysis Techniques #Complex network #Computer science #Cover (algebra) #Discrete mathematics #Engineering #Graph #Line graph #Mathematics #Pathwidth #Theoretical computer science #Treewidth
paper · doi:10.1137/1.9781611972924.10
published in Society for Industrial and Applied Mathematics eBooks, 93-102 (Society for Industrial and Applied Mathematics)
openalex publication_date 2012/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We consider the problem of edge clique cover on sparse networks and study an application to the identification of overlapping protein complexes for a network of binary protein-protein interactions. We first give an algorithm whose running time is linear in the size of the graph, provided the treewidth is bounded. We then provide an algorithm for planar graphs with bounded branchwidth upon which we build a PTAS for planar graphs. Empirical studies show that our algorithms are both efficient and practical on actual simulated and biological networks, and that the clique covers obtained on real networks yield biological insights.