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.

GraphSabsTracta图的Minmax关系是用于各种网络的数学模型，包括通信网络，运输网络和社交网络。许多可能的网络参数，例如功能，灵活性和可靠性，通常很难计算。该项目的目的是识别这些参数中的某些参数可有效分解的图。为此，PI提议研究最佳溶液的结构。这些结构性结果在根本上至关重要，并且它们将在计算许多相关的图形参数时具有许多应用。要确切地说，PI提议研究组合优化中的以下三个基本问题：1。表征奇数（奇数）奇数（Edge-Edge-Sets）的奇数（奇数）是理想的/少年。这个问题概括了普通匹配问题以及普通的边缘路径问题。 2。表征图形的图形（顶点）奇数电路的混乱是理想的/Mengerian。这是一个与T完美的图形问题密切相关的问题，该问题自然而然地在图中稳定集的研究中引起。该项目的目标之一是发现这两个问题之间的联系。 3。表征完美的2边缘相关图。这是一个问题来自对旅行推销员问题的研究。它有吸引力的特性之一是，在诱导的少量关系的“双重”下保留了完美的2边缘连接，这是许多重要的图形属性保留的图形遏制关系。所有提出的问题都是基本的和有吸引力的。它们在许多方面都与完美的图形问题相似：它们都涉及美丽的Minmaxryations，它们都具有多面体和算法的含义，并且它们概括了许多已知的结果。