Solving Dominating Set Problem In Unit Disk Graphs By Genetic Algorithms
| Autor: | Azadeh Gholami, Mahmoud Shirazi, Bahram Sadeghi Bigham |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
ComputingMethodologies_PATTERNRECOGNITION
Data_CODINGANDINFORMATIONTHEORY Hardware_CONTROLSTRUCTURESANDMICROPROGRAMMING Wireless Ad-Hoc networks Backbone formation Genetic algorithm Dominating set Similarity Metric Similarity Robotics Trajectory Data Science Localization Computer Science::Information Theory |
| DOI: | 10.5281/zenodo.3788089 |
| Popis: | In this paper, we use Genetic Algorithms to find the Minimum Dominating Set (MDS) of Unit Disk Graphs (UDG). UDGs are used for modelling Ad-Hoc networks and finding MDS in such graphs is a promising approach to clustering the wireless Ad-Hoc networks. The MDS problem is proved to be NP-complete. The simulation results show that the proposed algorithm outperforms the existing algorithms for finding MDS in terms of the DS size. Computer Science, Mathematics |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|