Graph colouring via entropy compression

通过熵压缩进行图形着色

• 批准号: FT130100464
• 负责人: Prof David Wood
• 金额: $ 50.34万
• 依托单位: Monash University
• 依托单位国家: 澳大利亚
• 项目类别: ARC Future Fellowships
• 财政年份: 2014
• 资助国家: 澳大利亚
• 起止时间: 2014-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://dataportal.arc.gov.au/RGS/Web/Grants/FT130100464
• 关键词: Graph; colouring; via; entropy; compression

Graphs and hypergraphs are mathematical structures that model networks. Colouring graphs and hypergraphs is a key problem in many fields including scheduling, computing derivatives, cryptography, and coding theory. This project will apply a revolutionary method called "entropy compression" to produce new mathematical tools and algorithms for colouring graphs and hypergraphs. These results will have significant ramifications for the above applications, and will also be of fundamental importance in graph theory itself.

图和超图是建模网络的数学结构。在许多领域，包括调度，计算衍生物，密码学和编码理论在内的许多领域，着色图和超图是一个关键问题。该项目将应用一种称为“熵压缩”的革命性方法，以生成用于着色图和超图的新数学工具和算法。这些结果将对上述应用产生重大影响，并且在图理论本身中也将非常重要。