{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T01:51:09Z","timestamp":1725501069540},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744498"},{"type":"electronic","value":"9783540744504"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74450-4_26","type":"book-chapter","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T05:49:24Z","timestamp":1189748964000},"page":"282-293","source":"Crossref","is-referenced-by-count":5,"title":["All-Pairs Ancestor Problems in Weighted Dags"],"prefix":"10.1007","author":[{"given":"Matthias","family":"Baumgart","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Eckhardt","sequence":"additional","affiliation":[]},{"given":"Jan","family":"Griebsch","sequence":"additional","affiliation":[]},{"given":"Sven","family":"Kosub","sequence":"additional","affiliation":[]},{"given":"Johannes","family":"Nowak","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"26_CR1","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1137\/0205011","volume":"5","author":"A. Aho","year":"1976","unstructured":"Aho, A., Hopcroft, J., Ullman, J.: On finding lowest common ancestors in trees. SIAM J.\u00a0Comput.\u00a05(1), 115\u2013132 (1976)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"1","key":"26_CR2","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1145\/59287.59293","volume":"11","author":"H. A\u00eft-Kaci","year":"1989","unstructured":"A\u00eft-Kaci, H., Boyer, R., Lincoln, P., Nasr, R.: Efficient implementation of lattice operations. ACM Trans.\u00a0Program.\u00a0Lang.\u00a0Syst.\u00a011(1), 115\u2013146 (1989)","journal-title":"ACM Trans.\u00a0Program.\u00a0Lang.\u00a0Syst."},{"issue":"4\u20135","key":"26_CR3","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/BF01940874","volume":"16","author":"N. Alon","year":"1996","unstructured":"Alon, N., Naor, M.: Derandomization, witnesses for boolean matrix multiplication and construction of perfect hash functions. Algorithmica\u00a016(4\u20135), 434\u2013449 (1996)","journal-title":"Algorithmica"},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"Baumgart, M., Eckhardt, S., Griebsch, J., Kosub, S., Nowak, J.: All-pairs common-ancestor problems in weighted dags. Technical Report TUM-I0606, Institut f\u00fcr Informatik, TU M\u00fcnchen (April 2006)","DOI":"10.1007\/978-3-540-74450-4_26"},{"key":"26_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1007\/3-540-48481-7_43","volume-title":"Algorithms - ESA\u201999","author":"A. Bencz\u00far","year":"1999","unstructured":"Bencz\u00far, A., F\u00f6rster, J., Kir\u00e1ly, Z.: Dilworth\u2019s theorem and its application for path systems of a cycle - implementation and analysis. In: Ne\u0161et\u0159il, J. (ed.) ESA 1999. LNCS, vol.\u00a01643, pp. 498\u2013509. Springer, Heidelberg (1999)"},{"key":"26_CR6","unstructured":"Bender, M., Pemmasani, G., Skiena, S., Sumazin, P.: Finding least common ancestors in directed acyclic graphs. In: SODA 2001. Proc. 12th Annual Symposium on Discrete Algorithms, pp. 845\u2013854 (2001)"},{"issue":"2","key":"26_CR7","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"M. Bender","year":"2005","unstructured":"Bender, M., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. J.\u00a0Algorithms\u00a057(2), 75\u201394 (2005)","journal-title":"J.\u00a0Algorithms"},{"issue":"2","key":"26_CR8","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/S0022-0000(05)80002-9","volume":"48","author":"O. Berkman","year":"1994","unstructured":"Berkman, O., Vishkin, U.: Finding level-ancestors in trees. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a048(2), 214\u2013230 (1994)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"issue":"4","key":"26_CR9","doi-asserted-by":"publisher","first-page":"894","DOI":"10.1137\/S0097539700370539","volume":"34","author":"R. Cole","year":"2005","unstructured":"Cole, R., Hariharan, R.: Dynamic LCA queries on trees. SIAM\u00a0J.\u00a0Comput.\u00a034(4), 894\u2013923 (2005)","journal-title":"SIAM\u00a0J.\u00a0Comput."},{"issue":"3","key":"26_CR10","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J.\u00a0Symbolic Computation\u00a09(3), 251\u2013280 (1990)","journal-title":"J.\u00a0Symbolic Computation"},{"issue":"1","key":"26_CR11","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1006\/jcom.1997.0438","volume":"13","author":"D. Coppersmith","year":"1997","unstructured":"Coppersmith, D.: Rectangular matrix multiplication revisited. J.\u00a0Complexity\u00a013(1), 42\u201349 (1997)","journal-title":"J.\u00a0Complexity"},{"key":"26_CR12","unstructured":"Czumaj, A., Kowaluk, M., Lingas, A.: Faster algorithms for finding lowest common ancestors in directed acyclic graphs. Electronic Colloquium on Computational Complexity (ECCC), TR06-111 (2006)"},{"issue":"6","key":"26_CR13","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1109\/90.974527","volume":"9","author":"L. Gao","year":"2001","unstructured":"Gao, L.: On inferring autonomous system relationships in the Internet. IEEE\/ACM Trans.\u00a0Networking\u00a09(6), 733\u2013745 (2001)","journal-title":"IEEE\/ACM Trans.\u00a0Networking"},{"issue":"2","key":"26_CR14","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.: Fast algorithms for finding nearest common ancestors. SIAM J.\u00a0Comput.\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM J.\u00a0Comput."},{"key":"26_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/11523468_20","volume-title":"Automata, Languages and Programming","author":"M. Kowaluk","year":"2005","unstructured":"Kowaluk, M., Lingas, A.: LCA queries in directed acyclic graphs. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 241\u2013248. Springer, Heidelberg (2005)"},{"issue":"1","key":"26_CR16","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1109\/TCBB.2004.10","volume":"1","author":"B. Moret","year":"2004","unstructured":"Moret, B., Nakhleh, L., Warnow, T., Linder, C., Tholse, A., Padolina, A., Sun, J., Timme, R.: Phylogenetic networks: Modeling, reconstructibility, and accuracy. IEEE\/ACM Trans.\u00a0Comput.\u00a0Biology\u00a0Bioinform.\u00a01(1), 13\u201323 (2004)","journal-title":"IEEE\/ACM Trans.\u00a0Comput.\u00a0Biology\u00a0Bioinform."},{"key":"26_CR17","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/11567752_6","volume-title":"Transactions on Computational Systems Biology II","author":"L. Nakhleh","year":"2005","unstructured":"Nakhleh, L., Wang, L.: Phylogenetic networks: Properties and relationship to trees and clusters. In: Priami, C., Zelikovsky, A. (eds.) Transactions on Computational Systems Biology II. LNCS (LNBI), vol.\u00a03680, pp. 82\u201399. Springer, Heidelberg (2005)"},{"issue":"1","key":"26_CR18","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/0020-0190(94)00050-6","volume":"50","author":"M. Nyk\u00e4nen","year":"1994","unstructured":"Nyk\u00e4nen, M., Ukkonen, E.: Finding lowest common ancestors in arbitrarily directed trees. Inf.\u00a0Process.\u00a0Lett.\u00a050(1), 307\u2013310 (1994)","journal-title":"Inf.\u00a0Process.\u00a0Lett."},{"issue":"6","key":"26_CR19","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"Schieber, B., Vishkin, U.: On finding lowest common ancestors: Simplification and parallelization. SIAM J.\u00a0Comput.\u00a017(6), 1253\u20131262 (1988)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"3","key":"26_CR20","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1995.1078","volume":"51","author":"R. Seidel","year":"1995","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a051(3), 400\u2013403 (1995)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"issue":"4","key":"26_CR21","first-page":"690","volume":"26","author":"R. Tarjan","year":"1979","unstructured":"Tarjan, R.: Applications of path compression on balanced trees. J.\u00a0ACM\u00a026(4), 690\u2013715 (1979)","journal-title":"J.\u00a0ACM"},{"issue":"1\u20132","key":"26_CR22","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0255(99)00046-8","volume":"119","author":"B. Wang","year":"1999","unstructured":"Wang, B., Tsai, J., Chuang, Y.: The lowest common ancestor problem on a tree with an unfixed root. Inf.\u00a0Sci.\u00a0119(1\u20132), 125\u2013130 (1999)","journal-title":"Inf.\u00a0Sci."},{"issue":"1","key":"26_CR23","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0020-0190(94)00058-1","volume":"51","author":"Z. Wen","year":"1994","unstructured":"Wen, Z.: New algorithms for the LCA problem and the binary tree reconstruction problem. Inf.\u00a0Process.\u00a0Lett.\u00a051(1), 11\u201316 (1994)","journal-title":"Inf.\u00a0Process.\u00a0Lett."},{"issue":"3","key":"26_CR24","first-page":"289","volume":"49","author":"U. Zwick","year":"2002","unstructured":"Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. J.\u00a0ACM\u00a049(3), 289\u2013317 (2002)","journal-title":"J.\u00a0ACM"}],"container-title":["Lecture Notes in Computer Science","Combinatorics, Algorithms, Probabilistic and Experimental Methodologies"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74450-4_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,26]],"date-time":"2020-04-26T13:52:48Z","timestamp":1587909168000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74450-4_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540744498","9783540744504"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74450-4_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}