{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:18:03Z","timestamp":1761621483246},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030340285"},{"type":"electronic","value":"9783030340292"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[[2019]]},"DOI":"10.1007\/978-3-030-34029-2_12","type":"book-chapter","created":{"date-parts":[[2019,11,13]],"date-time":"2019-11-13T22:02:40Z","timestamp":1573682560000},"page":"167-183","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Constraint Generation Algorithm for the Minimum Connectivity Inference Problem"],"prefix":"10.1007","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diana-Elena","family":"F\u0103l\u0103ma\u015f","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R\u00e9mi","family":"Watrigant","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,14]]},"reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/978-3-642-40450-4_25","volume-title":"Algorithms \u2013 ESA 2013","author":"D Agarwal","year":"2013","unstructured":"Agarwal, D., Araujo, J.-C.S., Caillouet, C., Cazals, F., Coudert, D., P\u00e9rennes, S.: Connectivity inference in mass spectrometry based structure determination. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 289\u2013300. Springer, Heidelberg (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-642-40450-4_25"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"2274","DOI":"10.1074\/mcp.M114.047779","volume":"14","author":"D Agarwal","year":"2015","unstructured":"Agarwal, D., Ara\u00fajo, J.C.S., Caillouet, C., Cazals, F., Coudert, D., P\u00e9rennes, S.: Unveiling contacts within macro-molecular assemblies by solving minimum weight connectivity inference problems. Mol. Cell. Proteomics 14, 2274\u20132284 (2015)","journal-title":"Mol. Cell. Proteomics"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-642-16108-7_12","volume-title":"Algorithmic Learning Theory","author":"D Angluin","year":"2010","unstructured":"Angluin, D., Aspnes, J., Reyzin, L.: Inferring social networks from outbreaks. In: Hutter, M., Stephan, F., Vovk, V., Zeugmann, T. (eds.) ALT 2010. LNCS (LNAI), vol. 6331, pp. 104\u2013118. Springer, Heidelberg (2010). \nhttps:\/\/doi.org\/10.1007\/978-3-642-16108-7_12"},{"issue":"1","key":"12_CR4","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/BF01386316","volume":"4","author":"JF Benders","year":"1962","unstructured":"Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1), 238\u2013252 (1962)","journal-title":"Numerische Mathematik"},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.jda.2011.12.009","volume":"14","author":"U Brandes","year":"2012","unstructured":"Brandes, U., Cornelsen, S., Pampel, B., Sallaberry, A.: Path-based supports for hypergraphs. J. Discrete Algorithms 14, 248\u2013261 (2012). Proceedings of the 21st International Workshop on Combinatorial Algorithms (IWOCA 2010)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"12_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/140955057","volume":"29","author":"J Chen","year":"2015","unstructured":"Chen, J., Komusiewicz, C., Niedermeier, R., Sorge, M., Such\u00fd, O., Weller, M.: Polynomial-time data reduction for the subset interconnection design problem. SIAM J. Discrete Math. 29(1), 1\u201325 (2015)","journal-title":"SIAM J. Discrete Math."},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Chockler, G., Melamed, R., Tock, Y., Vitenberg, R.: Constructing scalable overlays for pub-sub with many topics. In: Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing (PODC 2007), pp. 109\u2013118 (2007)","DOI":"10.1145\/1281100.1281118"},{"key":"12_CR8","unstructured":"Conitzer, V., Derryberry, J., Sandholm, T.: Combinatorial auctions with structured item graphs. In: Proceedings of the 19th National Conference on Artifical Intelligence, AAAI 2004, pp. 212\u2013218 (2004)"},{"key":"12_CR9","series-title":"Advances in Mechanics and Mathematics","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-030-02487-1_7","volume-title":"Advances in Mathematical Methods and High Performance Computing","author":"MA Dar","year":"2019","unstructured":"Dar, M.A., Fischer, A., Martinovic, J., Scheithauer, G.: A computational study of reduction techniques for the minimum connectivity inference problem. In: Singh, V.K., Gao, D., Fischer, A. (eds.) Advances in Mathematical Methods and High Performance Computing. AMM, vol. 41, pp. 135\u2013148. Springer, Cham (2019). \nhttps:\/\/doi.org\/10.1007\/978-3-030-02487-1_7"},{"issue":"0","key":"12_CR10","first-page":"1","volume":"0","author":"MA Dar","year":"2018","unstructured":"Dar, M.A., Fischer, A., Martinovic, J., Scheithauer, G.: An improved flow-based formulation and reduction principles for the minimum connectivity inference problem. Optimization 0(0), 1\u201321 (2018)","journal-title":"Optimization"},{"issue":"4","key":"12_CR11","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0401042","volume":"1","author":"DZ Du","year":"1988","unstructured":"Du, D.Z., Miller, Z.: Matroids and subset interconnection design. SIAM J. Discrete Math. 1(4), 416\u2013424 (1988)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"12_CR12","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01096768","volume":"6","author":"DZ Du","year":"1995","unstructured":"Du, D.Z., Miller, Z.: On complexity of subset interconnection designs. J. Global Optim. 6(2), 193\u2013205 (1995)","journal-title":"J. Global Optim."},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-540-85097-7_19","volume-title":"Combinatorial Optimization and Applications","author":"H Fan","year":"2008","unstructured":"Fan, H., Hundt, C., Wu, Y.-L., Ernst, J.: Algorithms and implementation for interconnection graph problem. In: Yang, B., Du, D.-Z., Wang, C.A. (eds.) COCOA 2008. LNCS, vol. 5165, pp. 201\u2013210. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-85097-7_19"},{"issue":"2","key":"12_CR14","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"12_CR15","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.tcs.2011.12.033","volume":"429","author":"J Hosoda","year":"2012","unstructured":"Hosoda, J., Hromkovi\u010d, J., Izumi, T., Ono, H., Steinov\u00e1, M., Wada, K.: On the approximability and hardness of minimum topic connected overlay and its special instances. Theoret. Comput. Sci. 429, 144\u2013154 (2012)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"12_CR16","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1002\/jgt.3190110306","volume":"11","author":"DS Johnson","year":"1987","unstructured":"Johnson, D.S., Pollak, H.O.: Hypergraph planarity and the complexity of drawing venn diagrams. J. Graph Theory 11(3), 309\u2013325 (1987)","journal-title":"J. Graph Theory"},{"key":"12_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/978-3-319-08404-6_23","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"B Klemz","year":"2014","unstructured":"Klemz, B., Mchedlidze, T., N\u00f6llenburg, M.: Minimum tree supports for hypergraphs and low-concurrency Euler diagrams. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 265\u2013276. Springer, Cham (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-319-08404-6_23"},{"issue":"1","key":"12_CR18","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s10107-003-0410-x","volume":"98","author":"E Korach","year":"2003","unstructured":"Korach, E., Stern, M.: The clustering matroid and the optimal clustering tree. Math. Program. 98(1), 385\u2013414 (2003)","journal-title":"Math. Program."},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"Onus, M., Richa, A.W.: Minimum maximum degree publish-subscribe overlay network design. In: IEEE INFOCOM 2009, pp. 882\u2013890 (2009)","DOI":"10.1109\/INFCOM.2009.5061998"}],"container-title":["Lecture Notes in Computer Science","Analysis of Experimental Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-34029-2_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,11,13]],"date-time":"2019-11-13T22:08:54Z","timestamp":1573682934000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-34029-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030340285","9783030340292"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-34029-2_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"14 November 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SEA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Experimental Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kalamata","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 June 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wea2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.caopt.com\/SEA2019\/","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":"45","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":"35","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":"78% - 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":"2","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":"2","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)"}}]}}