{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:02Z","timestamp":1759638422735},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439500"},{"type":"electronic","value":"9783662439517"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_45","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T08:37:49Z","timestamp":1402475869000},"page":"532-543","source":"Crossref","is-referenced-by-count":14,"title":["Orienting Fully Dynamic Graphs with Worst-Case Time Bounds"],"prefix":"10.1007","author":[{"given":"Tsvi","family":"Kopelowitz","sequence":"first","affiliation":[]},{"given":"Robert","family":"Krauthgamer","sequence":"additional","affiliation":[]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"45_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM\u00a042, 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"45_CR2","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0304-3975(91)90020-3","volume":"86","author":"M. Chrobak","year":"1991","unstructured":"Chrobak, M., Eppstein, D.: Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci.\u00a086, 243\u2013266 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"45_CR3","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R.: Dynamic representation of sparse graphs. In: 6th International Workshop on Algorithms and Data Structures, WADS, pp. 342\u2013351 (1999)","DOI":"10.1007\/3-540-48447-7_34"},{"key":"45_CR4","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.ipl.2006.12.006","volume":"102","author":"L. Kowalik","year":"2007","unstructured":"Kowalik, L.: Adjacency queries in dynamic sparse graphs. Inf. Process. Lett.\u00a0102, 191\u2013195 (2007)","journal-title":"Inf. Process. Lett."},{"key":"45_CR5","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1145\/1159892.1159895","volume":"2","author":"L. Kowalik","year":"2006","unstructured":"Kowalik, L., Kurowski, M.: Oracles for bounded-length shortest paths in planar graphs. ACM Transactions on Algorithms\u00a02, 335\u2013363 (2006)","journal-title":"ACM Transactions on Algorithms"},{"key":"45_CR6","unstructured":"Cain, J.A., Sanders, P., Wormald, N.: The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation. In: 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 469\u2013476. SIAM (2007)"},{"key":"45_CR7","doi-asserted-by":"crossref","unstructured":"Neiman, O., Solomon, S.: Simple deterministic algorithms for fully dynamic maximal matching. In: Proc. of 45th STOC, pp. 745\u2013754 (2013)","DOI":"10.1145\/2488608.2488703"},{"key":"45_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1007\/978-3-642-40104-6_27","volume-title":"Algorithms and Data Structures","author":"Z. Dvo\u0159\u00e1k","year":"2013","unstructured":"Dvo\u0159\u00e1k, Z., T\u016fma, V.: A dynamic data structure for counting subgraphs in sparse graphs. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol.\u00a08037, pp. 304\u2013315. Springer, Heidelberg (2013)"},{"key":"45_CR9","doi-asserted-by":"crossref","unstructured":"Eisenstat, D., Klein, P.N., Mathieu, C.: An efficient polynomial-time approximation scheme for steiner forest in planar graphs. In: Proc. of SODA, pp. 626\u2013638 (2012)","DOI":"10.1137\/1.9781611973099.53"},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: All maximal independent sets and dynamic dominance for sparse graphs. ACM Transactions on Algorithms\u00a05 (2009)","DOI":"10.1145\/1597036.1597042"},{"issue":"1","key":"45_CR11","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"36","author":"C.S.J.A. Nash-Williams","year":"1961","unstructured":"Nash-Williams, C.S.J.A.: Edge-disjoint spanning trees in finite graphs. Journal of the London Mathematical Society\u00a036(1), 445\u2013450 (1961)","journal-title":"Journal of the London Mathematical Society"},{"issue":"1","key":"45_CR12","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1112\/jlms\/s1-39.1.12","volume":"39","author":"C.S.J.A. Nash-Williams","year":"1964","unstructured":"Nash-Williams, C.S.J.A.: Decomposition of finite graphs into forests. Journal of the London Mathematical Society\u00a039(1), 12 (1964)","journal-title":"Journal of the London Mathematical Society"},{"key":"45_CR13","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF01758774","volume":"7","author":"H.N. Gabow","year":"1992","unstructured":"Gabow, H.N., Westermann, H.H.: Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica\u00a07, 465\u2013497 (1992)","journal-title":"Algorithmica"},{"key":"45_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0166-218X(97)00007-3","volume":"78","author":"S.R. Arikati","year":"1997","unstructured":"Arikati, S.R., Maheshwari, A., Zaroliagis, C.D.: Efficient computation of implicit representations of sparse graphs. Discrete Appl. Math.\u00a078, 1\u201316 (1997)","journal-title":"Discrete Appl. Math."},{"key":"45_CR15","unstructured":"Erickson, J.: (2006), \n                    \n                      http:\/\/www.cs.uiuc.edu\/~jeffe\/teaching\/datastructures\/2006\/problems\/Bill-arboricity.pdf\n                    \n                    \n                   (retrieved November 2013)"},{"key":"45_CR16","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A., Stein, C.: Maintaining assignments online: Matching, scheduling, and flows. In: Chekuri, C. (ed.) SODA, pp. 468\u2013479. SIAM (2014)","DOI":"10.1137\/1.9781611973402.35"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43951-7_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:24:25Z","timestamp":1558923865000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}