{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T23:23:53Z","timestamp":1743031433952,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031433795"},{"type":"electronic","value":"9783031433801"}],"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-43380-1_11","type":"book-chapter","created":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T20:29:12Z","timestamp":1695414552000},"page":"143-156","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Constructions for\u00a0the\u00a0Gy\u0151ri-Lov\u00e1sz Theorem on\u00a0Almost Chordal Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6146-8684","authenticated-orcid":false,"given":"Katrin","family":"Casel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0076-6308","authenticated-orcid":false,"given":"Tobias","family":"Friedrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5559-7471","authenticated-orcid":false,"given":"Davis","family":"Issac","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4911-4493","authenticated-orcid":false,"given":"Aikaterini","family":"Niklanovits","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0378-1458","authenticated-orcid":false,"given":"Ziena","family":"Zeif","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,23]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","unstructured":"Broersma, H., Dahlhaus, E., Kloks, T.: Algorithms for the treewidth and minimum fill-in of HHD-free graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 109\u2013117 (1997). https:\/\/doi.org\/10.1007\/BFb0024492","DOI":"10.1007\/BFb0024492"},{"key":"11_CR2","doi-asserted-by":"publisher","unstructured":"Chandran, L.S., Cheung, Y.K., Issac, D.: Spanning tree congestion and computation of generalized Gy\u00f6ri-Lov\u00e1sz partition. In: International Colloquium on Automata, Languages, and Programming, (ICALP). LIPIcs, vol. 107, pp. 32:1\u201332:14 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.32","DOI":"10.4230\/LIPIcs.ICALP.2018.32"},{"issue":"4","key":"11_CR3","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/1255443.1255444","volume":"54","author":"J Chen","year":"2007","unstructured":"Chen, J., Kleinberg, R.D., Lov\u00e1sz, L., Rajaraman, R., Sundaram, R., Vetta, A.: (Almost) tight bounds and existence theorems for single-commodity confluent flows. J. ACM 54(4), 16 (2007). https:\/\/doi.org\/10.1145\/1255443.1255444","journal-title":"J. ACM"},{"key":"11_CR4","unstructured":"Gy\u0151ri, E.: On division of graphs to connected subgraphs, combinatorics. In: Colloq. Math. Soc. Janos Bolyai, 1976 (1976)"},{"key":"11_CR5","unstructured":"Hoyer, A.: On the independent spanning tree conjectures and related problems. Ph.D. thesis, Georgia Institute of Technology (2019)"},{"issue":"3","key":"11_CR6","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1016\/0196-8858(88)90019-X","volume":"9","author":"B Jamison","year":"1988","unstructured":"Jamison, B., Olariu, S.: On the semi-perfect elimination. Adv. Appl. Math. 9(3), 364\u2013376 (1988)","journal-title":"Adv. Appl. Math."},{"issue":"3\u20134","key":"11_CR7","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF01896190","volume":"30","author":"L Lov\u00e1sz","year":"1977","unstructured":"Lov\u00e1sz, L.: A homology theory for spanning tress of a graph. Acta Math. Hungar. 30(3\u20134), 241\u2013251 (1977)","journal-title":"Acta Math. Hungar."},{"issue":"2","key":"11_CR8","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0166-218X(93)90048-S","volume":"42","author":"M Lucertini","year":"1993","unstructured":"Lucertini, M., Perl, Y., Simeone, B.: Most uniform path partitioning and its use in image processing. Discrete Appl. Math. 42(2), 227\u2013256 (1993). https:\/\/doi.org\/10.1016\/0166-218X(93)90048-S","journal-title":"Discrete Appl. Math."},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1187436.1216585","volume":"11","author":"RH M\u00f6hring","year":"2006","unstructured":"M\u00f6hring, R.H., Schilling, H., Sch\u00fctz, B., Wagner, D., Willhalm, T.: Partitioning graphs to speedup Dijkstra\u2019s algorithm. ACM J. Exp. Algorithmics 11, 2\u20138 (2006). https:\/\/doi.org\/10.1145\/1187436.1216585","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"6","key":"11_CR10","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0020-0190(97)00083-5","volume":"62","author":"S Nakano","year":"1997","unstructured":"Nakano, S., Rahman, M.S., Nishizeki, T.: A linear-time algorithm for four-partitioning four-connected planar graphs. Inf. Process. Lett. 62(6), 315\u2013322 (1997). https:\/\/doi.org\/10.1016\/S0020-0190(97)00083-5","journal-title":"Inf. Process. Lett."},{"key":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/11732990_27","volume-title":"Research in Computational Molecular Biology","author":"TM Przytycka","year":"2006","unstructured":"Przytycka, T.M.: An important connection between network motifs and parsimony models. In: Apostolico, A., Guerra, C., Istrail, S., Pevzner, P.A., Waterman, M. (eds.) RECOMB 2006. LNCS, vol. 3909, pp. 321\u2013335. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11732990_27"},{"issue":"2","key":"11_CR12","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1089\/cmb.2006.13.351","volume":"13","author":"TM Przytycka","year":"2006","unstructured":"Przytycka, T.M., Davis, G.B., Song, N., Durand, D.: Graph theoretical insights into evolution of multidomain proteins. J. Comput. Biol. 13(2), 351\u2013363 (2006). https:\/\/doi.org\/10.1089\/cmb.2006.13.351","journal-title":"J. Comput. Biol."},{"issue":"2","key":"11_CR13","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266\u2013283 (1976). https:\/\/doi.org\/10.1137\/0205021","journal-title":"SIAM J. Comput."},{"issue":"5","key":"11_CR14","first-page":"584","volume":"31","author":"H Suzuki","year":"1990","unstructured":"Suzuki, H., Takahashi, N., Nishizeki, T., Miyano, H., Ueno, S.: An algorithm for tripartitioning 3-connected graphs. J. Inf. Process. Soc. Japan 31(5), 584\u2013592 (1990)","journal-title":"J. Inf. Process. Soc. Japan"},{"issue":"5","key":"11_CR15","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0020-0190(90)90189-5","volume":"33","author":"H Suzuki","year":"1990","unstructured":"Suzuki, H., Takahashi, N., Nishizeki, T.: A linear algorithm for bipartition of biconnected graphs. Inf. Process. Lett. 33(5), 227\u2013231 (1990). https:\/\/doi.org\/10.1016\/0020-0190(90)90189-5","journal-title":"Inf. Process. Lett."},{"key":"11_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/3-540-57899-4_47","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"K Wada","year":"1994","unstructured":"Wada, K., Kawaguchi, K.: Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs. In: van Leeuwen, J. (ed.) WG 1993. LNCS, vol. 790, pp. 132\u2013143. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-57899-4_47"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/j.eswa.2018.09.001","volume":"116","author":"X Zhou","year":"2019","unstructured":"Zhou, X., Wang, H., Ding, B., Hu, T., Shang, S.: Balanced connected task allocations for multi-robot systems: an exact flow-based integer program and an approximate tree-based genetic algorithm. Expert Syst. Appl. 116, 10\u201320 (2019). https:\/\/doi.org\/10.1016\/j.eswa.2018.09.001","journal-title":"Expert Syst. Appl."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43380-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T20:30:23Z","timestamp":1695414623000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43380-1_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031433795","9783031433801"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43380-1_11","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":"23 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Fribourg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Switzerland","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":"28 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"49","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.unifr.ch\/wg2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}