Algorithm engineering for color-coding with applications to signaling pathway detection

DOI10.1007/s00453-007-9008-7zbMath1170.68048OpenAlexW2043107521MaRDI QIDQ958201

Falk Hüffner, Sebastian Wernicke, Thomas Zichner

Publication date: 2 December 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9008-7

zbMATH Keywords

color-coding algorithmprotein interaction networks

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (25)

Fast exact algorithms using Hadamard product of polynomials ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ Parameterized algorithms for the module motif problem ⋮ A multivariate framework for weighted FPT algorithms ⋮ Improved Parameterized Algorithms for Network Query Problems ⋮ Improved parameterized algorithms for network query problems ⋮ Detours in directed graphs ⋮ Parameterized Algorithms and Hardness Results for Some Graph Motif Problems ⋮ Finding and counting vertex-colored subtrees ⋮ Going Far from Degeneracy ⋮ Confronting intractability via parameters ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ Maximum disjoint paths on edge-colored graphs: approximability and tractability ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Algorithms for topology-free and alignment network queries ⋮ Complexity issues in vertex-colored graph pattern matching ⋮ Unnamed Item ⋮ Partial information network queries ⋮ Faster deterministic parameterized algorithm for \(k\)-path ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ On the Descriptive Complexity of Color Coding ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ Balanced Hashing, Color Coding and Approximate Counting ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

Uses Software

• QNet
• FASPAD
• QPath

Cites Work

• On approximating the longest path in a graph
• Looking at the stars
• A faster parameterized algorithm for set packing
• A Dynamic Programming Approach to Sequencing Problems
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Divide-and-Color
• Finding paths and cycles of superpolylogarithmic length
• On Linear Time Minor Tests with Depth-First Search
• Color-coding
• Parameterized and Exact Computation
• Algorithms – ESA 2004
• Research in Computational Molecular Biology
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algorithm engineering for color-coding with applications to signaling pathway detection