{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:57:34Z","timestamp":1781305054000,"version":"3.54.1"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032286901","type":"print"},{"value":"9783032286918","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-28691-8_2","type":"book-chapter","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:33:05Z","timestamp":1781303585000},"page":"17-31","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A PTAS for\u00a0Weighted Triangle-Free 2-Matching"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8647-6928","authenticated-orcid":false,"given":"Miguel","family":"Bosch-Calvo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9676-4931","authenticated-orcid":false,"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9478-7307","authenticated-orcid":false,"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-1634-2733","authenticated-orcid":false,"given":"Takashi","family":"Noguchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,13]]},"reference":[{"key":"2_CR1","unstructured":"Adamaszek, A., Mnich, M., Paluch, K.: New approximation algorithms for (1,2)-TSP. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 9:1\u20139:14 (2018)"},{"issue":"3","key":"2_CR2","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/s00453-012-9642-6","volume":"64","author":"MA Babenko","year":"2012","unstructured":"Babenko, M.A.: Improved algorithms for even factors and square-free simple b-matchings. Algorithmica 64(3), 362\u2013383 (2012)","journal-title":"Algorithmica"},{"key":"2_CR3","unstructured":"B\u00e9rczi, K.: The triangle-free 2-matching polytope of subcubic graphs. Technical Report TR-2012-02, Egerv\u00e1ry Research Group, Budapest (2012). http:\/\/egres.elte.hu"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"B\u00e9rczi, K., V\u00e9gh, L.A.: Restricted $$b$$-matchings in degree-bounded graphs. In: Proceedings of the 14th Conference of Integer Programming and Combinatorial Optimization (IPCO 2010), volume 6080 of LNCS, pp. 43\u201356 (2010)","DOI":"10.1007\/978-3-642-13036-6_4"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Bl\u00e4ser, M., Ram, L.S.: An improved approximation algorithm for TSP with distances one and two. In: Li\u015bkiewicz, M., Reischuk, R., (eds.), Fundamentals of Computation Theory, pp. 504\u2013515. Springer, Berlin, Heidelberg (2005)","DOI":"10.1007\/11537311_44"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Bosch-Calvo, M., Garg, M., Grandoni, F., Hommelsheim, F., Ameli, A.J., Lindermayr, A.: A 5\/4-approximation for two-edge connectivity. In: Kouck\u00fd, M., Bansal, N., (eds.), Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, 23-27 June 2025, pp. 653\u2013664. ACM (2025)","DOI":"10.1145\/3717823.3718275"},{"key":"2_CR7","unstructured":"Bosch-Calvo, M., Grandoni, F., Ameli, A.J.: A 4\/3 approximation for 2-vertex-connectivity. In: Etessami, K., Feige, U., Puppis, G., (eds.), 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, 10-14 July 2023, Paderborn, Germany, volume 261 of LIPIcs, pp. 29:1\u201329:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"key":"2_CR8","unstructured":"Bosch-Calvo, M., Grandoni, F., Ameli, A.J.: A PTAS for triangle-free 2- matching. arXiv preprint arXiv:2311.11869 (2023)"},{"key":"2_CR9","unstructured":"Bosch-Calvo, M., Grandoni, F., Kobayashi, Y., Noguchi, T.: A PTAS for weighted triangle-free 2-matching. arXiv preprint arXiv:2603.09144 (2026)"},{"issue":"3","key":"2_CR10","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1016\/j.jctb.2011.08.007","volume":"102","author":"K B\u00e9rczi","year":"2012","unstructured":"B\u00e9rczi, K., Kobayashi, Y.: An algorithm for (n-3)-connectivity augmentation problem: jump system approach. J. Comb. Theory Seri. B 102(3), 565\u2013587 (2012)","journal-title":"J. Comb. Theory Seri. B"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Cheriyan, J., Seb\u0151, A., Szigeti, Z.: Improving on the 1.5-approximation of a smallest 2-edge connected spanning subgraph. SIAM J. Discret. Math. 14(2), 170\u2013180 (2001)","DOI":"10.1137\/S0895480199362071"},{"issue":"2","key":"2_CR12","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0012-365X(80)90002-3","volume":"29","author":"G Cornu\u00e9jols","year":"1980","unstructured":"Cornu\u00e9jols, G., Pulleyblank, W.: A matching problem with side conditions. Discret. Math. 29(2), 135\u2013159 (1980)","journal-title":"Discret. Math."},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Garg, M., Grandoni, F., Ameli, A.J.: Improved approximation for two-edge-connectivity. In: Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pp. 2368\u20132410 (2023)","DOI":"10.1137\/1.9781611977554.ch92"},{"key":"2_CR14","unstructured":"Garg, N., Vempala, S.S., Singla, A.: Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques. In: Ramachandran, V., (eds.), Proceedings of the Fourth Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms, 25-27 January 1993, Austin, Texas, USA, pp. 103\u2013111. ACM\/SIAM (1993)"},{"key":"2_CR15","unstructured":"Hartvigsen, D.: Extensions of Matching Theory. PhD thesis, Carnegie Mellon University (1984). https:\/\/david-hartvigsen.net"},{"issue":"5","key":"2_CR16","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/j.jctb.2006.01.004","volume":"96","author":"D Hartvigsen","year":"2006","unstructured":"Hartvigsen, D.: Finding maximum square-free 2-matchings in bipartite graphs. J. Comb. Theory Seri. B 96(5), 693\u2013705 (2006)","journal-title":"J. Comb. Theory Seri. B"},{"issue":"3","key":"2_CR17","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1002\/jgt.23089","volume":"106","author":"D Hartvigsen","year":"2024","unstructured":"Hartvigsen, D.: Finding triangle-free 2-factors in general graphs. J. Graph Theory 106(3), 581\u2013662 (2024)","journal-title":"J. Graph Theory"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Hartvigsen, D., Li, Y.: Triangle-free simple 2-matchings in subcubic graphs (extended abstract). In: Proceedings of the 12th International Conference on Integer Programming and Combinatorial Optimization, IPCO \u201907, pp. 43\u201352. Springer-Verlag, Berlin, Heidelberg (2007)","DOI":"10.1007\/978-3-540-72792-7_4"},{"issue":"3","key":"2_CR19","doi-asserted-by":"publisher","first-page":"1820","DOI":"10.1137\/16M1091587","volume":"31","author":"K Heeger","year":"2017","unstructured":"Heeger, K., Vygen, J.: Two-connected spanning subgraphs with at most $$\\frac{10}{7}{OPT}$$ edges. SIAM J. Discret. Math. 31(3), 1820\u20131835 (2017)","journal-title":"SIAM J. Discret. Math."},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Hommelsheim, F., Lindermayr, A., Liu, Z.: A better-than-5\/4-approximation for two-edge connectivity. In: Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pp. 1468\u20131520 (2026) arXiv:2509.19655","DOI":"10.1137\/1.9781611978971.54"},{"issue":"4","key":"2_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3341599","volume":"15","author":"C Hunkenschr\u00f6der","year":"2019","unstructured":"Hunkenschr\u00f6der, C., Vempala, S., Vetta, A.: A 4\/3-approximation algorithm for the minimum 2-edge connected subgraph problem. ACM Trans. Algorithms 15(4), 1\u201328 (2019)","journal-title":"ACM Trans. Algorithms"},{"key":"2_CR22","unstructured":"Iwamasa, Y., Kobayashi, Y., Takazawa, K.: Finding a maximum restricted $$t$$-matching via Boolean edge-CSP. In Proceedings of the 32nd Annual European Symposium on Algorithms (ESA 2024), volume 308 of LIPIcs, pp. 75:1\u201375:15 (2024)"},{"issue":"2","key":"2_CR23","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1145\/174652.174654","volume":"41","author":"S Khuller","year":"1994","unstructured":"Khuller, S., Vishkin, U.: Biconnectivity approximations and graph carvings. J. ACM 41(2), 214\u2013235 (1994)","journal-title":"J. ACM"},{"key":"2_CR24","unstructured":"Kir\u00e1ly, Z.: Restricted t-matchings in bipartite graphs. Technical Report QP-2009-04, Egerv\u00e1ry Research Group, Budapest (2009). http:\/\/egres.elte.hu"},{"issue":"4","key":"2_CR25","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.disopt.2010.04.001","volume":"7","author":"Y Kobayashi","year":"2010","unstructured":"Kobayashi, Y.: A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs. Discret. Optim. 7(4), 197\u2013202 (2010)","journal-title":"Discret. Optim."},{"issue":"1\u20132","key":"2_CR26","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/s10107-021-01661-y","volume":"192","author":"Y Kobayashi","year":"2022","unstructured":"Kobayashi, Y.: Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles. Math. Program. 192(1\u20132), 675\u2013702 (2022)","journal-title":"Math. Program."},{"key":"2_CR27","unstructured":"Kobayashi, Y., Noguchi, T.: An approximation algorithm for two-edge-connected subgraph problem via triangle-free two-edge-cover. In 34th International Symposium on Algorithms and Computation (ISAAC 2023), volume 283 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 49:1\u201349:10 (2023)"},{"key":"2_CR28","doi-asserted-by":"crossref","unstructured":"Kobayashi, Y., Noguchi, T.: Validating a PTAS for triangle-free 2-matching via a simple decomposition theorem. In: 2025 Symposium on Simplicity in Algorithms (SOSA), pp. 281\u2013289 (2025)","DOI":"10.1137\/1.9781611978315.22"},{"key":"2_CR29","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/060652282","volume":"21","author":"M Makai","year":"2007","unstructured":"Makai, M.: On maximum cost $$K_{t, t}$$-free $$t$$-matchings of bipartite graphs. SIAM J. Discret. Math. 21, 349\u2013360 (2007)","journal-title":"SIAM J. Discret. Math."},{"key":"2_CR30","unstructured":"Nam, Y.: Matching Theory: Subgraphs with Degree Constraints and Other Properties. PhD thesis, University of British Columbia (1994)"},{"key":"2_CR31","unstructured":"Paluch, K.: Triangle-free 2-matchings. arXiv preprint arXiv:2311.13590 (2023)"},{"key":"2_CR32","unstructured":"Paluch, K., Wasylkiewicz, M.: Restricted $$t$$-matchings via half-edges. In: Proceedings of the 29th Annual European Symposium on Algorithms (ESA 2021), volume 204 of LIPIcs, pp. 73:1\u201373:17 (2021)"},{"key":"2_CR33","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2021.106146","volume":"171","author":"K Paluch","year":"2021","unstructured":"Paluch, K., Wasylkiewicz, M.: A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs - via half-edges. Inf. Process. Lett. 171, 106146 (2021)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"2_CR34","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10107-006-0053-9","volume":"110","author":"G Pap","year":"2007","unstructured":"Pap, G.: Combinatorial algorithms for matchings, even factors and square-free 2-factors. Math. Program. 110(1), 57\u201369 (2007)","journal-title":"Math. Program."},{"key":"2_CR35","unstructured":"Schrijver, A.: Combinatorial optimization: polyhedra and efficiency. Springer Science & Business Media (2003)"},{"issue":"5","key":"2_CR36","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s00493-014-2960-3","volume":"34","author":"A Seb\u0151","year":"2014","unstructured":"Seb\u0151, A., Vygen, J.: Shorter tours by nicer ears: 7\/5-approximation for the graph-tsp, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. Combinatorica 34(5), 597\u2013629 (2014)","journal-title":"Combinatorica"},{"key":"2_CR37","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1287\/moor.1080.0365","volume":"34","author":"K Takazawa","year":"2009","unstructured":"Takazawa, K.: A weighted $$K_{t, t}$$-free $$t$$-factor algorithm for bipartite graphs. Math. Oper. Res. 34, 351\u2013362 (2009)","journal-title":"Math. Oper. Res."},{"key":"2_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/3-540-44436-X_26","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"S Vempala","year":"2000","unstructured":"Vempala, S., Vetta, A.: Factor 4\/3 approximations for minimum 2-connected subgraphs. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol. 1913, pp. 262\u2013273. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44436-X_26"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-28691-8_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:33:13Z","timestamp":1781303593000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28691-8_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032286901","9783032286918"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28691-8_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"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":"Padua","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":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.math.unipd.it\/ipco2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}