A novel algorithm for the vertex cover problem based on minimal elements of discernibility matrix
- PDF / 2,242,331 Bytes
- 8 Pages / 595.276 x 790.866 pts Page_size
- 72 Downloads / 219 Views
ORIGINAL ARTICLE
A novel algorithm for the vertex cover problem based on minimal elements of discernibility matrix Shengyang Zhuang1 · Degang Chen1 Received: 30 July 2018 / Accepted: 21 January 2019 © Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract Minimal vertex cover problem (MVCP) is a famous important NP-hard problem in graph theory. It has been reported that MVCP is equivalent to finding reducts of information systems in rough sets theory. This relationship motivates our idea to deal with MVCP in terms of approaches to discernibility matrix in rough set. First we point out that only minimal elements in the discernibility matrix are useful for MVCP, and we present a novel algorithm based on minimal elements for MVCP. Then we make experimental comparisons to demonstrate the effectiveness of this new algorithm on big graphs. Keywords Vertex cover · Attribute reduction · Discernibility matrix · Minimal element
1 Introduction As a typical combinatorial optimization problem in graph theory, the minimal vertex cover problem(MVCP) aims to find a minimal set of vertices in a graph that covers all edges. MVCP has been widely applied to staff mobility [22], network security [3, 18], resource allocation [27], circuit design [19], and transportation vehicle routing [15], which results in strong demand for efficient algorithms of MVCP, especially higher requirements on calculation speed and computational efficiency for big graph in the existing big data era. Therefore finding efficient algorithms of MVCP is of great significance. In the classical graph theory, MVCP can be translated as the calculation of prime implications of the Boolean function [2]. Although we can get all of the minimal vertex covers by calculating the Boolean function, the calculation of the Boolean function is a famous NP-hard optimization problem [11]. The classical approximation methods such as greedy, rounda and Dual-LP [12], are heuristic algorithms in which calculation results are often not optimal, i.e., the best known performance bound on the approximation ratio is two * Shengyang Zhuang [email protected] Degang Chen [email protected] 1
School of Mathematics and Physics, North China Electric Power University, Beijing 102206, People’s Republic of China
[12, 13]. Therefore, the introduction of ideas and methods outside the graph theory field is a breakthrough of MVCP. On the other hand, information system is a basic notion in rough set theory [20, 21], and attribute reduction of information systems aims to find a minimal subset of attributes that preserve the same classification ability as the set of original attributes. Among the existing researches on attribute reduction within the framework of rough set [20], discernibility matrix method plays the fundamental role in finding reduction of information systems. A discernibility function can be developed by the discernibility matrix and all reducts can be found with this function. Chen et al. [8, 9] explored the relationship between discerninility function in rough s
Data Loading...
