Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
复制标题
用于在顶点彩色图中查找连接图案的清晰易处理边界线
DOI：
10.1007/978-3-540-73420-8_31
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Stéphane Vialette
中科院分区：
文献类型：
--
作者：
M. Fellows;G. Fertin;D. Hermelin;Stéphane Vialette
我们研究了在顶点着色图中发现图案出现的问题，其中图案是颜色的多集，图案的出现是连通顶点的子集，其颜色的多集等于图案。这个问题在代谢网络分析中有应用，代谢网络分析是生物信息学的一个重要领域。我们给出了两个积极的结果和三个消极的结果，这些结果共同在问题的易处理和难处理的实例之间划出了清晰的界限
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 has applications in metabolic network analysis, an important area in bioinformatics. We give two positive results and three negative results that together draw sharp borderlines between tractable and intractable instances of the problem