Inferring a graph from path frequency

被引：17

作者：

Akutsu, Tatsuya ^{[1
]}

Fukagawa, Daiji ^{[2
]}

Jansson, Jesper ^{[3
]}

Sadakane, Kunihiko ^{[4
]}

机构：

[1] Kyoto Univ, Bioinformat Ctr, Inst Chem Res, Kyoto 6110011, Japan

[2] Doshisha Univ, Fac Culture & Informat Sci, Kyoto 6100394, Japan

[3] Ochanomizu Univ, Tokyo 1128610, Japan

[4] Natl Inst Informat, Tokyo 1018430, Japan

来源：

DISCRETE APPLIED MATHEMATICS | 2012年 / 160卷 / 10-11期

关键词：

Kernel method; Graph algorithms; Feature vector; Pre-image; ALGORITHM; TREE;

D O I：

10.1016/j.dam.2012.02.002

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper considers the problem of inferring a graph from the number of occurrences of vertex-labeled paths, which is closely related to the pre-image problem for graphs: to reconstruct a graph from its feature space representation. It is shown that both exact and approximate versions of the problem can be solved in polynomial time in the size of an output graph by using dynamic programming algorithms if the graphs are trees whose maximum degree is bounded by a constant and the lengths of given paths and alphabet size are bounded by constants. On the other hand, it is shown that this problem is strongly NP-hard even for trees of bounded degree if the maximum length of paths is not bounded. The problem of inferring a string from the number of occurrences of fixed size substrings is also studied. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：1416 / 1428

页数：13

共 29 条

[11]

Cortes C., 2005, INT C MACH LEARN ICM, V119, P153, DOI DOI 10.1145/1102351.1102371

[12]

CORTES C., 2007, Predicting Structured Data, P143

[13] On an algorithm of Zemlyachenko for subtree isomorphism [J].