Stability in graphs: methodologies and related problems

图的稳定性：方法论和相关问题

• 批准号: EP/L020408/1
• 负责人: Vadim Lozin
• 金额: $ 50.38万
• 依托单位: University of Warwick
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2014
• 资助国家: 英国
• 起止时间: 2014 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FL020408%2F1
• 关键词: Stability; graphs; methodologies; related; problems

In 1965, Edmonds published his celebrated solution to the maximum matching problem, which is a special case of the maximum independent (stable) set problem restricted to the class of line graphs. Two key tools in the solution of Edmonds are augmenting chains and cycle shrinking. Both tools can be extended to general graphs but neither of them has been studied or used on a systematic basis. The idea of the present project is to lay theoretical foundations for both techniques (augmenting graphs and graph transformations) in order to turn their isolated applications into a developed methodology and apply this methodology to obtain faster exponential time algorithms for the maximum independent set and related problems, such as satisfiability and constraint satisfaction.

1965 年，Edmonds 发表了他对最大匹配问题的著名解决方案，这是限制于线图类的最大独立（稳定）集问题的特例。 Edmonds 解决方案中的两个关键工具是增加链条和缩短周期。这两种工具都可以扩展到一般图，但都没有被系统地研究或使用。本项目的想法是为这两种技术（增强图和图变换）奠定理论基础，以便将它们的孤立应用转化为成熟的方法，并应用该方法为最大独立集和相关问题（例如可满足性和约束满足）获得更快的指数时间算法。

项目成果

Deciding the Bell Number for Hereditary Graph Properties

确定遗传图属性的贝尔数

• DOI: 10.1137/15m1024214
• 发表时间: 2016
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Atminas A

Combinatorial Algorithms

组合算法

• DOI: 10.1007/978-3-319-29516-9_1
• 发表时间: 2016
• 作者: Abdullah M

Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation

没有大双团的图，并且通过诱导子图关系具有良好的准有序性

• DOI: 10.4310/joc.2019.v10.n2.a8
• 发表时间: 2019
• 期刊: Journal of Combinatorics
• 影响因子: 0.3
• 作者: Atminas A

Upper Domination: Towards a Dichotomy Through Boundary Properties

上层统治：通过边界属性走向二分法

• DOI: 10.1007/s00453-017-0346-9
• 发表时间: 2017
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: AbouEisha H

On forbidden induced subgraphs for unit disk graphs

单位圆盘图的禁止归纳子图

• DOI: 10.48550/arxiv.1602.08148
• 发表时间: 2016
• 作者: Atminas A