Algorithms and structural matroid theory

算法和结构拟阵理论

• 批准号: RGPIN-2016-03886
• 负责人: Geelen, Jim
• 金额: $ 3.93万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634936
• 关键词: Algorithms; structural; matroid; theory

The Graph Minors Project, of Robertson and Seymour, is a sequence of 23 papers that have transformed the area of graph theory and have made a significant impact in theoretical computer science; the extent of that impact is witnessed by more than 6500 citations. Matroid theory provides a unifying framework for problems involving graphs and matrices, and has applications in diverse areas such as combinatorial optimization, coding theory, information theory, and computational biology. The research in this proposal is particularly applicable to coding theory, since linear codes are effectively the same as representable matroids and since minors give a natural containment relation on codes.

由Robertson和Seymour发起的Graph Minors Project是一个由23篇论文组成的系列，这些论文改变了图论领域，并对理论计算机科学产生了重大影响;超过6500次引用证明了这种影响的程度。 拟阵理论为涉及图和矩阵的问题提供了一个统一的框架，并在不同的领域，如组合优化，编码理论，信息论和计算生物学中有应用。在这个建议中的研究是特别适用于编码理论，因为线性码是有效的表示拟阵相同，因为未成年人给一个自然的代码包含关系。