{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:16:42Z","timestamp":1753885002290,"version":"3.41.2"},"reference-count":23,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"DOI":"10.13039\/501100012165","name":"Key Technologies Research and Development Program","doi-asserted-by":"publisher","award":["2019YFB2101604"],"award-info":[{"award-number":["2019YFB2101604"]}],"id":[{"id":"10.13039\/501100012165","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Inter. Net."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:p> The graph bipartization problem, arising from via minimization in VLSI design and related areas, consists in finding a vertex subset [Formula: see text] of graph [Formula: see text] such that the induced subgraph [Formula: see text] is bipartite and [Formula: see text] is maximized. The problem has been proved to be NP-hard even for planar graphs and cubic graphs. On the other hand, the study of polynomial-time algorithms for typical graph classes is significant in both theoretical and applied aspects. This paper focuses on several intersection graph classes, such as line graphs, circular-arc graphs, and directed path graphs. For the line graphs, we show the NP-hardness results in general and present the polynomial-time algorithms for special cases. For circular-arc graphs and directed path graphs, we propose algorithms that improve on the previously known ones. <\/jats:p>","DOI":"10.1142\/s0219265924500063","type":"journal-article","created":{"date-parts":[[2024,4,8]],"date-time":"2024-04-08T08:32:05Z","timestamp":1712565125000},"source":"Crossref","is-referenced-by-count":0,"title":["Graph Bipartization and Via Minimization for Intersection Graphs"],"prefix":"10.1142","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2218-2506","authenticated-orcid":false,"given":"Lan","family":"Lin","sequence":"first","affiliation":[{"name":"School of Electronics and Information Engineering, Tongji University, Shanghai 200092, P. R. China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4807-1735","authenticated-orcid":false,"given":"Yixun","family":"Lin","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2024,4,6]]},"reference":[{"doi-asserted-by":"publisher","key":"S0219265924500063BIB001","DOI":"10.1006\/jagm.1996.0058"},{"year":"2022","author":"Bagga J.","journal-title":"AKCE Intern. J. Graphs and Combin.","key":"S0219265924500063BIB002"},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB003","DOI":"10.1007\/978-1-84628-970-5"},{"issue":"3","key":"S0219265924500063BIB004","first-page":"251","volume":"4","author":"Chia G. L.","year":"2007","journal-title":"AKCE J. Graphs Combin."},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB005","DOI":"10.1137\/0402004"},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB006","DOI":"10.1109\/43.85735"},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB007","DOI":"10.1016\/j.dam.2007.08.013"},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB008","DOI":"10.1007\/s10589-010-9355-1"},{"volume-title":"Computers and Intractability: A Guide to the NP-Completeness","year":"1979","author":"Garey M. R.","key":"S0219265924500063BIB009"},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB010","DOI":"10.1016\/0012-365X(75)90021-7"},{"volume-title":"Algorithmic Graph Theory and Perfect Graphs","year":"2004","author":"Golumbic M. C.","key":"S0219265924500063BIB011"},{"key":"S0219265924500063BIB012","first-page":"271","volume-title":"Selected Topics in Graph Theory","author":"Hemminger R. L.","year":"1987"},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB013","DOI":"10.1137\/0210055"},{"key":"S0219265924500063BIB014","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1109\/TCAD.1983.1270041","volume":"2","author":"Hsu C.-P.","year":"1983","journal-title":"IEEE Trans. Computer-Aided Design."},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB015","DOI":"10.1007\/978-3-030-39881-1_14"},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB016","DOI":"10.1007\/s00453-010-9432-y"},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB017","DOI":"10.1016\/j.jcss.2019.11.001"},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB018","DOI":"10.1142\/S0129054122500198"},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB020","DOI":"10.1007\/s00453-003-1032-7"},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB021","DOI":"10.1016\/j.orl.2003.10.009"},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB022","DOI":"10.1007\/3-540-45784-4_3"},{"doi-asserted-by":"publisher","key":"S0219265924500063BIB023","DOI":"10.1109\/43.31548"},{"volume-title":"Algorithms for VLSI Physical Design Automation (Third Edition)","year":"2002","author":"Sherwani N. A.","key":"S0219265924500063BIB024"}],"container-title":["Journal of Interconnection Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219265924500063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T03:56:19Z","timestamp":1745380579000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0219265924500063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,6]]},"references-count":23,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10.1142\/S0219265924500063"],"URL":"https:\/\/doi.org\/10.1142\/s0219265924500063","relation":{},"ISSN":["0219-2659","1793-6713"],"issn-type":[{"type":"print","value":"0219-2659"},{"type":"electronic","value":"1793-6713"}],"subject":[],"published":{"date-parts":[[2024,4,6]]},"article-number":"2450006"}}