An Efficient Local Search for the Minimum Independent Dominating Set Problem

DOI10.4230/LIPIcs.SEA.2018.13zbMath1496.90076arXiv1802.06478OpenAlexW2963534575MaRDI QIDQ5140723

Kazuya Haraguchi

Publication date: 16 December 2020

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

zbMATH Keywords

metaheuristicslocal searchplateau searchminimum independent dominating set problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Uses Software

• BHOSLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast local search for the maximum independent set problem
• Approximating the minimum maximal independence number
• Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers
• Fast algorithms for min independent dominating set
• Independent domination in graphs: A survey and recent results
• The Weighted Independent Domination Problem: ILP Model and Algorithmic Approaches
• Maximum Minimal Vertex Cover Parameterized by Vertex Cover
• Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic
• Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs