論文

査読有り
2009年2月

A detachment algorithm for inferring a graph from path frequency

Algorithmica (New York)
  • Hiroshi Nagamochi

53
2
開始ページ
207
終了ページ
224
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1007/s00453-008-9184-0

Inferring graphs from path frequency has been studied as an important problem which has a potential application to drug design and elucidation of chemical structures. 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 occurrences 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 in an inferred graph is required to have a specified degree. © 2008 Springer Science+Business Media, LLC.

リンク情報
DOI
https://doi.org/10.1007/s00453-008-9184-0
ID情報
  • DOI : 10.1007/s00453-008-9184-0
  • ISSN : 0178-4617
  • ISSN : 1432-0541
  • SCOPUS ID : 60649083386

エクスポート
BibTeX RIS