Dual-Neighborhood Search for Solving the Minimum Dominating Tree Problem
The minimum dominating tree (MDT) problem consists of finding a minimum weight subgraph from an undirected graph, such that each vertex not in this subgraph is adjacent to at least one of the vertices in it, and the subgraph is connected without any ring structures. This paper presents a dual-neighb...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-10-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/19/4214 |
| _version_ | 1797575561999024128 |
|---|---|
| author | Ze Pan Xinyun Wu Caiquan Xiong |
| author_facet | Ze Pan Xinyun Wu Caiquan Xiong |
| author_sort | Ze Pan |
| collection | DOAJ |
| description | The minimum dominating tree (MDT) problem consists of finding a minimum weight subgraph from an undirected graph, such that each vertex not in this subgraph is adjacent to at least one of the vertices in it, and the subgraph is connected without any ring structures. This paper presents a dual-neighborhood search (DNS) algorithm for solving the MDT problem, which integrates several distinguishing features, such as two neighborhoods collaboratively working for optimizing the objective function, a fast neighborhood evaluation method to boost the searching effectiveness, and several diversification techniques to help the searching process jump out of the local optimum trap thus obtaining better solutions. DNS improves the previous best-known results for four public benchmark instances while providing competitive results for the remaining ones. Several ingredients of DNS are investigated to demonstrate the importance of the proposed ideas and techniques. |
| first_indexed | 2024-03-10T21:40:18Z |
| format | Article |
| id | doaj.art-f4e5404724d04c39a460681df4a17387 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T21:40:18Z |
| publishDate | 2023-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-f4e5404724d04c39a460681df4a173872023-11-19T14:44:55ZengMDPI AGMathematics2227-73902023-10-011119421410.3390/math11194214Dual-Neighborhood Search for Solving the Minimum Dominating Tree ProblemZe Pan0Xinyun Wu1Caiquan Xiong2School of Computer Science, Hubei University of Technology, Wuhan 430068, ChinaSchool of Computer Science, Hubei University of Technology, Wuhan 430068, ChinaSchool of Computer Science, Hubei University of Technology, Wuhan 430068, ChinaThe minimum dominating tree (MDT) problem consists of finding a minimum weight subgraph from an undirected graph, such that each vertex not in this subgraph is adjacent to at least one of the vertices in it, and the subgraph is connected without any ring structures. This paper presents a dual-neighborhood search (DNS) algorithm for solving the MDT problem, which integrates several distinguishing features, such as two neighborhoods collaboratively working for optimizing the objective function, a fast neighborhood evaluation method to boost the searching effectiveness, and several diversification techniques to help the searching process jump out of the local optimum trap thus obtaining better solutions. DNS improves the previous best-known results for four public benchmark instances while providing competitive results for the remaining ones. Several ingredients of DNS are investigated to demonstrate the importance of the proposed ideas and techniques.https://www.mdpi.com/2227-7390/11/19/4214metaheuristicdominating treedual neighborhoodsfast neighborhood evaluationoptimization |
| spellingShingle | Ze Pan Xinyun Wu Caiquan Xiong Dual-Neighborhood Search for Solving the Minimum Dominating Tree Problem Mathematics metaheuristic dominating tree dual neighborhoods fast neighborhood evaluation optimization |
| title | Dual-Neighborhood Search for Solving the Minimum Dominating Tree Problem |
| title_full | Dual-Neighborhood Search for Solving the Minimum Dominating Tree Problem |
| title_fullStr | Dual-Neighborhood Search for Solving the Minimum Dominating Tree Problem |
| title_full_unstemmed | Dual-Neighborhood Search for Solving the Minimum Dominating Tree Problem |
| title_short | Dual-Neighborhood Search for Solving the Minimum Dominating Tree Problem |
| title_sort | dual neighborhood search for solving the minimum dominating tree problem |
| topic | metaheuristic dominating tree dual neighborhoods fast neighborhood evaluation optimization |
| url | https://www.mdpi.com/2227-7390/11/19/4214 |
| work_keys_str_mv | AT zepan dualneighborhoodsearchforsolvingtheminimumdominatingtreeproblem AT xinyunwu dualneighborhoodsearchforsolvingtheminimumdominatingtreeproblem AT caiquanxiong dualneighborhoodsearchforsolvingtheminimumdominatingtreeproblem |