Upper and lower bounds for finding connected motifs in vertex-colored graphs

Title: Upper and lower bounds for finding connected motifs in vertex-colored graphs
Creator: Fellows, Michael R.; Fertin, Guillaume; Hermelin, Danny; Vialette, Stephane
Relation: Journal of Computer and System Sciences Vol. 77, Issue 4, p. 799-811
Publisher Link: http://dx.doi.org/10.1016/j.jcss.2010.07.003
Publisher: Academic Press
Resource Type: journal article
Date: 2011
Description: 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.
Subject: graph motif; graph pattern matching; parameterized complexity; W hardness; treewidth
Identifier: http://hdl.handle.net/1959.13/1056843
Identifier: uon:16090
Identifier: ISSN:0022-0000
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format