Minmax relations for graphs

图的最小最大关系

• 批准号: 0556091
• 负责人: Guoli Ding
• 金额: $ 10.14万
• 依托单位: Louisiana State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-06-15 至 2010-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0556091&HistoricalAwards=false
• 关键词: Minmax; relations; graphs

Minmax relations for graphsAbstractA graph is a mathematical model for various networks, includingcommunication networks, transportation networks, and social networks. Manyimportant network parameters, like the capability, flexibility, andreliability, are often very difficult to compute. The goal of this projectis to identify graphs for which some of these parameters are efficientlycomputable. To accomplish this, the PI proposes to study the structure ofoptimal solutions. These structural results are fundamentally importantand they will have numerous applications on computing many related graphparameters.To be precise, the PI proposes to study the following three fundamentalproblems in combinatorial optimization: 1. To characterize graphs for which the clutter of (edge-sets of) odd st-paths is ideal/Mengerian. This problem generalizes the ordinary matching problem as well as the ordinary edge-disjoint paths problem. 2. To characterize graphs for which the clutter of (vertex-set of) odd circuits is ideal/Mengerian. This is a problem very closely related to the t-perfect graph problem, which arises naturally in the study of stable sets in graphs. One of the goals of this project is to discover the connections between these two problems. 3. To characterize perfectly 2-edge-connected graphs. This is a problem originated from the study of the Traveling Salesman Problem. One of its attractive properties is that being perfectly 2-edge-connected is preserved under the "dual" of the induced-minor relation, which is a graph containment relation preserved by many important graph properties.All the proposed problems are fundamental and attractive. They resemblethe perfect graph problem in many ways: they all involve beautiful minmaxrelations, they all have polyhedral and algorithmic implications, and theyall generalize many known results.

图是各种网络的数学模型，包括通信网络、交通网络和社交网络。许多重要的网络参数，如容量、灵活性和可靠性，通常很难计算。这个项目的目标是确定其中一些参数是有效计算的图形。为了实现这一点，PI建议研究最优解的结构。这些结构性的结果是非常重要的，它们将在计算许多相关的图参数上有许多应用。确切地说，PI建议研究组合优化中的以下三个基本问题： 1.刻画图的（边集）的杂乱性 奇数st-路是理想的/门格尔的。这个问题概括了 普通匹配问题以及普通边不相交问题 路径问题。 2.描述图的（顶点集）的杂乱性 奇数电路是理想的/门格尔的。这是一个非常密切的问题 与t-完美图问题有关， 在图中稳定集的研究中。其中一个目标是 这个项目的目的是发现这两者之间的联系 问题 3.刻画完美2-边连通图。这是一 一个问题起源于对旅行推销员的研究 问题.它的一个吸引人的特性是 完美的2-边连通在“对偶”下被保持， 导出子关系，这是一个图包含关系 所有提出的问题都是基本的和有吸引力的。他们在许多方面都在讨论完美图问题：他们都涉及到美丽的最小最大关系，他们都有多面体和算法的含义，他们都推广了许多已知的结果。