Back to Search
Start Over
Graphical Representation and Hierarchical Decomposition Mechanism for Vertex-Cover Solution Space
- Publication Year :
- 2019
-
Abstract
- In this paper, solution space organization of minimum vertex-cover problem is deeply investigated using the K\"{o}nig-Eg\'{e}rvary (KE) graph and theorem, in which a hierarchical decomposition mechanism named KE-layer structure of general graphs is proposed to reveal the complexity of vertex-cover. An algorithm to verify the KE graph is given by the solution space expression of vertex-cover, and the relation between multi-layer KE graphs and maximal matching is illustrated and proved. Furthermore, a framework to calculate the KE-layer number and approximate the minimal vertex-cover is provided, with different strategies of switching nodes and counting energy. The phase transition phenomenon between different KE-layers are studied with the transition points located, and searching of vertex-cover got by this strategy presents comparable advantage against several other methods. The graphical representation and hierarchical decomposition provide a new perspective to illustrate the intrinsic complexity for large-scale graphs/systems recognition.<br />Comment: 20 pages, 6 figures
- Subjects :
- Computer Science - Social and Information Networks
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1912.08559
- Document Type :
- Working Paper