{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T17:41:35Z","timestamp":1683740495561},"reference-count":8,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2007,2]]},"abstract":"<jats:p>We show that two data structures, min-augmented range tree and priority search pennant, efficiently support all the required operations for updatable IP router tables and argue that both structures are better suited for the one-dimensional dynamic IP lookup problem than the priority search tree (PST) used in a previous solution. It is possible to maintain both structures in time O(1) after a rotation, while PST with n elements may require \u03a9( log n) steps for a single rotation. Therefore, the proposed structures can be balanced using a larger class of rebalancing schemes compared to PST. Both structures are also of interest independently of the IP lookup problem and may be used as attractive implementations of priority search queues in other contexts as well.<\/jats:p>","DOI":"10.1142\/s0129054107004607","type":"journal-article","created":{"date-parts":[[2007,2,7]],"date-time":"2007-02-07T12:42:34Z","timestamp":1170852154000},"page":"139-161","source":"Crossref","is-referenced-by-count":2,"title":["UPDATE-EFFICIENT DATA STRUCTURES FOR DYNAMIC IP ROUTER TABLES"],"prefix":"10.1142","volume":"18","author":[{"given":"TOBIAS","family":"LAUER","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Albert-Ludwigs-Universit\u00e4t Freiburg, Georges-K\u00f6hler-Allee, Geb\u00e4ude 51, 79110 Freiburg im Breisgau, Germany"}]},{"given":"THOMAS","family":"OTTMANN","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Albert-Ludwigs-Universit\u00e4t Freiburg, Georges-K\u00f6hler-Allee, Geb\u00e4ude 51, 79110 Freiburg im Breisgau, Germany"}]},{"given":"AMITAVA","family":"DATTA","sequence":"additional","affiliation":[{"name":"School of Computer Science &amp; Software Engineering, University of Western Australia, 35 Stirling Highway, Crawley, Perth, WA 6009, Australia"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1145\/358476.358509"},{"key":"rf3","doi-asserted-by":"crossref","unstructured":"P.\u00a0Gupta, Handbook of Data Structures and Applications, eds. D. P.\u00a0Mehta and S.\u00a0Sahni (Chapman & Hall\/CRC, Boca Raton, 2005)\u00a0p. 49-1-20.","DOI":"10.1201\/9781420035179.ch49"},{"key":"rf5","first-page":"1217","volume":"53","author":"Lu H.","journal-title":"IEEE Trans. Cornput."},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/PL00013303"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69900-9"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1109\/65.912716"},{"key":"rf10","doi-asserted-by":"crossref","unstructured":"S.\u00a0Sahni, K. S.\u00a0Kim and H.\u00a0Lu, Handbook of Data Structures and Applications, eds. D. P.\u00a0Mehta and S.\u00a0Sahni (Chapman & Hall\/CRC, Boca Raton, 2005)\u00a0p. 48-1-24.","DOI":"10.1201\/9781420035179.pt7"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054107004607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T17:08:43Z","timestamp":1683738523000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054107004607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2]]},"references-count":8,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2007,2]]}},"alternative-id":["10.1142\/S0129054107004607"],"URL":"https:\/\/doi.org\/10.1142\/s0129054107004607","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,2]]}}}