{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:45Z","timestamp":1759638825128,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030457709"},{"type":"electronic","value":"9783030457716"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"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":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-45771-6_18","type":"book-chapter","created":{"date-parts":[[2020,4,13]],"date-time":"2020-04-13T21:03:32Z","timestamp":1586811812000},"page":"223-237","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Popular Branchings and Their Dual Certificates"],"prefix":"10.1007","author":[{"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tam\u00e1s","family":"Kir\u00e1ly","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jannik","family":"Matuschke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ildik\u00f3","family":"Schlotter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrike","family":"Schmidt-Kraepelin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,14]]},"reference":[{"issue":"4","key":"18_CR1","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1137\/06067328X","volume":"37","author":"DJ Abraham","year":"2007","unstructured":"Abraham, D.J., Irving, R.W., Kavitha, T., Mehlhorn, K.: Popular matchings. SIAM J. Comput. 37(4), 1030\u20131034 (2007)","journal-title":"SIAM J. Comput."},{"key":"18_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-642-13073-1_10","volume-title":"Algorithms and Complexity","author":"P Bir\u00f3","year":"2010","unstructured":"Bir\u00f3, P., Irving, R.W., Manlove, D.F.: Popular matchings in the marriage and roommates problems. In: Calamoneri, T., Diaz, J. (eds.) CIAC 2010. LNCS, vol. 6078, pp. 97\u2013108. Springer, Heidelberg (2010). \nhttps:\/\/doi.org\/10.1007\/978-3-642-13073-1_10"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Bloembergen, D., Grossi, D., Lackner, M.: On rational delegations in liquid democracy. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI) (2019)","DOI":"10.1609\/aaai.v33i01.33011796"},{"issue":"2","key":"18_CR4","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1111\/jopp.12065","volume":"24","author":"C Blum","year":"2016","unstructured":"Blum, C., Zuber, C.I.: Liquid democracy: Potentials, problems, and perspectives. J. Polit. Philos. 24(2), 162\u2013182 (2016)","journal-title":"J. Polit. Philos."},{"key":"18_CR5","unstructured":"Brill, M.: Interactive democracy. In: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) Blue Sky Ideas Track, pp. 1183\u20131187 (2018)"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Christoff, Z., Grossi, D.: Binary voting with delegable proxy: An analysis of liquid democracy. In: Proceedings of the 16th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), pp. 134\u2013150 (2017)","DOI":"10.4204\/EPTCS.251.10"},{"key":"18_CR7","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer Programming","author":"M Conforti","year":"2014","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Integer Programming. GTM, vol. 271. Springer, Cham (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-319-11008-0"},{"issue":"4","key":"18_CR8","doi-asserted-by":"publisher","first-page":"2348","DOI":"10.1137\/16M1076162","volume":"31","author":"\u00c1 Cseh","year":"2017","unstructured":"Cseh, \u00c1., Huang, C.C., Kavitha, T.: Popular matchings with two-sided preferences and one-sided ties. SIAM J. Disc. Math. 31(4), 2348\u20132377 (2017)","journal-title":"SIAM J. Disc. Math."},{"issue":"1","key":"18_CR9","first-page":"209","volume":"172","author":"\u00c1 Cseh","year":"2017","unstructured":"Cseh, \u00c1., Kavitha, T.: Popular edges and dominant matchings. Math. Program. 172(1), 209\u2013229 (2017)","journal-title":"Math. Program."},{"issue":"5","key":"18_CR10","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1142\/S0129054113500226","volume":"24","author":"A Darmann","year":"2013","unstructured":"Darmann, A.: Popular spanning trees. Int. J. Found. Comput. Sci. 24(5), 655\u2013677 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"18_CR11","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00186-016-0535-3","volume":"84","author":"A Darmann","year":"2016","unstructured":"Darmann, A.: It is difficult to tell if there is a Condorcet spanning tree. Math. Methods Oper. Res. 84(1), 93\u2013104 (2016). \nhttps:\/\/doi.org\/10.1007\/s00186-016-0535-3","journal-title":"Math. Methods Oper. Res."},{"issue":"4","key":"18_CR12","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s11238-010-9228-1","volume":"70","author":"A Darmann","year":"2011","unstructured":"Darmann, A., Klamler, C., Pferschy, U.: Finding socially best spanning trees. Theory Decis. 70(4), 511\u2013527 (2011)","journal-title":"Theory Decis."},{"issue":"4","key":"18_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71B","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Nat. Bureau Stan. 71B(4), 233\u2013240 (1967)","journal-title":"J. Res. Nat. Bureau Stan."},{"key":"18_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/978-3-030-30473-7_19","volume-title":"Algorithmic Game Theory","author":"B Escoffier","year":"2019","unstructured":"Escoffier, B., Gilbert, H., Pass-Lanneau, A.: The convergence of iterative delegations in liquid democracy in a social network. In: Fotakis, D., Markakis, E. (eds.) SAGT 2019. LNCS, vol. 11801, pp. 284\u2013297. Springer, Cham (2019). \nhttps:\/\/doi.org\/10.1007\/978-3-030-30473-7_19"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Kavitha, T.: Quasi-popular matchings, optimality, and extended formulations. In: Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 325\u2013344 (2020)","DOI":"10.1137\/1.9781611975994.20"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Kavitha, T., Powers, V., Zhang, X.: Popular matchings and limits to tractability. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2790\u20132809 (2019)","DOI":"10.1137\/1.9781611975482.173"},{"issue":"1","key":"18_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01580218","volume":"6","author":"DR Fulkerson","year":"1974","unstructured":"Fulkerson, D.R.: Packing rooted directed cuts in a weighted directed graph. Math. Program. 6(1), 1\u201313 (1974)","journal-title":"Math. Program."},{"issue":"1","key":"18_CR18","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"issue":"3","key":"18_CR19","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/bs.3830200304","volume":"20","author":"P G\u00e4rdenfors","year":"1975","unstructured":"G\u00e4rdenfors, P.: Match making: Assignments based on bilateral preferences. Behav. Sci. 20(3), 166\u2013173 (1975)","journal-title":"Behav. Sci."},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-030-04612-5_13","volume-title":"Web and Internet Economics","author":"P G\u00f6lz","year":"2018","unstructured":"G\u00f6lz, P., Kahng, A., Mackenzie, S., Procaccia, A.D.: The fluid mechanics of liquid democracy. In: Christodoulou, G., Harks, T. (eds.) WINE 2018. LNCS, vol. 11316, pp. 188\u2013202. Springer, Cham (2018). \nhttps:\/\/doi.org\/10.1007\/978-3-030-04612-5_13"},{"key":"18_CR21","doi-asserted-by":"crossref","unstructured":"Gupta, S., Misra, P., Saurabh, S., Zehavi, M.: Popular matching in roommates setting is NP-hard. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2810\u20132822 (2019)","DOI":"10.1137\/1.9781611975482.174"},{"key":"18_CR22","unstructured":"Hardt, S., Lopes, L.: Google votes: A liquid democracy experiment on a corporate social network. Technical report, Technical Disclosure Commons (2015)"},{"key":"18_CR23","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.ic.2012.10.012","volume":"222","author":"CC Huang","year":"2013","unstructured":"Huang, C.C., Kavitha, T.: Popular matchings in the stable marriage problem. Inf. Comput. 222, 180\u2013194 (2013)","journal-title":"Inf. Comput."},{"key":"18_CR24","doi-asserted-by":"crossref","unstructured":"Huang, C.C., Kavitha, T.: Popularity, mixed matchings, and self-duality. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2294\u20132310 (2017)","DOI":"10.1137\/1.9781611974782.151"},{"issue":"1","key":"18_CR25","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1137\/120902562","volume":"43","author":"T Kavitha","year":"2014","unstructured":"Kavitha, T.: A size-popularity tradeoff in the stable marriage problem. SIAM J. Comput. 43(1), 52\u201371 (2014)","journal-title":"SIAM J. Comput."},{"key":"18_CR26","unstructured":"Kavitha, T.: Popular half-integral matchings. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, pp. 22:1\u201322:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)"},{"key":"18_CR27","unstructured":"Kavitha, T., Kir\u00e1ly, T., Matuschke, J., Schlotter, I., Schmidt-Kraepelin, U.: Popular branchings and their dual certificates. Technical report 1912.01854 (2019). \nhttps:\/\/arxiv.org\/abs\/1912.01854"},{"issue":"24","key":"18_CR28","doi-asserted-by":"publisher","first-page":"2679","DOI":"10.1016\/j.tcs.2010.03.028","volume":"412","author":"T Kavitha","year":"2011","unstructured":"Kavitha, T., Mestre, J., Nasre, M.: Popular mixed matchings. Theor. Comput. Sci. 412(24), 2679\u20132690 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial Optimization","author":"B Korte","year":"2012","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-24488-9"},{"key":"18_CR30","unstructured":"Kotsialou, G., Riley, L.: Incentivising participation in liquid democracy with breadth first delegation. Technical report 1811.03710 (2018). \nhttps:\/\/arxiv.org\/abs\/1811.03710"},{"key":"18_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/978-3-540-78773-0_51","volume-title":"LATIN 2008: Theoretical Informatics","author":"RM McCutchen","year":"2008","unstructured":"McCutchen, R.M.: The least-unpopularity-factor and least-unpopularity-margin criteria for matching problems with one-sided preferences. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 593\u2013604. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-78773-0_51"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-45771-6_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T23:10:36Z","timestamp":1589929836000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-45771-6_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030457709","9783030457716"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-45771-6_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"14 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"London","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.xixilogic.org\/events\/clar2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"126","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":"33","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":"0","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":"26% - 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":"26","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)"}}]}}