Constrained multilinear detection for faster functional motif discovery

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)889-892
Number of pages4
JournalInformation Processing Letters
Volume112
Issue number22
DOIs
StatePublished - Nov 30 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Graph algorithms
  • Parameterized algorithms
  • Randomized algorithms

Fingerprint Dive into the research topics of 'Constrained multilinear detection for faster functional motif discovery'. Together they form a unique fingerprint.

Cite this