A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets

DOI10.1287/ijoc.2021.1106MaRDI QIDQ5085993

Fred Glover, Zhipeng Lü, Xinyun Wu

Publication date: 30 June 2022

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2021.1106

zbMATH Keywords

local search; metaheuristic; minimum dominating set; search space reduction; vertex weighting

Mathematics Subject Classification ID

90-XX: Operations research, mathematical programming

Related Items

An efficient local search algorithm for minimum positive influence dominating set problem

Cites Work

• An efficient local search heuristic with row weighting for the unicost set covering problem
• Flow-based formulation for the maximum leaf spanning tree problem
• Breakout local search for maximum clique problems
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• Approximation algorithms for connected dominating sets
• Spanning trees with a constraint on the number of leaves. A new formulation
• The broadcast storm problem in a mobile ad hoc network
• Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks
• Breakout local search for the quadratic assignment problem
• Revisiting connected dominating sets: an almost optimal local information algorithm
• Parametric tabu-search for mixed integer programs
• Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem
• An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets
• An Adaptive Flex-Deluge Approach to University Exam Timetabling
• The regenerator location problem
• The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm
• Robust Optimization of a Broad Class of Heterogeneous Vehicle Routing Problems Under Demand Uncertainty
• The maximum-leaf spanning tree problem: Formulations and facets
• Restricted swap-based neighborhood search for the minimum connected dominating set problem
• BROADCASTING IN AD HOC NETWORKS BASED ON SELF-PRUNING
• Unnamed Item
• Unnamed Item