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

DOI10.1287/IJOC.2021.1106MaRDI QIDQ5085993zbMATH OpenOpenAlexFDO

Authors Xinyun Wu, Zhipeng Lü, Fred Glover

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 searchmetaheuristicminimum dominating setsearch space reductionvertex weighting

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• Efficient local search based on dynamic connectivity maintenance for minimum connected dominating set
• An efficient local search framework for the minimum weighted vertex cover problem
• An Efficient Local Search for the Minimum Independent Dominating Set Problem
• Algorithms for the minimum weight k-fold (connected) dominating set problem
• Towards faster local search for minimum weight vertex cover on massive graphs
• A greedy approximation for minimum connected dominating sets
• Revisiting connected dominating sets: an optimal local algorithm?
• Approximating the maximum vertex/edge weighted clique using local search
• A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS
• Near-optimal distributed approximation of minimum-weight connected dominating set

Cites work

• An adaptive flex-deluge approach to university exam timetabling
• An efficient local search heuristic with row weighting for the unicost set covering problem
• An integer programming approach for fault-tolerant connected dominating sets
• Approximation algorithms for connected dominating sets
• BROADCASTING IN AD HOC NETWORKS BASED ON SELF-PRUNING
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• Breakout local search for maximum clique problems
• Breakout local search for the quadratic assignment problem
• Flow-based formulation for the maximum leaf spanning tree problem
• Graph domination, coloring and cliques in telecommunications
• Improving local search for random 3-SAT using quantitative configuration checking
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• Parametric tabu-search for mixed integer programs
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• Restricted swap-based neighborhood search for the minimum connected dominating set problem
• Revisiting connected dominating sets: an almost optimal local information algorithm
• Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty
• Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks
• Spanning trees with a constraint on the number of leaves. A new formulation
• The broadcast storm problem in a mobile ad hoc network
• The maximum-leaf spanning tree problem: Formulations and facets
• The minimum connected dominating set problem: formulation, valid inequalities and a branch-and-cut algorithm
• The regenerator location problem

Cited in

(5)

• An efficient local search algorithm for minimum positive influence dominating set problem
• An efficient sum query algorithm for distance-based locally dominating functions
• A novel local search approach with connected dominating degree-based incremental neighborhood evaluation for the minimum 2-connected dominating set problem
• Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
• Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism

This page was built for publication: A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5085993)