Minmax relations for graphs

图的最小极大关系摘要图是各种网络的数学模型，包括通信网络、交通网络和社会网络。许多重要的网络参数，如容量、灵活性和可靠性，往往很难计算。这个项目的目标是确定这些参数中的一些参数是可以有效计算的图。为了实现这一点，PI建议研究最优解的结构。准确地说，PI建议研究组合优化中的以下三个基本问题：1.刻画奇数st-路的(边集)杂乱是理想/门格尔的图。该问题推广了普通的匹配问题和普通的边不相交路径问题。2.刻画奇圈(顶点集)杂波为理想/门格图的图。这是一个与t-完美图问题密切相关的问题，t-完美图问题是在研究图中的稳定集时自然产生的。这个项目的目标之一是发现这两个问题之间的联系。3.刻画完全2-边连通图。这是一个源于旅行商问题研究的问题。它的一个吸引人的性质是，完全2-边连通是在诱导-次要关系的“对偶”下保持的，而诱导-次要关系是一种由许多重要的图性质保持的图包含关系。它们在许多方面类似于完美图问题：它们都涉及美丽的极大极小关系，它们都具有多面体和算法含义，它们都推广了许多已知的结果。

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.