DMS-EPSRC - The Power of Graph Structure

DMS-EPSRC - 图结构的力量

• 批准号: EP/V002813/1
• 负责人: K Vuskovic
• 金额: $ 54.79万
• 依托单位: University of Leeds
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2021
• 资助国家: 英国
• 起止时间: 2021 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FV002813%2F1
• 关键词: DMS; EPSRC; Power; Graph; Structure; DMS; EPSRC; Power; Graph; Structure

Graphs are mathematical objects used to model a variety of problems arising in diverse areas such as computer science, social science, transportation, telecommunication, molecular biology, industrial engineering, etc.The line of inquiry that guides our research is: what is the global difference between general graphs and graphs that do not contain a particular substructure? We focus on the following question: what algorithmic problems that are known to be hard (NP-hard, meaning that it is highly unlikely that there will ever be an efficient way to solve them by a computer) for general graphs can be solved efficiently (in polynomial time) if certain structural restrictions are placed on the input (more precisely: certain induced subgraphs are forbidden)? Understanding this phenomenon is a very interesting question, both in discrete mathematics and in theoretical computer science. In recent years powerful methods were developed in the theoretical computer science community to address this question. Our goal is to use our expertise in structural graph theory to augment and strengthen these methods, and apply them to several long-standing open problems.

图是用于建模各种问题的数学对象，例如计算机科学，社会科学，运输，电信，分子生物学，工业工程等。指导我们的研究的询问线是什么：一般图和图形之间的全球差异和图形之间的全球差异是什么？我们专注于以下问题：已知的算法问题（NP-HARD）（这意味着高度不可能有效地通过计算机解决这些问题）来有效地解决一般图表（在多项式时间内）如果将某些结构性限制放在输入上，则可以进行某些限制（某些预先限制：某些涉及的次数是：在离散数学和理论计算机科学中，了解这一现象是一个非常有趣的问题。近年来，在理论计算机科学界开发了强大的方法来解决这个问题。我们的目标是利用我们在结构图理论方面的专业知识来增强和加强这些方法，并将其应用于几个长期的开放问题。