{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,22]],"date-time":"2026-07-22T16:28:31Z","timestamp":1784737711544,"version":"3.55.0"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,11,20]],"date-time":"2018-11-20T00:00:00Z","timestamp":1542672000000},"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":["Algorithmica"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s00453-018-0528-0","type":"journal-article","created":{"date-parts":[[2018,11,20]],"date-time":"2018-11-20T10:56:30Z","timestamp":1542711390000},"page":"245-259","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A Simple Greedy Algorithm for Dynamic Graph Orientation"],"prefix":"10.1007","volume":"82","author":[{"given":"Edvin","family":"Berglin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,11,20]]},"reference":[{"key":"528_CR1","unstructured":"Berglin, E.: Geometric covers, graph orientations, counter games. Ph.D. thesis, Aarhus University (2017)"},{"key":"528_CR2","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Stein, C.: Fully dynamic matching in bipartite graphs. In: International Colloquium on Automata, Languages, and Programming, pp. 167\u2013179. Springer (2015)","DOI":"10.1007\/978-3-662-47672-7_14"},{"key":"528_CR3","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Stein, C.: Faster fully dynamic matchings with small approximation ratios. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 692\u2013711. Society for Industrial and Applied Mathematics (2016)","DOI":"10.1137\/1.9781611974331.ch50"},{"key":"528_CR4","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R.: Dynamic representation of sparse graphs. In: Proceedings 6th International Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science, vol. 1663, pp. 342\u2013351. Springer (1999)","DOI":"10.1007\/3-540-48447-7_34"},{"key":"528_CR5","doi-asserted-by":"crossref","unstructured":"Dietz, P., Sleator, D.: Two algorithms for maintaining order in a list. In: Proceedings 19th Annual ACM Symposium on Theory of Computing (STOC), pp. 365\u2013372. ACM (1987)","DOI":"10.1145\/28395.28434"},{"key":"528_CR6","doi-asserted-by":"crossref","unstructured":"He, M., Tang, G., Zeh, N.: Orienting dynamic graphs, with applications to maximal matchings and adjacency queries. In: Proceedings 25th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science, vol. 8889, pp. 128\u2013140. Springer (2014)","DOI":"10.1007\/978-3-319-13075-0_11"},{"issue":"4","key":"528_CR7","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/0405049","volume":"5","author":"S Kannan","year":"1992","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discrete Math. 5(4), 596\u2013603 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"528_CR8","doi-asserted-by":"crossref","unstructured":"Kopelowitz, T., Krauthgamer, R., Porat, E., Solomon, S.: Orienting fully dynamic graphs with worst-case time bounds. In: Proceedings 41st International Colloquium Automata, Languages, and Programming (ICALP), Part II, Lecture Notes in Computer Science, vol. 8573, pp. 532\u2013543. Springer (2014)","DOI":"10.1007\/978-3-662-43951-7_45"},{"issue":"5","key":"528_CR9","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.ipl.2006.12.006","volume":"102","author":"\u0141 Kowalik","year":"2007","unstructured":"Kowalik, \u0141.: Adjacency queries in dynamic sparse graphs. Inf. Process. Lett. 102(5), 191\u2013195 (2007)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"528_CR10","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF00299635","volume":"26","author":"C Levcopoulos","year":"1988","unstructured":"Levcopoulos, C., Overmars, M.H.: A balanced search tree with $$O(1)$$ O ( 1 ) worst-case update time. Acta Inform. 26(3), 269\u2013277 (1988)","journal-title":"Acta Inform."},{"issue":"1","key":"528_CR11","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/2700206","volume":"12","author":"O Neiman","year":"2016","unstructured":"Neiman, O., Solomon, S.: Simple deterministic algorithms for fully dynamic maximal matching. ACM Trans. Algorithms 12(1), 7 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"528_CR12","doi-asserted-by":"crossref","unstructured":"Peleg, D., Solomon, S.: Dynamic ( $$1+ \\varepsilon $$ 1 + \u03b5 )-approximate matchings: a density-sensitive approach. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 712\u2013729. Society for Industrial and Applied Mathematics (2016)","DOI":"10.1137\/1.9781611974331.ch51"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0528-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0528-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0528-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,15]],"date-time":"2020-11-15T16:13:46Z","timestamp":1605456826000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0528-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,20]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["528"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0528-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,20]]},"assertion":[{"value":"9 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}