Knowledge Management System of Institute of Theoretical Physics, CAS
Zhao, Jin-Hua; Zhou, Hai-Jun
| |
| Two faces of greedy leaf removal procedure on graphs | |
| Source Publication | JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
 |
| Language | 英语 |
| Keyword | STATISTICAL-MECHANICS INDEPENDENCE NUMBER COMMUNITY STRUCTURE PERCOLATION DYNAMICS NETWORKS INTERNET BAY |
| Abstract | The greedy leaf removal (GLR) procedure on a graph is an iterative removal of any vertex with degree one (leaf) along with its nearest neighbor (root). Its result has two faces: a residual subgraph as a core, and a set of removed roots. While the emergence of cores on uncorrelated random graphs was solved analytically, a theory for roots is ignored except in the case of Erdos- Renyi random graphs. Here we analytically study roots on random graphs. We further show that, with a simple geometrical interpretation and a concise mean-field theory of the GLR procedure, we reproduce the zero-temperature replica symmetric estimation of relative sizes of both minimal vertex covers and maximum matchings on random graphs with or without cores. |
| 2019 | |
| ISSN | 1742-5468 |
| Pages | 83401 |
| Cooperation Status | 国内 |
| Subject Area | Mechanics ; Physics |
| MOST Discipline Catalogue | Mechanics ; Physics, Mathematical |
| DOI | 10.1088/1742-5468/ab2cca |
| Indexed By | SCIE |
| Citation statistics | |
| Document Type | 期刊论文 |
| Identifier | http://ir.itp.ac.cn/handle/311006/27125 |
| Collection | SCI期刊论文 |
| Affiliation | 1.[Zhao, Jin-Hua 2.Chinese Acad Sci, Inst Theoret Phys, CAS Key Lab Theoret Phys, Beijing 100190, Peoples R China 3.South China Normal Univ, Inst Quantum Matter, Guangzhou 510006, Guangdong, Peoples R China 4.South China Normal Univ, Sch Phys & Telecommun Engn, Guangzhou 510006, Guangdong, Peoples R China 5.Univ Chinese Acad Sci, Sch Phys Sci, Beijing 100049, Peoples R China |
| Recommended Citation GB/T 7714 | Zhao, Jin-Hua,Zhou, Hai-Jun. Two faces of greedy leaf removal procedure on graphs[J]. JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT,2019:83401. |
| APA | Zhao, Jin-Hua,&Zhou, Hai-Jun.(2019).Two faces of greedy leaf removal procedure on graphs.JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT,83401. |
| MLA | Zhao, Jin-Hua,et al."Two faces of greedy leaf removal procedure on graphs".JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT (2019):83401. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment