{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:55:03Z","timestamp":1725663303442},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540515425"},{"type":"electronic","value":"9783540482376"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51542-9_30","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:07:07Z","timestamp":1330186027000},"page":"352-372","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Dynamic data structures for series parallel digraphs"],"prefix":"10.1007","author":[{"given":"Giuseppe F.","family":"Italiano","sequence":"first","affiliation":[]},{"given":"Alberto Marchetti","family":"Spaccamela","sequence":"additional","affiliation":[]},{"given":"Umberto","family":"Nanni","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"30_CR1","unstructured":"F. Afrati, An efficient parallel algorithm for directed reachability in series parallel graphs, manuscript 1988."},{"key":"30_CR2","unstructured":"F. Afrati, D. Goldin, and P. Kanellakis, Efficient parallelism for structured data: directed reachability in S-P dags, Technical Report, Brown University, 1988."},{"key":"30_CR3","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0201008","volume":"1","author":"A. V. Aho","year":"1972","unstructured":"A. V. Aho, M. R. Garey, and J. D. Ullman, The transitive reduction of a directed graph, SIAM J. Comput. 1 (1972), 131\u2013137.","journal-title":"SIAM J. Comput."},{"key":"30_CR4","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"M. Ajtai and R. Fagin, Reachability is harder for directed than for undirected graphs, Proc. 29th Annual Symp. on Foundations of Computer Science, 1988, 358\u2013367.","DOI":"10.1109\/SFCS.1988.21952"},{"key":"30_CR6","unstructured":"G. Ausiello, G. F. Italiano, A. Marchetti Spaccamela, and U. Nanni, On-line computation of minimal and maximal length paths, in preparation."},{"key":"30_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0035746","volume-title":"Proc. 1st Internat. Joint Conf. ISSAC 88 (Int. Symp. on Symbolic and Algebraic Computation) and AAECC 6 (6th Int. Conf. on Applied Algebra, Algebraic Algorithms and Error Correcting Codes)","author":"G. Ausiello","year":"1989","unstructured":"G. Ausiello, A. Marchetti Spaccamela, and U. Nanni, Dynamic maintenance of paths and path expressions in graphs, Proc. 1st Internat. Joint Conf. ISSAC 88 (Int. Symp. on Symbolic and Algebraic Computation) and AAECC 6 (6th Int. Conf. on Applied Algebra, Algebraic Algorithms and Error Correcting Codes), Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1989."},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"M. W. Bern, E. L. Lawler, and A. L. Wong, Why certain subgraph computations require only linear time, Proc. 26th Annual Symp. on Foundations of Computer Science, 1985, 117\u2013125.","DOI":"10.1109\/SFCS.1985.66"},{"key":"30_CR9","unstructured":"M. Burke, and B. G. Ryder, Incremental iterative data flow analysis algorithms, Technical Report LCSR-TR-96, Department of Computer Science, Rutgers University, August 1987."},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"M. D. Carrol and B. G. Ryder, Incremental data flow analysis via dominator and attribute updates, Proc. 15th Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, 1988, 274\u2013284.","DOI":"10.1145\/73560.73584"},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0022-0000(78)90022-3","volume":"16","author":"F. Chin","year":"1978","unstructured":"F. Chin and D. Houk, Algorithms for updating minimum spanning trees, J. Comput. System. Sci. 16 (1978), 333\u2013344.","journal-title":"J. Comput. System. Sci."},{"key":"30_CR12","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"R. J. Duffin","year":"1965","unstructured":"R. J. Duffin, Topology of series parallel networks, Journal of Mathematical Analysis and Applications 10 (1965), 303\u2013318.","journal-title":"Journal of Mathematical Analysis and Applications"},{"key":"30_CR13","unstructured":"D. Eppstein, Parallel recognition of series-parallel graphs, manuscript, 1989."},{"key":"30_CR14","unstructured":"D. Eppstein, G. F. Italiano, M. Yung, Minimum spanning trees in dynamic planar graphs, Tech. Rep. CUCS-434-89, Department of Computer Science, Columbia University, 1989."},{"key":"30_CR15","first-page":"371","volume":"49","author":"S. Even","year":"1985","unstructured":"S. Even, and H. Gazit, Updating distances in dynamic graphs, Methods of Operations Research 49 (1985), 371\u2013387.","journal-title":"Methods of Operations Research"},{"key":"30_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/322234.322235","volume":"28","author":"S. Even","year":"1981","unstructured":"S. Even, and Y. Shiloach, An on-line edge deletion problem, J. Assoc. Comput. Mach. 28 (1981), 1\u20134.","journal-title":"J. Assoc. Comput. Mach."},{"key":"30_CR17","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G. N. Frederickson","year":"1985","unstructured":"G. N. Frederickson, Data structures for on-line updating of minimum spanning trees, SIAM J. Comput. 14 (1985), 781\u2013798.","journal-title":"SIAM J. Comput."},{"key":"30_CR18","unstructured":"G. N. Frederickson and M. A. Srinivas, On-line updating of degree-constrained minimu spanning trees, Proc. 22nd Annual Allerton Conference on Communication, Control and Computing, 1984."},{"key":"30_CR19","unstructured":"D. Harel, On-line maintenance of the connected components of dynamic graphs, Unpublished manuscript, 1982."},{"key":"30_CR20","unstructured":"N. Horspool, Incremental generation of LR parsers, Technical Report, Department of Computer Science, University of Victoria, March 1988."},{"key":"30_CR21","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0190(83)90033-9","volume":"16","author":"T. Ibaraki","year":"1983","unstructured":"T. Ibaraki, and N. Katoh, On-line computation of transitive closure for graphs, Inform. Process. Lett. 16 (1983), 95\u201397.","journal-title":"Inform. Process. Lett."},{"key":"30_CR22","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0304-3975(86)90098-8","volume":"48","author":"G. F. Italiano","year":"1986","unstructured":"G. F. Italiano, Amortized efficiency of a path retrieval data structure, Theoret. Comput. Sci. 48 (1986), 273\u2013281.","journal-title":"Theoret. Comput. Sci."},{"key":"30_CR23","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0020-0190(88)90136-6","volume":"28","author":"G. F. Italiano","year":"1988","unstructured":"G. F. Italiano, Finding paths and deleting edges in directed acyclic graphs, Inform. Process. Lett. 28 (1988), 5\u201311.","journal-title":"Inform. Process. Lett."},{"key":"30_CR24","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0166-218X(83)90003-3","volume":"5","author":"T. Kikuno","year":"1983","unstructured":"T. Kikuno, N. Yoshida, and Y. Kakuda, A linear time algorithm for the domination number of a series parallel graph, Disc. Appl. Math. 5 (1983), 299\u2013311.","journal-title":"Disc. Appl. Math."},{"key":"30_CR25","first-page":"106","volume-title":"Proc. International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 314","author":"J. A. Poutr\u00e9 La","year":"1988","unstructured":"J. A. La Poutr\u00e9, and J. van Leeuwen, Maintenance of transitive closure and transitive reduction of graphs, Proc. International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 314, Springer-Verlag, Berlin, 1988, 106\u2013120."},{"key":"30_CR26","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0167-5060(08)70323-6","volume":"2","author":"E. L. Lawler","year":"1978","unstructured":"E. L. Lawler, Sequencing jobs to minimize total weight completion time subject to precedence constraints, Annals of Discrete Math. 2 (1978), 75\u201390.","journal-title":"Annals of Discrete Math."},{"key":"30_CR27","doi-asserted-by":"crossref","unstructured":"C. L. Monma, and J. B. Sidney, Sequencing with series-parallel precedence constraints, Math. of Operations Research 4, 215\u2013224.","DOI":"10.1287\/moor.4.3.215"},{"key":"30_CR28","doi-asserted-by":"crossref","unstructured":"F. P. Preparata, and R. Tamassia, Fully dynamic techniques for point location and transitive closure in planar structures, Proc. 29th Annual Symp. on Foundations of Computer Science, 1988, 558\u2013567.","DOI":"10.1109\/SFCS.1988.21972"},{"key":"30_CR29","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0020-0190(87)90095-0","volume":"25","author":"J. H. Reif","year":"1987","unstructured":"J. H. Reif, A topological approach to dynamic graph connectivity, Inform. Process. Lett. 25 (1987), 65\u201370.","journal-title":"Inform. Process. Lett."},{"key":"30_CR30","first-page":"279","volume-title":"Proc. 2nd Annual Symp. on Theoretical Aspects of Computer Science (STACS 85), Lecture Notes in Computer Science, vol. 182","author":"H. Rohnert","year":"1985","unstructured":"H. Rohnert, A dynamization of the all pairs least cost path problem, Proc. 2nd Annual Symp. on Theoretical Aspects of Computer Science (STACS 85), Lecture Notes in Computer Science, vol. 182, Springer-Verlag, Berlin, 1985, 279\u2013286."},{"key":"30_CR31","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"24","author":"D. D. Sleator","year":"1983","unstructured":"D. D. Sleator, and R. E. Tarjan, A data structure for dynamic trees, J. Comput. System Sci. 24 (1983), 362\u2013381.","journal-title":"J. Comput. System Sci."},{"key":"30_CR32","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1137\/0204032","volume":"4","author":"P. M. Spira","year":"1975","unstructured":"P. M. Spira and A. Pan, On finding and updating spanning trees and shortest paths, SIAM J. Comput. 4 (1975), 375\u2013380.","journal-title":"SIAM J. Comput."},{"key":"30_CR33","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K. Takamizawa","year":"1982","unstructured":"K. Takamizawa, T. Nishizeki, and N. Saito, Linear time computability of combinatorial problems on series parallel graphs, J. Assoc. Comput. Mach. 29 (1982), 623\u2013641.","journal-title":"J. Assoc. Comput. Mach."},{"key":"30_CR34","doi-asserted-by":"crossref","unstructured":"R. E. Tarjan, Data structures and network algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, SIAM, 1983.","DOI":"10.1137\/1.9781611970265"},{"key":"30_CR35","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan, Amortized computational complexity, SIAM J. Alg. Disc. Meth. 6 (1985), 306\u2013318.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"30_CR36","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R. E. Tarjan","year":"1984","unstructured":"R. E. Tarjan, and J. van Leeuwen, Worst-case analysis of set union algorithms, J. Assoc. Comput. Mach. 31 (1984), 245\u2013281.","journal-title":"J. Assoc. Comput. Mach."},{"key":"30_CR37","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J. Valdes","year":"1982","unstructured":"J. Valdes, R. E. Tarjan, and E. L. Lawler, The recognition of series parallel digraphs, SIAM J. Comput. 11 (1982), 298\u2013313.","journal-title":"SIAM J. Comput."},{"key":"30_CR38","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","volume":"34","author":"H. Whitney","year":"1932","unstructured":"H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932), 339\u2013362.","journal-title":"Trans. Amer. Math. Soc."},{"key":"30_CR39","series-title":"Research Report","volume-title":"A dynamic transitive closure algorithm","author":"D. M. Yellin","year":"1988","unstructured":"D. M. Yellin, A dynamic transitive closure algorithm, Research Report, IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY 10598, February 1988."},{"key":"30_CR40","doi-asserted-by":"crossref","unstructured":"D. M. Yellin, and R. Strom, INC: a language for incremental computations, Proc. ACM SIGPLAN '88 Conference on Programming Language Design and Implementation, 1988, 115\u2013124.","DOI":"10.1145\/960116.54002"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51542-9_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T18:55:52Z","timestamp":1578509752000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51542-9_30"}},"subtitle":["preliminary version"],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540515425","9783540482376"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/3-540-51542-9_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"26 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}