Algorithmic and Computational Graph Theory and Game Theory

算法和计算图论和博弈论

• 批准号: 356035-2013
• 负责人: Farzad, Babak
• 金额: $ 1.09万
• 依托单位: Brock University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=572724
• 关键词: Algorithmic; Computational; Graph; Theory; Game

Fundamental problems in computer science revolve around the discovery of efficient algorithms. Designing fast algorithms or proving that no fast algorithm exists intimately relies, in many cases, on geometrical and graph theoretic characteristics of the problem. Graph Theory has long been recognized as one of the most fruitful fields for the formal study of such problems. Recently, with the massive amounts of network data that are becoming computationally available (including some social and biological networks), mathematicians and computer scientists have studied topological characteristics that such networks exhibit. One aspect of my research will focus on the analysis of large-scale networks. This work includes a precise topological analysis and proposing generative mechanisms. Such mechanisms have potential to help us reason, at a general level, about the ways in which real-world networks are organized. These models have novel algorithmic and graph-theoretic questions that I plan to study. A closely related line of research is the study of statistical aspects of graphs and the probabilistic treatment of random graphs - graphs that are generated by some random process. Random graphs also allow researchers to consider graphs that are both large and unstructured. Random lifts, a new versatile class of random graphs, is defined by, roughly speaking, randomly selecting the permutation that defines the lift. This allows us to design somewhat structured random graphs to model a variety of important naturally-occurring random graphs. Thus, determining the typical properties of a lift, such as their chromatic number, and how they reflect the properties of the base graph are very important and is another aspect of my research. I also intend to work on some of the classically more important problems in graph colouring, a traditionally important area of graph theory for computer scientists. In some of these problems, I will make use of the discharging method - the tool by which the famous Four Colour Problem was finally proved in 1979.

计算机科学的基本问题围绕着高效算法的发现。设计快速算法或证明不存在快速算法密切依赖于，在许多情况下，几何和图论的问题的特点。图论一直被认为是形式化研究此类问题最富有成果的领域之一。 近年来，随着大量的网络数据（包括一些社会和生物网络）变得可计算，数学家和计算机科学家已经研究了这些网络所表现出的拓扑特征。我的研究的一个方面将集中在大规模网络的分析。这项工作包括一个精确的拓扑分析，并提出生成机制。这种机制有可能帮助我们在一般层面上推理现实世界网络的组织方式。这些模型具有我计划研究的新颖算法和图论问题。 一个密切相关的研究方向是研究图的统计方面和随机图的概率处理-由一些随机过程生成的图。随机图还允许研究人员考虑大型和非结构化的图。 随机提升是一类新的通用随机图，粗略地说，随机选择定义提升的排列来定义。这使我们能够设计一些结构化的随机图来模拟各种重要的自然发生的随机图。因此，确定提升的典型性质，如它们的色数，以及它们如何反映基图的性质是非常重要的，也是我研究的另一个方面。 我还打算工作的一些经典的更重要的问题，图着色，一个传统的重要领域的图论计算机科学家。在其中的一些问题中，我将使用放电方法-著名的四色问题最终在1979年被证明的工具。