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.

Please try later.