{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T04:27:23Z","timestamp":1748492843665,"version":"3.40.3"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031306747"},{"type":"electronic","value":"9783031306754"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-30675-4_10","type":"book-chapter","created":{"date-parts":[[2023,4,14]],"date-time":"2023-04-14T10:02:24Z","timestamp":1681466544000},"page":"137-153","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Edge Coloring on\u00a0Dynamic Graphs"],"prefix":"10.1007","author":[{"given":"Zhepeng","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Long","family":"Yuan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haofei","family":"Sui","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zi","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shiyu","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianye","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,4,15]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Archer, A., Lattanzi, S., Likarish, P., Vassilvitskii, S.: Indexing public-private graphs. In: Proceedings of the WWW, pp. 1461\u20131470 (2017)","DOI":"10.1145\/3038912.3052683"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Distributed graph coloring: fundamentals and recent developments. In: Synthesis Lectures on Distributed Computing Theory (2013)","DOI":"10.1007\/978-3-031-02009-4"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Maimon, T.: Fully-dynamic graph algorithms with sublinear time inspired by distributed computing. In: Proceedings of ICCS, pp. 89\u201398 (2017)","DOI":"10.1016\/j.procs.2017.05.098"},{"issue":"2","key":"10_CR4","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10_CR5","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/s10479-018-2977-x","volume":"286","author":"F Borghini","year":"2020","unstructured":"Borghini, F., M\u00e9ndez-D\u00edaz, I., Zabala, P.: An exact algorithm for the edge coloring by total labeling problem. Ann. Oper. Res. 286(1), 11\u201331 (2020)","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"10_CR6","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s00373-018-1986-5","volume":"35","author":"Y Cao","year":"2019","unstructured":"Cao, Y., Chen, G., Jing, G., Stiebitz, M., Toft, B.: Graph edge coloring: a survey. Graphs Comb. 35(1), 33\u201366 (2019)","journal-title":"Graphs Comb."},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Cheng, M., Yin, L.: Transmission scheduling in sensor networks via directed edge coloring. In: IEEE International Conference on Communications, pp. 3710\u20133715 (2007)","DOI":"10.1109\/ICC.2007.611"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Epasto, A., Kumar, R., Lattanzi, S.: Efficient algorithms for public-private social networks. In: Proceedings of KDD, pp. 139\u2013148 (2015)","DOI":"10.1145\/2783258.2783354"},{"issue":"3","key":"10_CR9","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s00453-007-9044-3","volume":"50","author":"R Cole","year":"2008","unstructured":"Cole, R., Kowalik, L.: New linear-time algorithms for edge-coloring planar graphs. Algorithmica 50(3), 351\u2013368 (2008)","journal-title":"Algorithmica"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Duan, R., He, H., Zhang, T.: Dynamic edge coloring with improved approximation. In: Chan, T.M. (ed.) Proceedings of SODA, pp. 1937\u20131945 (2019)","DOI":"10.1137\/1.9781611975482.117"},{"issue":"8","key":"10_CR11","doi-asserted-by":"publisher","first-page":"1261","DOI":"10.14778\/3389133.3389142","volume":"13","author":"W Fan","year":"2020","unstructured":"Fan, W., Liu, M., Tian, C., Ruiqi, X., Zhou, J.: Incrementalization of graph partitioning algorithms. Proc. VLDB Endow. 13(8), 1261\u20131274 (2020)","journal-title":"Proc. VLDB Endow."},{"issue":"2","key":"10_CR12","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/3500930","volume":"47","author":"W Fan","year":"2022","unstructured":"Fan, W., Tian, C.: Incremental graph computations: doable and undoable. ACM Trans. Database Syst. 47(2), 6:1-6:44 (2022)","journal-title":"ACM Trans. Database Syst."},{"issue":"1","key":"10_CR13","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1137\/0211009","volume":"11","author":"HN Gabow","year":"1982","unstructured":"Gabow, H.N., Kariv, O.: Algorithms for edge coloring bipartite graphs and multigraphs. SIAM J. Comput. 11(1), 117\u2013129 (1982)","journal-title":"SIAM J. Comput."},{"issue":"8","key":"10_CR14","doi-asserted-by":"publisher","first-page":"1122","DOI":"10.1016\/j.jpdc.2007.12.006","volume":"68","author":"S Gandham","year":"2008","unstructured":"Gandham, S., Dawande, M., Prakash, R.: Link scheduling in wireless sensor networks: Distributed edge-coloring revisited. J. Parallel Distrib. Comput. 68(8), 1122\u20131134 (2008)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"2","key":"10_CR15","doi-asserted-by":"publisher","first-page":"169","DOI":"10.14778\/3489496.3489499","volume":"15","author":"K Hao","year":"2021","unstructured":"Hao, K., Yuan, L., Zhang, W.: Distributed hop-constrained s-t simple path enumeration at billion scale. Proc. VLDB Endow. 15(2), 169\u2013182 (2021)","journal-title":"Proc. VLDB Endow."},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Hilgemeier, M., Drechsler, N., Drechsler, R.: Fast heuristics for the edge coloring of large graphs. In: Proceedings of DSD, pp. 230\u2013239 (2003)","DOI":"10.1109\/DSD.2003.1231932"},{"issue":"4","key":"10_CR17","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The np-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10_CR18","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0196-6774(87)90026-5","volume":"8","author":"HJ Karloff","year":"1987","unstructured":"Karloff, H.J., Shmoys, D.B.: Efficient parallel algorithms for edge coloring problems. J. Algorithms 8(1), 39\u201352 (1987)","journal-title":"J. Algorithms"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Khurana, U., Nguyen, V.-A., Cheng, H.-C., (Stephen) Chen, X., Shneiderman, B.: Visual analysis of temporal trends in social networks using edge color coding and metric timelines. In: Proceedings of IEEE PASSAT\/SocialCom, pp. 549\u2013554 (2011)","DOI":"10.1109\/PASSAT\/SocialCom.2011.212"},{"issue":"38\u201340","key":"10_CR20","doi-asserted-by":"publisher","first-page":"3733","DOI":"10.1016\/j.tcs.2009.05.005","volume":"410","author":"L Kowalik","year":"2009","unstructured":"Kowalik, L.: Improved edge-coloring with three colors. Theor. Comput. Sci. 410(38\u201340), 3733\u20133742 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Liu, B., Yuan, L., Lin, X., Qin, L., Zhang, W.: Efficient ($$\\alpha $$, $$\\beta $$)-core computation: an index-based approach. In: Proceedings of WWW, pp. 1130\u20131141 (2019)","DOI":"10.1145\/3308558.3313522"},{"issue":"5","key":"10_CR22","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1007\/s00778-020-00606-9","volume":"29","author":"B Liu","year":"2020","unstructured":"Liu, B., Yuan, L., Lin, X., Qin, L., Zhang, W., Zhou, J.: Efficient ($$\\alpha $$, $$\\beta $$)-core computation in bipartite graphs. VLDB J. 29(5), 1075\u20131099 (2020). https:\/\/doi.org\/10.1007\/s00778-020-00606-9","journal-title":"VLDB J."},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"Meng, L., Yuan, L., Chen,Z., Lin, X., Yang, S.: Index-based structural clustering on directed graphs. In: Proceedings of ICDE, pp. 2831\u20132844 (2022)","DOI":"10.1109\/ICDE53745.2022.00257"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Misra, J., Gries, D.: A constructive proof of vizing\u2019s theorem. In: Information Processing Letters (1992)","DOI":"10.1016\/0020-0190(92)90041-S"},{"issue":"6","key":"10_CR25","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0167-6377(91)90003-8","volume":"10","author":"GL Nemhauser","year":"1991","unstructured":"Nemhauser, G.L., Park, S.: A polyhedral approach to edge coloring. Oper. Res. Lett. 10(6), 315\u2013322 (1991)","journal-title":"Oper. Res. Lett."},{"key":"10_CR26","doi-asserted-by":"crossref","unstructured":"Ohsaka, N., Maehara, T., Kawarabayashi, K.: Efficient pagerank tracking in evolving networks. In: Proceedings of SIGKDD, pp. 875\u2013884 (2015)","DOI":"10.1145\/2783258.2783297"},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"Ramalingam, G., Reps, T.W.: On the computational complexity of dynamic graph problems. Theor. Comput. Sci. 158(1 &2), 233\u2013277 (1996)","DOI":"10.1016\/0304-3975(95)00079-8"},{"key":"10_CR28","unstructured":"Saberi, A., Wajc, D.: The greedy algorithm is not optimal for on-line edge coloring. In: Proceedings of ICALP, pp. 109:1\u2013109:18 (2021)"},{"issue":"1","key":"10_CR29","first-page":"37","volume":"1","author":"A Sameh","year":"2013","unstructured":"Sameh, A.: A twitter analytic tool to measure opinion, influence and trust. J. Ind. Intell. Inf. 1(1), 37\u201345 (2013)","journal-title":"J. Ind. Intell. Inf."},{"key":"10_CR30","unstructured":"Sanders, P., Steurer, D.: An asymptotic approximation scheme for multigraph edge coloring. In: Proceedings of SODA, pp. 897\u2013906 (2005)"},{"key":"10_CR31","first-page":"25","volume":"3","author":"VG Vizing","year":"1964","unstructured":"Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Discret. Analiz 3, 25\u201330 (1964)","journal-title":"Discret. Analiz"},{"key":"10_CR32","doi-asserted-by":"crossref","unstructured":"Yang, B., Sato, I., Nakagawa, H.: Privacy-preserving EM algorithm for clustering on social network. In: Proceedings of PAKDD, pp. 542\u2013553 (2012)","DOI":"10.1007\/978-3-642-30217-6_45"},{"issue":"2","key":"10_CR33","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s00778-015-0408-z","volume":"25","author":"L Long Yuan","year":"2016","unstructured":"Long Yuan, L., Qin, X.L., Chang, L., Zhang, W.: Diversified top-k clique search. VLDB J. 25(2), 171\u2013196 (2016)","journal-title":"VLDB J."},{"issue":"3","key":"10_CR34","doi-asserted-by":"publisher","first-page":"338","DOI":"10.14778\/3157794.3157802","volume":"11","author":"L Long Yuan","year":"2017","unstructured":"Long Yuan, L., Qin, X.L., Chang, L., Zhang, W.: Effective and efficient dynamic graph coloring. Proc. VLDB Endow. 11(3), 338\u2013351 (2017)","journal-title":"Proc. VLDB Endow."},{"issue":"5","key":"10_CR35","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1109\/TKDE.2017.2783933","volume":"30","author":"L Long Yuan","year":"2018","unstructured":"Long Yuan, L., Qin, W.Z., Chang, L., Yang, J.: Index-based densest clique percolation community search in networks. IEEE Trans. Knowl. Data Eng. 30(5), 922\u2013935 (2018)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"11","key":"10_CR36","doi-asserted-by":"publisher","first-page":"2640","DOI":"10.14778\/3551793.3551820","volume":"15","author":"J Zhang","year":"2022","unstructured":"Zhang, J., Li, W., Yuan, L., Qin, L., Zhang, Y., Chang, L.: Shortest-path queries on complex networks: experiments, analyses, and improvement. Proc. VLDB Endow. 15(11), 2640\u20132652 (2022)","journal-title":"Proc. VLDB Endow."},{"key":"10_CR37","doi-asserted-by":"crossref","unstructured":"Zhang, J., Yuan, L., Li, W., Qin, L., Zhang, Y.: Efficient label-constrained shortest path queries on road networks: a tree decomposition approach. Proc. VLDB Endow. 15(3), 686\u2013698 (2021)","DOI":"10.14778\/3494124.3494148"},{"issue":"3","key":"10_CR38","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1006\/jagm.1996.0061","volume":"21","author":"X Zhou","year":"1996","unstructured":"Zhou, X., Nakano, S.-I., Nishizeki, T.: Edge-coloring partial k-trees. J. Algorithms 21(3), 598\u2013617 (1996)","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Database Systems for Advanced Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30675-4_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T12:07:46Z","timestamp":1710245266000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30675-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031306747","9783031306754"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30675-4_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"15 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DASFAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Database Systems for Advanced Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Tianjin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 April 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 April 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dasfaa2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.tjudb.cn\/dasfaa2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Microsoft CMT","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"652","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"125","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"66","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"19% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7.3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}