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.

图和超图是模拟网络的数学结构。图和超图的着色是调度、计算导数、密码学和编码理论等许多领域的关键问题。该项目将应用一种称为“熵压缩”的革命性方法来产生用于着色图和超图的新数学工具和算法。这些结果将对上述应用产生重大影响，并且对于图论本身也具有根本性的重要性。