کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427583 | 686524 | 2012 | 4 صفحه PDF | دانلود رایگان |

The Graph Motif problem asks whether a given multiset of colors appears on a connected subgraph of a vertex-colored graph. The fastest known parameterized algorithm for this problem is based on a reduction to the k-Multilinear Detection (k-MlD) problem: the detection of multilinear terms of total degree k in polynomials presented as circuits. We revisit k-MlD and define k-CMlD, a constrained version of it which reflects Graph Motif more faithfully. We then give a fast algorithm for k-CMlD. As a result we obtain faster parameterized algorithms for Graph Motif and variants of it.
► Faster parameterized algorithms for functional motif problems.
► Generalization of the multilinear detection framework.
► Significant speedups in 5 variants of the basic GRAPH MOTIF problem.
Journal: Information Processing Letters - Volume 112, Issue 22, 30 November 2012, Pages 889–892