A Detachment Algorithm for Inferring a Graph from Path Frequency
A Detachment Algorithm for Inferring a Graph from Path Frequency
复制标题
从路径频率推断图的分离算法
DOI：
10.1007/11809678_30
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
H. Nagamochi
中科院分区：
文献类型：
--
作者：
H. Nagamochi
从路径频率推断图是一个在药物设计中有潜在应用的重要问题。给定长度最多为K的多个标签串集合g，该问题要求找到一个顶点标记图G，该图G在g与沿着长度最多为K的所有路径的标签序列集合之间实现一一对应。在G中。本文证明了K=1的问题可以转化为一个寻找无环连通分离的问题，并在此基础上给出了求解该问题的一个有效算法。我们的算法还解决了一个额外的约束，这样每个顶点都需要有一个指定的程度的问题。
Inferring a graph from path frequency has been studied as an important problem which has a potential application to drug design. Given a multiple set g of strings of labels with length at most K, the problem asks to find a vertex-labeled graph G that attains a one-to-one correspondence between g and the set of sequences of labels along all paths of length at most K in G. In this paper, we prove that the problem with K=1 can be formulated as a problem of finding a loopless and connected detachment, based on which an efficient algorithm for solving the problem is derived. Our algorithm also solves the problem with an additional constraint such that every vertex is required to have a specified degree.