Random Graphs: Structure and Algorithms

随机图：结构和算法

• 批准号: 0753472
• 负责人: ALAN FRIEZE
• 金额: $ 17.18万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-07-01 至 2012-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0753472&HistoricalAwards=false
• 关键词: Random; Graphs; Structure; Algorithms

ABSTRACTPrincipal Investigator: Frieze, Alan Proposal Number: DMS - 0753472 Institution: Carnegie-Mellon UniversityTitle: Random Graphs: Structure and AlgorithmsThe study of random combinatorial structures has emerged as an important component of Discrete Mathematics. The most intensely studied area is that of random graphs and many of the results of this area have been extended to hypergraphs or set systems. This proposal is aimed at doing research into various structural properties of random graphs and hypergraphs. In addition the proposal will consider some related algorithmic questions.Graphs and networks are emerging as important phenomena. Networks arise in social contexts such as links between pages in the World Wide Web. They also arise in biological systems such as the protein inter-action network of a cell. These networks arise from "random processes" and so the study of random graphs is becoming more and more relevant. Finally, studying algorithms on typical graphs will hopefully be usefull in drawing back the shadow of the negative results of complexity theory.

摘要 首席研究员：Frieze, Alan 提案编号：DMS - 0753472 机构：卡内基梅隆大学 标题：随机图：结构和算法 随机组合结构的研究已成为离散数学的重要组成部分。研究最深入的领域是随机图，该领域的许多结果已扩展到超图或集合系统。该提案旨在研究随机图和超图的各种结构特性。此外，该提案还将考虑一些相关的算法问题。图和网络正在成为重要的现象。网络出现在社交环境中，例如万维网上页面之间的链接。它们也出现在生物系统中，例如细胞的蛋白质相互作用网络。这些网络产生于“随机过程”，因此随机图的研究变得越来越重要。最后，在典型图上研究算法有望有助于消除复杂性理论负面结果的阴影。