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