Liu, Hsiao-FeiHsiao-FeiLiuChang, Ya-HuiYa-HuiChangKUN-MAO CHAO2009-04-292018-07-052009-04-292018-07-05200401635808http://ntur.lib.ntu.edu.tw//handle/246246/154514https://www.scopus.com/inward/record.uri?eid=2-s2.0-4444368373&doi=10.1145%2f1024694.1024698&partnerID=40&md5=7fab555cfa47096243489f65b9961890Trees and graphs are widely used to model biological databases. Providing efficient algorithms to support tree-based or graph-based querying is therefore an important issue. In this paper, we propose an optimal algorithm which can answer the following question: "Where do the root-to-leaf paths of a rooted labeled tree Q occur in another rooted labeled tree T?" in time O(m + Occ), where m is the size of Q and Occ is the output size. We also show the problem of querying a general graph is NP-complete and not approximate within nk for any k < 1, where n is the number of nodes in the queried graph, unless P = NP.application/pdf950239 bytesapplication/pdfen-USAlgorithms; Approximation theory; Biotechnology; Computational complexity; Set theory; Trees (mathematics); World Wide Web; XML; Bioinformatics; Biological databases; Generalized tree pattern (GTP); Taxonomy; Database systemsconference paper10.1145/1024694.10246982-s2.0-4444368373http://ntur.lib.ntu.edu.tw/bitstream/246246/154514/1/04.pdf