ITP OpenIR  > SCI期刊论文
Zhao, Jin-Hua; Zhou, Hai-Jun
Two faces of greedy leaf removal procedure on graphs
Source PublicationJOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
Language英语
KeywordSTATISTICAL-MECHANICS INDEPENDENCE NUMBER COMMUNITY STRUCTURE PERCOLATION DYNAMICS NETWORKS INTERNET BAY
AbstractThe 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
ISSN1742-5468
Pages83401
Cooperation Status国内
Subject AreaMechanics ; Physics
MOST Discipline CatalogueMechanics ; Physics, Mathematical
DOI10.1088/1742-5468/ab2cca
Indexed BySCIE
Citation statistics
Cited Times:1[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/27125
CollectionSCI期刊论文
Affiliation1.[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.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhao, Jin-Hua]'s Articles
[Zhou, Hai-Jun]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhao, Jin-Hua]'s Articles
[Zhou, Hai-Jun]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhao, Jin-Hua]'s Articles
[Zhou, Hai-Jun]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.