A matheuristic approach for solving the 2-connected dominating set problem

DOI10.2298/AADM190227052JMaRDI QIDQ4989008zbMATH OpenOpenAlexFDO

Authors Raka Jovanovic, Stefan Voß

Publication date 20 May 2021

Published in Applicable Analysis and Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2298/aadm190227052j

zbMATH Keywords

dominating set problemmatheuristicGRASP

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Randomized algorithms (68W20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Mixed integer programming (90C11)

Recommendations

• Restricted swap-based neighborhood search for the minimum connected dominating set problem
• A decomposition approach for the minimum connected dominating set problem
• Approximation algorithms for connected dominating sets
• A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem
• Approximation algorithms for connected dominating sets

Cites work

• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• A heuristic approach for dividing graphs into bi-connected components with a size constraint
• A math-heuristic Dantzig-Wolfe algorithm for capacitated lot sizing
• An integer programming approach for fault-tolerant connected dominating sets
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• Combining metaheuristics with mathematical programming, constraint programming and machine learning
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
• On connected dominating sets of restricted diameter
• On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
• On the construction of \(k\)-connected \(m\)-dominating sets in wireless networks
• Perfect and quasiperfect domination in trees
• Total roman domination in graphs

Cited in

(5)

• A decomposition approach for the minimum connected dominating set problem
• Heuristics for \(k\)-domination models of facility location problems in street networks
• scientific article; zbMATH DE number 1320677 (Why is no real title available?)
• A novel local search approach with connected dominating degree-based incremental neighborhood evaluation for the minimum 2-connected dominating set problem
• Restricted swap-based neighborhood search for the minimum connected dominating set problem

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: A matheuristic approach for solving the 2-connected dominating set problem

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