Dual-Neighborhood Search for Solving the Minimum Dominating Tree Problem

Ze Pan, Xinyun Wu () and Caiquan Xiong
Additional contact information
Ze Pan: School of Computer Science, Hubei University of Technology, Wuhan 430068, China
Xinyun Wu: School of Computer Science, Hubei University of Technology, Wuhan 430068, China
Caiquan Xiong: School of Computer Science, Hubei University of Technology, Wuhan 430068, China

Mathematics, 2023, vol. 11, issue 19, 1-20

Abstract: 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.

Keywords: metaheuristic; dominating tree; dual neighborhoods; fast neighborhood evaluation; optimization (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/19/4214/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/19/4214/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:19:p:4214-:d:1256247

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().