Guillemot Sylvain

  1. Finding and counting vertex-colored subtrees.

    Authors: Guillemot Sylvain, Florian Sikora
    Subjects: Computational Complexity
    Abstract

    The problems studied in this article originate in the Graph Motif problem
    introduced by Lacroix et al. (TCBB 2006) in the context of biological networks.
    The problem is to decide if a vertex-colored graph has a connected subgraph
    whose colors equals a given multiset of colors M. Using an algebraic framework
    recently introduced in Koutis (ICALP 2008) and Koutis, Williams (ICALP 2009),
    we obtain new FPT algorithms for Graph Motif and variants, with improved
    running times.

Syndicate content