{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:34:25Z","timestamp":1753882465573,"version":"3.41.2"},"reference-count":12,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:p> In the minimum constraint removal ([Formula: see text]), there is no feasible path to move from a starting point towards the goal, and the minimum constraints should be removed in order to find a collision-free path. It has been proved that [Formula: see text] problem is NP-hard when constraints have arbitrary shapes or even they are in shape of convex polygons. However, it has a simple linear solution when constraints are lines and the problem is open for other cases yet. In this paper, using a reduction from Subset Sum problem, in three steps, we show that the problem is NP-hard for both weighted and unweighted line segments. <\/jats:p>","DOI":"10.1142\/s1793830922500550","type":"journal-article","created":{"date-parts":[[2022,1,13]],"date-time":"2022-01-13T15:24:18Z","timestamp":1642087458000},"source":"Crossref","is-referenced-by-count":1,"title":["Minimum constraint removal problem for line segments is NP-hard"],"prefix":"10.1142","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3387-3193","authenticated-orcid":false,"given":"Bahram Sadeghi","family":"Bigham","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Technology, Institute for Advanced Studies in Basic Sciences (IASBS), Zanjan, Iran"}]}],"member":"219","published-online":{"date-parts":[[2022,1,12]]},"reference":[{"key":"S1793830922500550BIB001","volume-title":"Proc. 2001 ICRA. IEEE Int. Conf. Robotics and Automation","volume":"2","author":"Basch J.","year":"2001"},{"volume-title":"Int. Symp. Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics","year":"2009","author":"Bereg S.","key":"S1793830922500550BIB002"},{"key":"S1793830922500550BIB003","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1007\/3-540-48686-0_36","volume-title":"Int. Computing and Combinatorics Conf.","author":"Cai Y. J.","year":"1999"},{"volume-title":"Proc. Twenty-Seventh AAAI Conf. Artificial Intelligence","year":"2013","author":"Erickson L.","key":"S1793830922500550BIB004"},{"key":"S1793830922500550BIB005","doi-asserted-by":"publisher","DOI":"10.26493\/1855-3974.280.8d3"},{"key":"S1793830922500550BIB006","volume":"33","author":"Hauser K.","year":"2013","journal-title":"Int. J. Robot. Res."},{"key":"S1793830922500550BIB007","first-page":"2","volume":"6","author":"Hauser K.","year":"2013","journal-title":"Robot. Sci. Syst."},{"volume-title":"8th Annual Symp. Combinatorial Search","year":"2015","author":"Krontiris A.","key":"S1793830922500550BIB008"},{"issue":"3","key":"S1793830922500550BIB009","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/j.jocs.2011.08.005","volume":"3","author":"Bigham B. Sadeghi","year":"2012","journal-title":"J. Comput. Sci."},{"issue":"2","key":"S1793830922500550BIB010","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s12065-019-00331-5","volume":"13","author":"Bigham B. Sadeghi","year":"2020","journal-title":"Evolut. Intell."},{"issue":"4","key":"S1793830922500550BIB011","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1142\/S0219843605000545","volume":"2","author":"Stilman M.","year":"2005","journal-title":"Int. J. Human. Robot."},{"key":"S1793830922500550BIB012","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1016\/j.asoc.2016.02.047","volume":"43","author":"Xu B.","year":"2016","journal-title":"Appl. Soft Comput."}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830922500550","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,3]],"date-time":"2023-02-03T05:25:08Z","timestamp":1675401908000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S1793830922500550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,12]]},"references-count":12,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["10.1142\/S1793830922500550"],"URL":"https:\/\/doi.org\/10.1142\/s1793830922500550","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2022,1,12]]},"article-number":"2250055"}}