{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:56Z","timestamp":1725663776096},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540571551"},{"type":"electronic","value":"9783540479185"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57155-8_269","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T07:06:16Z","timestamp":1330239976000},"page":"442-451","source":"Crossref","is-referenced-by-count":8,"title":["A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs"],"prefix":"10.1007","author":[{"given":"Philip N.","family":"Klein","sequence":"first","affiliation":[]},{"given":"Sairam","family":"Subramanian","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"41_CR1","doi-asserted-by":"crossref","unstructured":"G. Ausiello, G.F. Italiano, A. Marchetti-Spaccamela, and U. Nanni, \u201cIncremental Algorithms for Minimal Length Paths,\u201d Proc. ACM-SIAM Symp. on Discrete Algorithms (1990), 12\u201321.","DOI":"10.1016\/0196-6774(91)90036-X"},{"key":"41_CR2","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra, \u201cA Note on Two Problems in Connexion with Graphs,\u201d Numerische Mathematik 1 (1959), 269\u2013271.","journal-title":"Numerische Mathematik"},{"key":"41_CR3","doi-asserted-by":"crossref","unstructured":"H. N. Djidev, G. E. Pantziou, and C. D. Zaroliagis, \u201cComputing Shortest Paths and Distances in Planar Graphs,\u201d Proc. 18th International Colloquium on Automata, Languages and Programming (1991), 327\u2013338.","DOI":"10.1007\/3-540-54233-7_145"},{"key":"41_CR4","first-page":"371","volume":"49","author":"S. Even","year":"1985","unstructured":"S. Even and H. Gazit, \u201cUpdating Distances in Dynamic Graphs,\u201d Methods of Operations Research 49 (1985), 371\u2013387.","journal-title":"Methods of Operations Research"},{"key":"41_CR5","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G.N. Frederickson","year":"1985","unstructured":"G.N. Frederickson, \u201cData Structures for On-Line Updating of Minimum Spanning Trees, with Applications,\u201d SIAM J. Computing 14 (1985), 781\u2013798.","journal-title":"SIAM J. Computing"},{"key":"41_CR6","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G.N. Frederickson","year":"1987","unstructured":"G.N. Frederickson, \u201cFast Algorithms for Shortest Paths in Planar Graphs, with Applications,\u201d SIAM Journal on Computing 16 (1987), 1004\u20131022.","journal-title":"SIAM Journal on Computing"},{"key":"41_CR7","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"M.L. Fredman and R.E. Tarjan, \u201cFibonacci Heaps and their Uses in Improved Network Optimization Algorithms,\u201d Journal of the Association for Computing Machinery 34 (1987), 596\u2013615.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"41_CR8","doi-asserted-by":"crossref","unstructured":"E. Fuerstein and A. Marchetti-Spaccamela, \u201cDynamic Algorithms for shortest Path Problems in Planar Graphs,\u201d Proc. 17th International Workshop on Graph Theoretic Concepts in Computer Science (1991), 187\u2013197.","DOI":"10.1007\/3-540-55121-2_18"},{"key":"41_CR9","doi-asserted-by":"crossref","unstructured":"Z. Galil and G. F. Italiano, \u201cMaintaining biconnected components of dynamic planar graphs,\u201d Proc. 18th Int. Colloquium or Automata, Languages, and Programming. (1991), 339\u2013350.","DOI":"10.1007\/3-540-54233-7_146"},{"key":"41_CR10","doi-asserted-by":"crossref","unstructured":"Z. Galil, G.F. Italiano, and N. Sarnak, \u201cFully Dynamic Planarity Testing,\u201d Proc. 24th Annual ACM Symposium on Theory of Computing (1992), 495\u2013506.","DOI":"10.1145\/129712.129761"},{"key":"41_CR11","doi-asserted-by":"crossref","unstructured":"P. N. Klein and S. Sairam, \u201cA Parallel Randomized Approximation Scheme for Shortest Paths,\u201d Proc. 24th ACM Symp. on Theory of Computing (1992), 750\u2013758.","DOI":"10.1145\/129712.129785"},{"key":"41_CR12","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"R.J. Lipton and R.E. Tarjan, \u201cA Separator Theorem for Planar Graphs,\u201d SIAM Journal of Applied Mathematics 36(1979), 177\u2013189.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"41_CR13","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"G. Miller","year":"1986","unstructured":"G. Miller, \u201cFinding Small Simple Cycle Separators for 2-Connected Planar Graphs,\u201d Journal of Computer and System Sciences 32 (1986), 265\u2013279.","journal-title":"Journal of Computer and System Sciences"},{"key":"41_CR14","unstructured":"Sairam Subramanian, \u201cParallel and Dynamic Graph Algorithms: A Combined Perspective,\u201d Department of Computer Science, Brown University, Ph.D. Thesis, 1993."},{"key":"41_CR15","doi-asserted-by":"crossref","unstructured":"Sairam Subramanian, \u201cA Fully Dynamic Data Structure For Reachability in Planar Digraphs,\u201d Department of Computer Science, Brown University, Technical report, 1993, submitted to the European Symposium on Algorithms.","DOI":"10.1007\/3-540-57273-2_72"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57155-8_269.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:08:22Z","timestamp":1605629302000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57155-8_269"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571551","9783540479185"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-57155-8_269","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}