{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:10:47Z","timestamp":1725664247770},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590712"},{"type":"electronic","value":"9783540491835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59071-4_49","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:01:38Z","timestamp":1330275698000},"page":"206-218","source":"Crossref","is-referenced-by-count":3,"title":["Prefix graphs and their applications"],"prefix":"10.1007","author":[{"given":"Shiva","family":"Chaudhuri","sequence":"first","affiliation":[]},{"given":"Torben","family":"Hagerup","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/174652.174661","volume":"41","author":"N. Alon","year":"1994","unstructured":"N. Alon and N. Megiddo, Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time, J. Assoc. Comput. Mach.\n41 (1994), pp. 422\u2013434.","journal-title":"J. Assoc. Comput. Mach."},{"key":"17_CR2","unstructured":"N. Alon and B. Schieber, Optimal Preprocessing for Answering On-line Product Queries, Tech. Rep. No. 71\/87, Tel-Aviv University, 1987."},{"key":"17_CR3","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1007\/BF01200429","volume":"2","author":"O. Berkman","year":"1992","unstructured":"O. Berkman, Y. Matias and U. Vishkin, Randomized Range-Maxima in Nearly-Constant Parallel Time, Comput. Complexity\n2 (1992), pp. 350\u2013373.","journal-title":"Comput. Complexity"},{"key":"17_CR4","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0222017","volume":"22","author":"O. Berkman","year":"1993","unstructured":"O. Berkman and U. Vishkin, Recursive Star-Tree Parallel Data Structure, SIAM J. Comput.\n22 (1993), pp. 221\u2013242.","journal-title":"SIAM J. Comput."},{"key":"17_CR5","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1006\/inco.1993.1056","volume":"106","author":"O. Berkman","year":"1993","unstructured":"O. Berkman and U. Vishkin, On Parallel Integer Merging, Inform. and Computation\n106 (1993), pp. 266\u2013285.","journal-title":"Inform. and Computation"},{"key":"17_CR6","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BFb0036901","volume":"154","author":"A. K. Chandra","year":"1983","unstructured":"A. K. Chandra, S. Fortune and R. Lipton, Lower Bounds for Constant Depth Circuits for Prefix Problems, Proc. 10th International Colloquium on Automata, Languages and Programming (1983), Springer Lecture Notes in Computer Science, Vol. 154, pp. 109\u2013117.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"17_CR7","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/0022-0000(85)90015-7","volume":"30","author":"A. K. Chandra","year":"1985","unstructured":"A. K. Chandra, S. Fortune and R. Lipton, Unbounded Fan-in Circuits and Associative Functions, J. Comput. Syst. Sci.\n30 (1985), pp. 222\u2013234.","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR8","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1146\/annurev.cs.03.060188.001313","volume":"3","author":"D. Eppstein","year":"1988","unstructured":"D. Eppstein and Z. Galil, Parallel Algorithmic Techniques for Combinatorial Computation, Ann. Rev. Comput. Sci.\n3 (1988), pp. 233\u2013283.","journal-title":"Ann. Rev. Comput. Sci."},{"key":"17_CR9","first-page":"259","volume":"577","author":"T. Hagerup","year":"1992","unstructured":"T. Hagerup, The Log-Star Revolution, Proc., 9th Annual Symposium on Theoretical Aspects of Computer Science (1992), Springer Lecture Notes in Computer Science, Vol. 577, pp. 259\u2013278.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"17_CR10","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"R. E. Ladner","year":"1980","unstructured":"R. E. Ladner and M. J. Fischer, Parallel Prefix Computation, J. Assoc. Comput. Mach.\n27 (1980), pp. 831\u2013838.","journal-title":"J. Assoc. Comput. Mach."},{"key":"17_CR11","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1006\/jagm.1993.1019","volume":"14","author":"P. Ragde","year":"1993","unstructured":"P. Ragde, The Parallel Simplicity of Compaction and Chaining, J. Alg.\n14 (1993), pp. 371\u2013380.","journal-title":"J. Alg."},{"key":"17_CR12","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"P. Raghavan, Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs, J. Comput. Syst. Sci.\n37 (1988), pp. 130\u2013143.","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR13","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"L. G. Valiant","year":"1975","unstructured":"L. G. Valiant, Parallelism in Comparison Problems, SIAM J. Comput\n4 (1975), pp. 348\u2013355.","journal-title":"SIAM J. Comput"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59071-4_49.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:22:26Z","timestamp":1619572946000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59071-4_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590712","9783540491835"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-59071-4_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}