{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T04:44:35Z","timestamp":1773377075025,"version":"3.50.1"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031151453","type":"print"},{"value":"9783031151460","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-15146-0_2","type":"book-chapter","created":{"date-parts":[[2022,9,6]],"date-time":"2022-09-06T23:02:27Z","timestamp":1662505347000},"page":"20-36","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On Computing Optimal Linear Diagrams"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0712-9726","authenticated-orcid":false,"given":"Alexander","family":"Dobler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0454-3937","authenticated-orcid":false,"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,9,7]]},"reference":[{"issue":"1","key":"2_CR1","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1111\/cgf.12722","volume":"35","author":"B Alsallakh","year":"2016","unstructured":"Alsallakh, B., Micallef, L., Aigner, W., Hauser, H., Miksch, S., Rodgers, P.: The state-of-the-art of set visualization. Computer Graphics Forum 35(1), 234\u2013260 (2016). https:\/\/doi.org\/10.1111\/cgf.12722","journal-title":"Computer Graphics Forum"},{"key":"2_CR2","doi-asserted-by":"publisher","unstructured":"Amburg, I., Veldt, N., Benson, A.: Clustering in graphs and hypergraphs with categorical edge labels. In: The Web Conference (WWW 2020), pp. 706\u2013717. ACM (2020). https:\/\/doi.org\/10.1145\/3366423.3380152","DOI":"10.1145\/3366423.3380152"},{"issue":"3","key":"2_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976). https:\/\/doi.org\/10.1016\/S0022-0000(76)80045-1","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"2_CR4","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1287\/moor.23.3.613","volume":"23","author":"RE Burkard","year":"1998","unstructured":"Burkard, R.E., Deineko, V.G., Woeginger, G.J.: The travelling salesman and the PQ-Tree. Math. Oper. Res. 23(3), 613\u2013623 (1998). https:\/\/doi.org\/10.1287\/moor.23.3.613","journal-title":"Math. Oper. Res."},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/978-3-030-86062-2_47","volume-title":"Diagrammatic Representation and Inference","author":"P Chapman","year":"2021","unstructured":"Chapman, P.: Interactivity in linear diagrams. In: Basu, A., Stapleton, G., Linker, S., Legg, C., Manalo, E., Viana, P. (eds.) Diagrams 2021. LNCS (LNAI), vol. 12909, pp. 449\u2013465. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-86062-2_47"},{"key":"2_CR6","unstructured":"Chapman, P., Sim, K., Chen, H.: Drawing algorithms for linear diagrams. In: Talk Abstracts of Diagrams 2021, pp. 1\u20133 (2021), http:\/\/www.diagrams-conference.org\/2021\/wp-content\/uploads\/2021\/08\/Peter-Chapman-6-chapman.pdf"},{"key":"2_CR7","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/978-3-662-44043-8_18","volume-title":"Diagrammatic Representation and Inference","author":"P Chapman","year":"2014","unstructured":"Chapman, P., Stapleton, G., Rodgers, P., Micallef, L., Blake, A.: Visualizing sets: an empirical comparison of diagram types. In: Dwyer, T., Purchase, H., Delaney, A. (eds.) Diagrams 2014. LNCS (LNAI), vol. 8578, pp. 146\u2013160. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44043-8_18"},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.endm.2009.07.020","volume":"34","author":"C Chauve","year":"2009","unstructured":"Chauve, C., Ma\u0148uch, J., Patterson, M.: On the gapped consecutive-ones property. Electron. Notes Discret. Math. 34, 121\u2013125 (2009). https:\/\/doi.org\/10.1016\/j.endm.2009.07.020","journal-title":"Electron. Notes Discret. Math."},{"key":"2_CR9","doi-asserted-by":"publisher","unstructured":"Dobler, A.: On computing optimal linear diagrams: Code (2022). https:\/\/doi.org\/10.5281\/zenodo.6637911","DOI":"10.5281\/zenodo.6637911"},{"issue":"3","key":"2_CR10","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.jcss.2009.07.001","volume":"76","author":"M Dom","year":"2010","unstructured":"Dom, M., Guo, J., Niedermeier, R.: Approximation and fixed-parameter algorithms for consecutive ones submatrix problems. J. Comput. Syst. Sci. 76(3), 204\u2013221 (2010). https:\/\/doi.org\/10.1016\/j.jcss.2009.07.001","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"2_CR11","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4), 704\u2013714 (1976). https:\/\/doi.org\/10.1137\/0205049","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2_CR12","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"PW Goldberg","year":"1995","unstructured":"Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol. 2(1), 139\u2013152 (1995). https:\/\/doi.org\/10.1089\/cmb.1995.2.139","journal-title":"J. Comput. Biol."},{"issue":"6","key":"2_CR13","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1111\/1475-3995.00387","volume":"9","author":"S Haddadi","year":"2002","unstructured":"Haddadi, S.: A note on the NP-hardness of the consecutive block minimization problem. Int. Trans. Op. Res. 9(6), 775\u2013777 (2002). https:\/\/doi.org\/10.1111\/1475-3995.00387","journal-title":"Int. Trans. Op. Res."},{"key":"2_CR14","doi-asserted-by":"publisher","unstructured":"Haddadi, S.: Exponential neighborhood search for consecutive block minimization. Int. Trans. Op. Res. (2021). https:\/\/doi.org\/10.1111\/itor.13065","DOI":"10.1111\/itor.13065"},{"key":"2_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105273","volume":"131","author":"S Haddadi","year":"2021","unstructured":"Haddadi, S.: Iterated local search for consecutive block minimization. Comput. Oper. Res. 131, 105273 (2021). https:\/\/doi.org\/10.1016\/j.cor.2021.105273","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"2_CR16","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.ipl.2008.04.009","volume":"108","author":"S Haddadi","year":"2008","unstructured":"Haddadi, S., Layouni, Z.: Consecutive block minimization is 1.5-approximable. Inf. Process. Lett. 108(3), 132\u2013135 (2008). https:\/\/doi.org\/10.1016\/j.ipl.2008.04.009","journal-title":"Inf. Process. Lett."},{"key":"2_CR17","doi-asserted-by":"publisher","unstructured":"Indukaev, F.: Supervenn python package (v0.3.2) (2021). https:\/\/doi.org\/10.5281\/zenodo.4424381","DOI":"10.5281\/zenodo.4424381"},{"issue":"2","key":"2_CR18","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.1109\/TVCG.2020.3030475","volume":"27","author":"B Jacobsen","year":"2021","unstructured":"Jacobsen, B., Wallinger, M., Kobourov, S., N\u00f6llenburg, M.: MetroSets: visualizing sets as metro maps. IEEE Trans. Vis. Comput. Graph. 27(2), 1257\u20131267 (2021). https:\/\/doi.org\/10.1109\/TVCG.2020.3030475","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"issue":"1","key":"2_CR19","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1137\/0206004","volume":"6","author":"LT Kou","year":"1977","unstructured":"Kou, L.T.: Polynomial complete consecutive information retrieval problems. SIAM J. Comput. 6(1), 67\u201375 (1977). https:\/\/doi.org\/10.1137\/0206004","journal-title":"SIAM J. Comput."},{"key":"2_CR20","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.jvlc.2017.09.003","volume":"43","author":"JB Lamy","year":"2017","unstructured":"Lamy, J.B., Berthelot, H., Capron, C., Favre, M.: Rainbow boxes: a new technique for overlapping set visualization and two applications in the biomedical domain. J. Vis. Lang. Comput. 43, 71\u201382 (2017). https:\/\/doi.org\/10.1016\/j.jvlc.2017.09.003","journal-title":"J. Vis. Lang. Comput."},{"issue":"3","key":"2_CR21","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1177\/1473871618754343","volume":"18","author":"S Luz","year":"2019","unstructured":"Luz, S., Masoodian, M.: A comparison of linear and mosaic diagrams for set visualization. Inf. Vis. 18(3), 297\u2013310 (2019). https:\/\/doi.org\/10.1177\/1473871618754343","journal-title":"Inf. Vis."},{"issue":"9","key":"2_CR22","doi-asserted-by":"publisher","first-page":"1243","DOI":"10.1089\/cmb.2011.0128","volume":"18","author":"J Ma\u0148uch","year":"2011","unstructured":"Ma\u0148uch, J., Patterson, M.: The complexity of the gapped consecutive-ones property problem for matrices of bounded maximum degree. J. Comput. Biol. 18(9), 1243\u20131253 (2011). https:\/\/doi.org\/10.1089\/cmb.2011.0128","journal-title":"J. Comput. Biol."},{"issue":"18","key":"2_CR23","doi-asserted-by":"publisher","first-page":"2760","DOI":"10.1016\/j.dam.2012.03.019","volume":"160","author":"J Ma\u0148uch","year":"2012","unstructured":"Ma\u0148uch, J., Patterson, M., Chauve, C.: Hardness results on the gapped consecutive-ones property problem. Discret. Appl. Math. 160(18), 2760\u20132768 (2012). https:\/\/doi.org\/10.1016\/j.dam.2012.03.019","journal-title":"Discret. Appl. Math."},{"key":"2_CR24","doi-asserted-by":"publisher","unstructured":"Masoodian, M., Koivunen, L.: Temporal visualization of sets and their relationships using time-sets. In: Information Visualisation (IV 2018), pp. 85\u201390. IEEE (2018). https:\/\/doi.org\/10.1109\/iV.2018.00025","DOI":"10.1109\/iV.2018.00025"},{"issue":"3","key":"2_CR25","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"CH Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.H.: The Euclidean travelling salesman problem is NP-complete. Theor. Comput. Sci. 4(3), 237\u2013244 (1977). https:\/\/doi.org\/10.1016\/0304-3975(77)90012-3","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"2_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2810012","volume":"22","author":"P Rodgers","year":"2015","unstructured":"Rodgers, P., Stapleton, G., Chapman, P.: Visualizing sets with linear diagrams. ACM Trans. Comput. Hum. Interact. 22(6), 1\u201339 (2015). https:\/\/doi.org\/10.1145\/2810012","journal-title":"ACM Trans. Comput. Hum. Interact."},{"key":"2_CR27","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1007\/978-3-642-31223-6_49","volume-title":"Diagrammatic Representation and Inference","author":"Y Sato","year":"2012","unstructured":"Sato, Y., Mineshima, K.: The efficacy of diagrams in syllogistic reasoning: a case of linear diagrams. In: Cox, P., Plimmer, B., Rodgers, P. (eds.) Diagrams 2012. LNCS (LNAI), vol. 7352, pp. 352\u2013355. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31223-6_49"},{"key":"2_CR28","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.104948","volume":"120","author":"LCR Soares","year":"2020","unstructured":"Soares, L.C.R., Reinsma, J.A., Nascimento, L.H.L., Carvalho, M.A.M.: Heuristic methods to consecutive block minimization. Comput. Oper. Res. 120, 104948 (2020). https:\/\/doi.org\/10.1016\/j.cor.2020.104948","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"2_CR29","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0211234","volume":"14","author":"G Stapleton","year":"2019","unstructured":"Stapleton, G., Chapman, P., Rodgers, P., Touloumis, A., Blake, A., Delaney, A.: The efficacy of Euler diagrams and linear diagrams for visualizing set cardinality using proportions and numbers. PLoS ONE 14(3), e0211234 (2019). https:\/\/doi.org\/10.1371\/journal.pone.0211234","journal-title":"PLoS ONE"}],"container-title":["Lecture Notes in Computer Science","Diagrammatic Representation and Inference"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-15146-0_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,6]],"date-time":"2022-09-06T23:04:57Z","timestamp":1662505497000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-15146-0_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031151453","9783031151460"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-15146-0_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"7 September 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Diagrams","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Theory and Application of Diagrams","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 September 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 September 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"diagrams2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.diagrams-conference.org\/2022\/","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":"58","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":"11","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":"19","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.03","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":"3.9","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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5 other types of papers were also accepted","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}