Name
Abstract | ||
|---|---|---|
We study the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors, and an occurrence of a motif is a subset of connected vertices whose multiset of colors equals the motif. This problem is a natural graph-theoretic pattern matching variant where we are not interested in the actual structure of the occurrence of the pattern, we only require it to preserve the very basic topological requirement of connectedness. We give two positive results and three negative results that together give an extensive picture of tractable and intractable instances of the problem. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jcss.2010.07.003 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
treewidth,graph pattern matching,positive result,w hardness,extensive picture,basic topological requirement,lower bound,connected vertex,vertex-colored graph,graph motif,connected motif,intractable instance,parameterized complexity,negative result,actual structure,natural graph-theoretic pattern,pattern matching,upper and lower bounds | Discrete mathematics,Social connectedness,Combinatorics,Parameterized complexity,Vertex (geometry),Multiset,Upper and lower bounds,Motif (music),Treewidth,Pattern matching,Mathematics | Journal |
Volume | Issue | ISSN |
77 | 4 | Journal of Computer and System Sciences |
Citations | PageRank | References |
29 | 1.05 | 26 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael R. Fellows | 1 | 4138 | 319.37 |
| Guillaume Fertin | 2 | 569 | 57.84 |
| Danny Hermelin | 3 | 790 | 48.62 |
| Stéphane Vialette | 4 | 648 | 48.10 |