Weak pattern matching in colored graphs: Minimizing the number of connected components
Weak pattern matching in colored graphs: Minimizing the number of connected components
复制标题
彩色图中的弱模式匹配：最小化连接组件的数量
DOI：
10.1142/9789812770998_0007
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Stéphane Vialette
中科院分区：
文献类型：
--
作者：
R. Dondi;G. Fertin;Stéphane Vialette
在代谢网络分析的背景下，Lacroix等人11引入了在顶点图中查找基序发生的问题，其中基序是多种颜色的多颜色，而序列的出现是连接的顶点的子集，该子集是颜色的，是颜色的。根据本文的所有颜色。影响最小数量的连接组件的目标图可以总结如下路径。我们通过在固定数量的颜色上构建了多项式时算法，并给出多项式时间算法，而目标图也是一个路径。范围当通过基序的大小进行参数时，我们可以给出一个更快的算法，以防目标图是树。 0，其中n是目标图的顺序，当通过基序中的连接组件的数量进行参数化时，hard是hard。 -cc问题，以防目标图是一棵树。
In the context of metabolic network analysis, Lacroix et al.11 introduced 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 which are colored by all colors of the motif. We consider in this paper the above-mentioned problem in one of its natural optimization forms, referred hereafter as the Min-CC problem: Find an occurrence of a motif in a vertex-colored graph, called the target graph, that induces a minimum number of connected components. Our results can be summarized as follows. We prove the Min-CC problem to be APX–hard even in the extremal case where the motif is a set and the target graph is a path. We complement this result by giving a polynomial-time algorithm in case the motif is built upon a fixed number of colors and the target graph is a path. Also, extending recent research8 , we prove the Min- CC problem to be fixed-parameter tractable when parameterized by the size of the motif, and we give a faster algorithm in case the target graph is a tree. Furthermore, we prove the Min-CC problem for trees not to be approximable within ratio c log n for some constant c > 0, where n is the order of the target graph, and to be W[2]–hard when parameterized by the number of connected components in the occurrence of the motif. Finally, we give an exact efficient exponential-time algorithm for the Min-CC problem in case the target graph is a tree.