Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949973 | Discrete Applied Mathematics | 2016 | 17 Pages |
Abstract
Previous algorithms for Graph Motif and its variants either rely on techniques for developing randomized algorithms that â if derandomized â render them inefficient, or the algebraic narrow sieves technique for which there is no known derandomization. In this paper, we present fast deterministic parameterized algorithms for Graph Motif and its variants. Specifically, we give such an algorithm for the more general Graph Motif with Deletions problem, followed by faster algorithms for Graph Motif and other well-studied special cases. Our algorithms make non-trivial use of representative families, and a novel tool that we call guiding trees, together enabling the efficient construction of the output tree.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ron Y. Pinter, Hadas Shachnai, Meirav Zehavi,