乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T17:08:41Z","timestamp":1722877721202},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2004,11]]},"abstract":"\n It is shown that a planar digraph can be preprocessed in near-linear time, producing a near-linear space oracle that can answer reachability queries in constant time. The oracle can be distributed as an\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n ) space label for each vertex and then we can determine if one vertex can reach another considering their two labels only.The approach generalizes to give a near-linear space approximate distances oracle for a weighted planar digraph. With weights drawn from {0, \u2026,\n N<\/jats:italic>\n }, it approximates distances within a factor (1 + \u03b5) in\n O<\/jats:italic>\n (log log (\n nN<\/jats:italic>\n ) + 1\/\u03b5) time. Our scheme can be extended to find and route along correspondingly short dipaths.\n <\/jats:p>","DOI":"10.1145\/1039488.1039493","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T16:35:53Z","timestamp":1106757353000},"page":"993-1024","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":151,"title":["Compact oracles for reachability and approximate distances in planar digraphs"],"prefix":"10.1145","volume":"51","author":[{"given":"Mikkel","family":"Thorup","sequence":"first","affiliation":[{"name":"AT&T Labs---Research, Florham Park, New Jersey"}]}],"member":"320","published-online":{"date-parts":[[2004,11]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 4th European Symposium on Algorithms","volume":"1136","author":"Arikati S."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Chen D.","year":"1995"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (Portland, Ore.). ACM","author":"Chen D."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science","volume":"1197","author":"Djidjev H.","year":"1996"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 18th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science","volume":"1991","author":"Djidjev H."},{"key":"e_1_2_1_6_1","volume-title":"Proceeding of 10th International Symposium on Fundamentals of Computation Theory. Lecture Notes in Computer Science","volume":"965","author":"Djidjev H."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, D.C.). ACM","author":"Gavoille C."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Alamitos, Calif., 148--157","author":"Gupta A."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 15th ACM Symposium on Parallel Algorithms. ACM","author":"Gupta A."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1171"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 31th Annual ACM Symposium on Theory of Computing (Atlanta, Ga.). ACM","author":"Indyk P.","year":"1999"},{"key":"e_1_2_1_16_1","unstructured":"Kernighan B. and Ritchie D. 1988. The C Programming Language Second ed. Prentice-Hall.]] Kernighan B. and Ritchie D. 1988. The C Programming Language Second ed. Prentice-Hall.]]"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Klein P.","year":"2002"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/PL00009223","article-title":"A fully dynamic approximation scheme for shortest path problems in planar graphs","volume":"23","author":"Klein P.","year":"1998","journal-title":"Algorithmica"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton R.","year":"1979","journal-title":"SIAM J. Appl. Math."},{"key":"e_1_2_1_20_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 25th Mathematical Foundations of Computer Science (Bratislava, Slovak Republik)","author":"Peleg D."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(200003)33:3%26lt;%26gt;1.0.CO;2-Y"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1093\/comjnl\/28.1.5","article-title":"Labelling and implicit routing in networks","volume":"28","author":"Santoro N.","year":"1985","journal-title":"Comput. J."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 1st European Symposium on Algorithms","volume":"726","author":"Subramanian S.","year":"1993"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90164-O"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1017\/S0963548300001668","article-title":"Shortcutting planar digraphs","volume":"4","author":"Thorup M.","year":"1995","journal-title":"Combin., Prob. Comput."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/316542.316548"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288246"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 33th Annual ACM Symposium on Theory of Computing","author":"Thorup M."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures","author":"Thorup M."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"van Leeuwen J. and Tan R. 1986. Computer networks with compact routing tables. In The book of L G. Rozenberg and A. Salomaa Eds. Springer-Verlag New York 259--273.]] van Leeuwen J. and Tan R. 1986. Computer networks with compact routing tables. In The book of L G. Rozenberg and A. Salomaa Eds. Springer-Verlag New York 259--273.]]","DOI":"10.1007\/978-3-642-95486-3_22"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"Williams J.","year":"1964","journal-title":"Heapsort. Commun. ACM"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1039488.1039493","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T15:49:16Z","timestamp":1672242556000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1039488.1039493"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,11]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2004,11]]}},"alternative-id":["10.1145\/1039488.1039493"],"URL":"https:\/\/doi.org\/10.1145\/1039488.1039493","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,11]]},"assertion":[{"value":"2004-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}