Some results on more flexible versions of Graph Motif

Details Some results on more flexible versions of Graph Motif Some results on more flexible versions of Graph Motif

2012-02-23

arxiv.org/abs/1202.5184v1

Computer Science

Computational Complexity

Accepted in The 7th International Computer Science Symposium in Russia (CSR 2012)

Scientific paper

The problems studied in this paper originate from Graph Motif, a problem introduced in 2006 in the context of biological networks. Informally speaking, it consists in deciding if a multiset of colors occurs in a connected subgraph of a vertex-colored graph. Due to the high rate of noise in the biological data, more flexible definitions of the problem have been outlined. We present in this paper two inapproximability results for two different optimization variants of Graph Motif. We also study another definition of the problem, when the connectivity constraint is replaced by modularity. While the problem stays NP-complete, it allows algorithms in FPT for biologically relevant parameterizations.

Affiliated with

Also associated with

No associations

Rating

Some results on more flexible versions of Graph Motif does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Some results on more flexible versions of Graph Motif, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some results on more flexible versions of Graph Motif will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-660336