An order-based algorithm for minimum dominating set with application in graph mining

DOI10.1016/j.ins.2017.10.033zbMath1436.68224arXiv1705.00318OpenAlexW2611770526MaRDI QIDQ781288

David Chalupa

Publication date: 16 July 2020

Published in: Information Sciences (Search for Journal in Brave)

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

zbMATH Keywords

heuristicscomplex networksminimum dominating setorder-based representationrandomised local search

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) 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) Randomized algorithms (68W20)

Related Items (6)

An evolutionary algorithm based hyper-heuristic framework for the set packing problem ⋮ A heuristic approximation algorithm of minimum dominating set based on rough set theory ⋮ Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism ⋮ An iterated greedy algorithm for finding the minimum dominating set in graphs ⋮ An efficient local search algorithm for minimum positive influence dominating set problem ⋮ An integer programming approach for solving a generalized version of the Grundy domination number

Uses Software

• GraphBase
• Bonmin
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph clustering
• Inapproximability of dominating set on power law graphs
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• An algorithmic framework for convex mixed integer nonlinear programs
• Approximation hardness of dominating set problems in bounded degree graphs
• Unit disk graphs
• Analysis of a greedy heuristic for finding small dominating sets in graphs
• Experimental analysis of Heuristic algorithms for the dominating set problem
• On the approximability of positive influence dominating set in social networks
• From the Cover: The structure of scientific collaboration networks
• Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
• Emergence of Scaling in Random Networks
• A threshold of ln n for approximating set cover
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• A measure & conquer approach for the analysis of exact algorithms
• NEW METAHEURISTIC APPROACHES FOR THE LEAF-CONSTRAINED MINIMUM SPANNING TREE PROBLEM
• A Greedy Heuristic for the Set-Covering Problem
• Community structure in social and biological networks
• Collective dynamics of ‘small-world’ networks
• Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game
• Constant-time distributed dominating set approximation

This page was built for publication: An order-based algorithm for minimum dominating set with application in graph mining