Two faces of greedy leaf removal procedure on graphs

doi:10.1088/1742-5468/ab2cca

CORC > 理论物理研究所 > 中国科学院理论物理研究所 > 理论物理所科研产出 > 理论物理所1978-2010年知识产出

	Two faces of greedy leaf removal procedure on graphs
	Zhao, Jin-Hua ; Zhou, Hai-Jun
刊名	JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
	2019
页码	83401
关键词	STATISTICAL-MECHANICS INDEPENDENCE NUMBER COMMUNITY STRUCTURE PERCOLATION DYNAMICS NETWORKS INTERNET BAY
ISSN号	1742-5468
DOI	10.1088/1742-5468/ab2cca
英文摘要	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.
学科主题	Mechanics ; Physics
语种	英语
内容类型	期刊论文
源URL	[http://ir.itp.ac.cn/handle/311006/27125]
专题	理论物理研究所_理论物理所1978-2010年知识产出
作者单位	1.Chinese Acad Sci, Inst Theoret Phys, CAS Key Lab Theoret Phys, Beijing 100190, Peoples R China 2.South China Normal Univ, Sch Phys & Telecommun Engn, Guangzhou 510006, Guangdong, Peoples R China 3.Univ Chinese Acad Sci, Sch Phys Sci, Beijing 100049, Peoples R China 4.South China Normal Univ, Inst Quantum Matter, Guangzhou 510006, Guangdong, Peoples R China 5.[Zhao, Jin-Hua
推荐引用方式 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.