2009年2月
A Detachment Algorithm for Inferring a Graph from Path Frequency
ALGORITHMICA
- 巻
- 53
- 号
- 2
- 開始ページ
- 207
- 終了ページ
- 224
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1007/s00453-008-9184-0
- 出版者・発行元
- SPRINGER
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.
- リンク情報
-
- DOI
- https://doi.org/10.1007/s00453-008-9184-0
- DBLP
- https://dblp.uni-trier.de/rec/journals/algorithmica/Nagamochi09
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000263351500004&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/algorithmica/algorithmica53.html#journals/algorithmica/Nagamochi09
- ID情報
-
- DOI : 10.1007/s00453-008-9184-0
- ISSN : 0178-4617
- DBLP ID : journals/algorithmica/Nagamochi09
- Web of Science ID : WOS:000263351500004