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

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，意思是不太可能有一种有效的方法来通过计算机解决它们）可以有效地解决（在多项式时间内）？无论是在离散数学还是在理论计算机科学中，理解这种现象都是一个非常有趣的问题。近年来，理论计算机科学界开发了强大的方法来解决这个问题。我们的目标是利用我们在结构图论方面的专业知识来增强和加强这些方法，并将它们应用于几个长期存在的开放问题。

项目成果

Claw-free beta-perfect graphs

无爪 beta 完美图

• 期刊: submitted to Discrete Mathematics
• 作者: J. Horsffield

Submodular functions and perfect graphs

子模函数和完美图

• 期刊: submitted to Mathematics of Operations Research
• 作者: Abrishami T

Induced subgraphs and tree decompositions V. one neighbor in a hole

诱导子图和树分解 V. 洞中的一个邻居

• DOI: 10.1002/jgt.23055
• 发表时间: 2022
• 期刊: Journal of Graph Theory
• 影响因子: 0.9
• 作者: Tara Abrishami;M. Chudnovsky;Sepehr Hajebi;S. Spirkl
• 通讯作者: S. Spirkl

Bisimplicial vertices

双单纯顶点

• 期刊: submitted to Journal of Graph Theory
• 作者: M. Milanic

Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree

归纳子图和树分解 II。

• DOI: 10.1016/j.jctb.2023.10.005
• 发表时间: 2021
• 期刊: J. Comb. Theory B
• 作者: Tara Abrishami;M. Chudnovsky;Cemil Dibek;Sepehr Hajebi;Pawel Rzka.zewski;S. Spirkl;Kristina Vuvskovi'c
• 通讯作者: Kristina Vuvskovi'c