Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function

DOI10.1613/jair.5205zbMath1404.68146arXiv1702.04594OpenAlexW3100239395MaRDI QIDQ2962573

Minghao Yin, Yiyuan Wang, Shaowei Cai

Publication date: 17 February 2017

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1702.04594

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (11)

Solving the set packing problem via a maximum weighted independent set heuristic ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ The weighted independent domination problem: integer linear programming models and metaheuristic approaches ⋮ MLQCC: an improved local search algorithm for the set k‐covering problem ⋮ Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism ⋮ An efficient local search algorithm for minimum positive influence dominating set problem ⋮ An improved configuration checking-based algorithm for the unicost set covering problem ⋮ SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem ⋮ Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set ⋮ An order-based algorithm for minimum dominating set with application in graph mining ⋮ New heuristic approaches for maximum balanced biclique problem

This page was built for publication: Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function