Algorithms and structural matroid theory
算法和结构拟阵理论
基本信息
- 批准号:RGPIN-2016-03886
- 负责人:
- 金额:$ 3.93万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2018
- 资助国家:加拿大
- 起止时间:2018-01-01 至 2019-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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.*** Since 1999, I have worked with Bert Gerards (the Centrum voor Wiskunde en Informatica, the Netherlands) and Geoff Whittle (Victoria University of Wellington, New Zealand) on extending the Graph Minors Project of Neil Robertson and Paul Seymour to matroids. Our Matroid Minors Project has been a spectacular success with most of the major goals having been attained. This proposal addresses a number of fundamental algorithmic issues that remain.*** Our main goals are:***(1) Simplify the algorithms in the Matroid Minors Project. Three computational aspects of the Matroid Minors Project (namely the Minor-Testing Theorem, the constructive version of the Matroid Minors Structure Theorem, and the Three Elements Problem) are currently entangled into one complicated algorithm. We propose to disentangle the parts by finding a separate direct algorithm for the Three-Elements Problem; in this problem we are given three columns of a matrix and we ask whether or not there is a "circuit" in the matrix that contains all three of the given elements.***(2) Improve the analysis of the algorithms. The Minor-Testing Theorem gives an efficient that searches for a particular "minor" in a given matroid. The theorem currently only shows that there exists an efficient algorithm, but it does not explicity hand you an algorithm that could be programmed into a computer. ****(3) Develop a better understanding of frame matroids. "Frame matroids" arise in the Matroid Minors structure theory as the most important minor-closed class of matroids. However, at this stage we do not understand the class very well. We propose to address this by developing an algorithm for recognizing frame matroids.***(4) Develop applications in coding theory. Binary linear codes are of fundamental importance in information theory, and the distance of a code measures its tolerance to errors. The problem of computing the distance of a binary linear code is known to be "NP-hard", which means that it is unlikely that there exists an efficient algorithm. However, we hope to develop efficient algorithms when the code is chosen from any fixed "minor-closed" class of codes. ****** **
Robertson和Seymour的“图小项目”(Graph minor Project)由23篇论文组成,这些论文改变了图论领域,并对理论计算机科学产生了重大影响;超过6500次的引用见证了这种影响的程度。矩阵理论为涉及图和矩阵的问题提供了一个统一的框架,并在组合优化、编码理论、信息论和计算生物学等不同领域有应用。本文的研究特别适用于编码理论,因为线性码与可表示的拟阵是有效的相同的,并且由于次元在码上给出了自然的包含关系。***自1999年以来,我一直与Bert Gerards(荷兰Centrum voor Wiskunde en Informatica)和Geoff Whittle(新西兰惠灵顿维多利亚大学)合作,将Neil Robertson和Paul Seymour的Graph minor项目扩展到拟阵。我们的Matroid未成年人项目已经取得了惊人的成功,大多数主要目标已经实现。这个提议解决了一些基本的算法问题。***我们的主要目标是:***(1)简化矩阵未成年人项目的算法。目前,Matroid minor项目的三个计算方面(即Minor-Testing定理、构造版的Matroid minor结构定理和三要素问题)被纠缠在一个复杂的算法中。我们建议通过寻找一种单独的直接算法来解三要素问题;在这个问题中,我们有一个矩阵的三列,我们问矩阵中是否存在一个包含所有三个给定元素的“电路”。***(2)改进算法分析。次要检验定理给出了在给定矩阵中搜索特定“次要”的有效方法。这个定理目前只表明存在一个有效的算法,但它并没有明确地给你一个可以被编程到计算机中的算法。****(3)加深对框架拟阵的理解。“框架拟阵”作为拟阵中最重要的小闭类,出现在拟阵minor结构理论中。然而,在这个阶段,我们并没有很好地理解这个类。我们建议通过开发一种识别框架拟阵的算法来解决这个问题。***(4)开发编码理论的应用。二进制线性码在信息论中具有重要的基础地位,码的距离衡量了码的容错能力。计算二进制线性码的距离的问题被称为“NP-hard”,这意味着不太可能存在有效的算法。然而,我们希望开发有效的算法,当代码是从任何固定的“小闭”类代码中选择时。* * * * * * * *
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Geelen, Jim其他文献
Packing non-zero A-paths in group-labelled graphs
- DOI:
10.1007/s00493-006-0030-1 - 发表时间:
2006-01-01 - 期刊:
- 影响因子:1.1
- 作者:
Chudnovsky, Maria;Geelen, Jim;Seymour, Paul - 通讯作者:
Seymour, Paul
An algorithm for packing non-zero A-paths in group-labelled graphs
- DOI:
10.1007/s00493-008-2157-8 - 发表时间:
2008-01-01 - 期刊:
- 影响因子:1.1
- 作者:
Chudnovsky, Maria;Cunningham, William H.;Geelen, Jim - 通讯作者:
Geelen, Jim
Geelen, Jim的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Geelen, Jim', 18)}}的其他基金
Algorithms and structural matroid theory
算法和结构拟阵理论
- 批准号:
RGPIN-2016-03886 - 财政年份:2021
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual
Algorithms and structural matroid theory
算法和结构拟阵理论
- 批准号:
RGPIN-2016-03886 - 财政年份:2019
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual
Algorithms and structural matroid theory
算法和结构拟阵理论
- 批准号:
RGPIN-2016-03886 - 财政年份:2017
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual
Algorithms and structural matroid theory
算法和结构拟阵理论
- 批准号:
RGPIN-2016-03886 - 财政年份:2016
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual
Canada Research Chair in Combinatorial Optimization
加拿大组合优化研究主席
- 批准号:
1000208904-2008 - 财政年份:2013
- 资助金额:
$ 3.93万 - 项目类别:
Canada Research Chairs
Canada Research Chair in Combinatorial Optimization
加拿大组合优化研究主席
- 批准号:
1000208904-2008 - 财政年份:2012
- 资助金额:
$ 3.93万 - 项目类别:
Canada Research Chairs
Canada Research Chair in Combinatorial Optimization
加拿大组合优化研究主席
- 批准号:
1000208904-2008 - 财政年份:2011
- 资助金额:
$ 3.93万 - 项目类别:
Canada Research Chairs
Canada Research Chair in Combinatorial Optimization
加拿大组合优化研究主席
- 批准号:
1000208904-2008 - 财政年份:2010
- 资助金额:
$ 3.93万 - 项目类别:
Canada Research Chairs
Canada Research Chair in Combinatorial Optimization
加拿大组合优化研究主席
- 批准号:
1000208904-2008 - 财政年份:2009
- 资助金额:
$ 3.93万 - 项目类别:
Canada Research Chairs
Canada Research Chair in Combinatorial Optimization
加拿大组合优化研究主席
- 批准号:
1000201835-2003 - 财政年份:2008
- 资助金额:
$ 3.93万 - 项目类别:
Canada Research Chairs
相似国自然基金
CuAgSe基热电材料的结构特性与构效关系研究
- 批准号:22375214
- 批准年份:2023
- 资助金额:50.00 万元
- 项目类别:面上项目
Understanding structural evolution of galaxies with machine learning
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
染色体结构维持蛋白1在端粒DNA双链断裂损伤修复中的作用及其机理
- 批准号:31801145
- 批准年份:2018
- 资助金额:25.0 万元
- 项目类别:青年科学基金项目
典型团簇结构模式随尺度变化的理论计算研究
- 批准号:21043001
- 批准年份:2010
- 资助金额:10.0 万元
- 项目类别:专项基金项目
气动/结构耦合动力学系统目标敏感性分析的快速准确计算方法及优化设计研究
- 批准号:10402036
- 批准年份:2004
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
相似海外基金
Algorithms and structural matroid theory
算法和结构拟阵理论
- 批准号:
RGPIN-2016-03886 - 财政年份:2021
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual
Applications of structural matroid theory to minor-closed classes of codes
结构拟阵理论在小闭类码中的应用
- 批准号:
RGPIN-2016-04131 - 财政年份:2021
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual
Applications of structural matroid theory to minor-closed classes of codes
结构拟阵理论在小闭类码中的应用
- 批准号:
RGPIN-2016-04131 - 财政年份:2020
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual
Applications of structural matroid theory to minor-closed classes of codes
结构拟阵理论在小闭类码中的应用
- 批准号:
RGPIN-2016-04131 - 财政年份:2019
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual
Algorithms and structural matroid theory
算法和结构拟阵理论
- 批准号:
RGPIN-2016-03886 - 财政年份:2019
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual
Applications of structural matroid theory to minor-closed classes of codes
结构拟阵理论在小闭类码中的应用
- 批准号:
RGPIN-2016-04131 - 财政年份:2018
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual
Algorithms and structural matroid theory
算法和结构拟阵理论
- 批准号:
RGPIN-2016-03886 - 财政年份:2017
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual
Applications of structural matroid theory to minor-closed classes of codes
结构拟阵理论在小闭类码中的应用
- 批准号:
RGPIN-2016-04131 - 财政年份:2017
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual
Algorithms and structural matroid theory
算法和结构拟阵理论
- 批准号:
RGPIN-2016-03886 - 财政年份:2016
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual
Applications of structural matroid theory to minor-closed classes of codes
结构拟阵理论在小闭类码中的应用
- 批准号:
RGPIN-2016-04131 - 财政年份:2016
- 资助金额:
$ 3.93万 - 项目类别:
Discovery Grants Program - Individual