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完整问题在仅限于这些对象类别时变为多项式。特别是我将调查以下问题：