Structural problems and minimax relations in graphs and matroids

图和拟阵中的结构问题和极小极大关系

• 批准号: 238811-2012
• 负责人: Guenin, Bertrand
• 金额: $ 1.24万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2012
• 资助国家: 加拿大
• 起止时间: 2012-01-01 至 2013-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=507980
• 关键词: Structural; problems; minimax; relations; graphs

In this research proposal I plan to investigate the structure of certain minor closed classes of graphs and binary matroids. The particular classes considered arise naturally in the context of combinatorial optimization. The motivation is fourfold: to provide the building blocks for understanding more complex classes of objects; to find common generalizations to flow and coloring results in graphs; to design efficient algorithms to recognize these classes of graphs and matroids; and to show that certain NP-complete problems become polynomial when restricted to these classes of objects. In particular I will investigate the following problems:

在这个研究计划中，我计划研究图和二拟阵的某些小闭类的结构。所考虑的特定类在组合优化的上下文中自然出现。动机有四个方面：为理解更复杂的对象类提供构建块；在图中找到流和着色结果的共同概括；设计有效的算法来识别这类图和拟阵；并证明某些np完全问题在被限制于这类对象时变成多项式。我将特别调查以下问题：