{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T23:38:07Z","timestamp":1761176287208,"version":"build-2065373602"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"value":"9781643686318","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,21]],"date-time":"2025-10-21T00:00:00Z","timestamp":1761004800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,10,21]]},"abstract":"<jats:p>The Minimum Dominating Set problem (MDS) is a challenging NP-Hard problem with many practical applications. In this paper, we focus on its generalization, the Minimum Weight Dominating Set problem (MWDS). We first propose a novel lower bound for MWDS and prove a condition in which the computed lower bound is tight, then present a new local search approach, called Dual Bounds Search (DBS), which searches for a lower bound and an upper bound simultaneously in an alternate and collaborative way. We implement the lower bound algorithm and integrate two state-of-the-art local search algorithms into our DBS approach to obtain two new DBS algorithms for MWDS. Extensive experiments show that DBS approach can improve the local search performance for MWDS significantly. Thanks to the lower bound, new DBS algorithms can also provide a quality measure of solutions, which is practical in applications and is a clear difference from existing local searches for MWDS.<\/jats:p>","DOI":"10.3233\/faia251386","type":"book-chapter","created":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T10:00:10Z","timestamp":1761127210000},"source":"Crossref","is-referenced-by-count":0,"title":["A Novel Lower Bound and Dual Bounds Search for the Minimum Weight Dominating Set Problem"],"prefix":"10.3233","author":[{"given":"Hua","family":"Jiang","sequence":"first","affiliation":[{"name":"Yunnan University, Kunming, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wentao","family":"Luo","sequence":"additional","affiliation":[{"name":"Yunnan University, Kunming, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhifei","family":"Zheng","sequence":"additional","affiliation":[{"name":"Yunnan University, Kunming, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shengfa","family":"Miao","sequence":"additional","affiliation":[{"name":"Yunnan University, Kunming, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheng","family":"Xie","sequence":"additional","affiliation":[{"name":"Yunnan University, Kunming, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2025"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA251386","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T10:00:10Z","timestamp":1761127210000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA251386"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,21]]},"ISBN":["9781643686318"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia251386","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,21]]}}}