{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T10:38:49Z","timestamp":1742380729108},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223412"},{"type":"electronic","value":"9783540278016"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27801-6_5","type":"book-chapter","created":{"date-parts":[[2010,9,5]],"date-time":"2010-09-05T23:00:15Z","timestamp":1283727615000},"page":"59-73","source":"Crossref","is-referenced-by-count":14,"title":["Approximate Labelled Subtree Homeomorphism"],"prefix":"10.1007","author":[{"given":"Ron Y.","family":"Pinter","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oleg","family":"Rokhlenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dekel","family":"Tsur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Ziv-Ukelson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","volume-title":"Network Flows: Theory, Algorithms and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice-Hall, Englewood Cliffs (1993)"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Carmel, D., Efrati, N., Landau, G.M., Maarek, Y.S., Mass, Y.: An extension of the vector space model for querying xml documents via xml fragments. In: XML and Information Retrieval (Workshop) Tampere, Finland (2002)","DOI":"10.1145\/860435.860464"},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/0196-6774(87)90030-7","volume":"8","author":"M.J. Chung","year":"1987","unstructured":"Chung, M.J.: O(N2.5) time algorithms for the subgraph homeomorphism problem on trees. J. Algorithms\u00a08, 106\u2013112 (1987)","journal-title":"J. Algorithms"},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connection with graphs. Numerische Mathematik\u00a01, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"issue":"2","key":"5_CR5","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. of the Assoc. for Comput. Mach.\u00a019(2), 248\u2013264 (1972)","journal-title":"J. of the Assoc. for Comput. Mach."},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"Feder, T., Motwani, R.: Clique partitions, graph compression and speeding-up algorithms. In: Proceedings 23rd Symposium on the Theory of Computing (STOC 1991), pp. 123\u2013133 (1991)","DOI":"10.1145\/103418.103424"},{"issue":"3","key":"5_CR7","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the Association for Computing Machinery\u00a034(3), 596\u2013615 (1987)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"5","key":"5_CR8","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1137\/0218069","volume":"18","author":"H.N. Gabow","year":"1989","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for network problems. SIAM J. Comput.\u00a018(5), 1012\u20131036 (1989)","journal-title":"SIAM J. Comput."},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(90)90081-M","volume":"29","author":"P.B. Gibbons","year":"1990","unstructured":"Gibbons, P.B., Karp, R.M., Soroker, D.: Subtree isomorphism is in random NC. Discrete Applied Mathmatics\u00a029, 35\u201362 (1990)","journal-title":"Discrete Applied Mathmatics"},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jagm.1993.1009","volume":"14","author":"V. Goldberg","year":"1993","unstructured":"Goldberg, V., Plotkin, S.A., Vidya, P.M.: Sublinear-time parallel algorithms for matching and related problems. J. Algorithms\u00a014, 180\u2013213 (1993)","journal-title":"J. Algorithms"},{"key":"5_CR11","volume-title":"Flows in Networks","author":"L.R. Ford Jr.","year":"1962","unstructured":"Ford Jr., L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)"},{"issue":"2","key":"5_CR12","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1137\/S0097539797332275","volume":"30","author":"M.Y. Kao","year":"2000","unstructured":"Kao, M.Y., Lam, T.W., Sung, W.K., Ting, H.F.: Cavity matchings, label compressions, and unrooted evolutionary trees. SIAM J. Comput.\u00a030(2), 602\u2013624 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"5_CR13","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(89)90170-1","volume":"30","author":"M. Karpinski","year":"1989","unstructured":"Karpinski, M., Lingas, A.: Subtree isomorphism is NC reducible to bipartite perfect matching. Information Processing Letters\u00a030(1), 27\u201332 (1989)","journal-title":"Information Processing Letters"},{"issue":"2","key":"5_CR14","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1137\/S0097539791218202","volume":"24","author":"P. Kilpelainen","year":"1995","unstructured":"Kilpelainen, P., Mannila, H.: Ordered and unordered tree inclusion. SIAM J. Comput.\u00a024(2), 340\u2013356 (1995)","journal-title":"SIAM J. Comput."},{"key":"5_CR15","first-page":"273","volume":"10","author":"D.W. Matula","year":"1968","unstructured":"Matula, D.W.: An algorithm for subtree identification. SIAM Rev.\u00a010, 273\u2013274 (1968)","journal-title":"SIAM Rev."},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0167-5060(08)70324-8","volume":"2","author":"D.W. Matula","year":"1978","unstructured":"Matula, D.W.: Subtree isomorphism in O(n5\/2). Ann. Discrete Math.\u00a02, 91\u2013106 (1978)","journal-title":"Ann. Discrete Math."},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"4021","DOI":"10.1093\/nar\/28.20.4021","volume":"28","author":"H. Ogata","year":"2000","unstructured":"Ogata, H., Fujibuchi, W., Goto, S., Kanehisa, M.: A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters. Nucleic Acids Research\u00a028, 4021\u20134028 (2000)","journal-title":"Nucleic Acids Research"},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/BF01586040","volume":"54","author":"J.B. Orlin","year":"1992","unstructured":"Orlin, J.B., Ahuja, R.K.: New scaling algorithms for the assignment and minimum cycle mean problems. Math. Prog.\u00a054, 541\u2013561 (1992)","journal-title":"Math. Prog."},{"key":"5_CR19","doi-asserted-by":"crossref","unstructured":"Pinter, R.Y., Rokhlenko, O., Yeger-Lotem, E., Ziv-Ukelson, M.: A new tool for the alignment of metabolic pathways (2004) (manuscript)","DOI":"10.1093\/bioinformatics\/bti554"},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1137\/0206053","volume":"6","author":"S.W. Reyner","year":"1977","unstructured":"Reyner, S.W.: An analysis of a good algorithm for the subtree problems. SIAM J. Comput.\u00a06, 730\u2013732 (1977)","journal-title":"SIAM J. Comput."},{"key":"5_CR21","unstructured":"Schlieder, T., Naumann, F.: Approximate Tree Embedding for Querying XML Data. In: ACM SIGIR Workshop on XML and IR (2000)"},{"key":"5_CR22","unstructured":"Schreiber, F.: Comparison of metabolic pathways using constraint graph drawing. In: Proceedings of the Asia-Pacific Bioinformatics Conference (APBC 2003), Conferences in Research and Practice in Information Technology, vol.19, pp. 105\u2013110 (2003)"},{"issue":"2","key":"5_CR23","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jagm.1999.1044","volume":"33","author":"R. Shamir","year":"1999","unstructured":"Shamir, R., Tsur, D.: Faster subtree isomorphism. Journal of Algorithms\u00a033(2), 267\u2013280 (1999)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"5_CR24","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(93)90181-8","volume":"48","author":"M.A. Steel","year":"1993","unstructured":"Steel, M.A., Warnow, T.: Kaikoura tree theorems: Computing the maximum agreement subtree. Information Processing Letters\u00a048(2), 77\u201382 (1993)","journal-title":"Information Processing Letters"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E.: Data Structures and Network Algorithms. In: SIAM, Philadelphia (1982)","DOI":"10.1137\/1.9781611970265"},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/3-540-44888-8_26","volume-title":"Combinatorial Pattern Matching","author":"G. Valiente","year":"2003","unstructured":"Valiente, G.: Constrained tree inclusion. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol.\u00a02676, pp. 361\u2013371. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27801-6_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:21:31Z","timestamp":1605759691000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27801-6_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223412","9783540278016"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27801-6_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}