Parallel color-coding

George M. Slota, Kamesh Madduri

Research output: Contribution to journalArticlepeer-review

11 Citations (SciVal)


Abstract We present new parallelization and memory-reducing strategies for the graph-theoretic color-coding approximation technique, with applications to biological network analysis. Color-coding is a technique that gives fixed parameter tractable algorithms for several well-known NP-hard optimization problems. In this work, by efficiently parallelizing steps in color-coding, we create two new biological protein interaction network analysis tools: Fascia for subgraph counting and motif finding and FastPath for signaling pathway detection. We demonstrate considerable speedup over prior work, and the optimizations introduced in this paper can also be used for other problems where color-coding is applicable.

Original languageEnglish (US)
Article number2236
Pages (from-to)51-69
Number of pages19
JournalParallel Computing
StatePublished - Aug 4 2015

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence


Dive into the research topics of 'Parallel color-coding'. Together they form a unique fingerprint.

Cite this