{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:49:01Z","timestamp":1767340141085},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>The minimum weight dominating set (MWDS) problem is NP-hard and also important in many applications. Recent heuristic MWDS algorithms can hardly solve massive real world graphs effectively. In this paper, we design a fast local search algorithm called FastMWDS for the MWDS problem, which aims to obtain a good solution on massive graphs within a short time. In this novel local search framework, we propose two ideas to make it effective. Firstly, we design a new fast construction procedure with four reduction rules to cut down the size of massive graphs. Secondly, we propose the three-valued two-level configuration checking strategy to improve local search, which is interestingly a variant of configuration checking (CC) with two levels and multiple values. Experiment results on a broad range of massive real world graphs show that FastMWDS finds much better solutions than state of the art MWDS algorithms.<\/jats:p>","DOI":"10.24963\/ijcai.2018\/210","type":"proceedings-article","created":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T01:49:10Z","timestamp":1530755350000},"page":"1514-1522","source":"Crossref","is-referenced-by-count":23,"title":["A Fast Local Search Algorithm for Minimum Weight Dominating Set Problem on Massive Graphs"],"prefix":"10.24963","author":[{"given":"Yiyuan","family":"Wang","sequence":"first","affiliation":[{"name":"School of Computer Science and Information Technology, Northeast Normal University, China"},{"name":"Key Laboratory of Symbol Computation and Knowledge Engineering of Ministry of Education, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaowei","family":"Cai","sequence":"additional","affiliation":[{"name":"Institute of Software, Chinese Academy of Sciences, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiejiang","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Computer Science and Information Technology, Northeast Normal University, China"},{"name":"Key Laboratory of Symbol Computation and Knowledge Engineering of Ministry of Education, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minghao","family":"Yin","sequence":"additional","affiliation":[{"name":"School of Computer Science and Information Technology, Northeast Normal University, China"},{"name":"Key Laboratory of Symbol Computation and Knowledge Engineering of Ministry of Education, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"number":"27","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2018","name":"Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}","start":{"date-parts":[[2018,7,13]]},"theme":"Artificial Intelligence","location":"Stockholm, Sweden","end":{"date-parts":[[2018,7,19]]}},"container-title":["Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T01:51:01Z","timestamp":1530755461000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2018\/210"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2018\/210","relation":{},"subject":[],"published":{"date-parts":[[2018,7]]}}}