Collaborative research on degree conditions for packing and covering problems on graphs

图上包装覆盖问题度条件的协同研究

• 批准号: 0652306
• 负责人: Gexin Yu
• 金额: $ 8.04万
• 依托单位: Vanderbilt University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-06-01 至 2008-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0652306&HistoricalAwards=false
• 关键词: Collaborative; research; degree; conditions; packing

Packing and covering are dual notions that are basic in combinatorial optimization and in combinatorics, in general. They are different and yet very closely related. One important instance of combinatorial packing problems is that of graph packing. Graphs of size n pack, if there exists an edge disjoint placement of all these graphs into the complete graph with n vertices. Various classical combinatorial problems can be modeled as packing or covering problems.For example, the problem of existence of a spanning cycle in an n-vertex graph is the question whether the n-cycle packs with the complement of G. Important examples of packing and covering problems are problems on existence of a given subgraph, coloring problems, Turan-type problems, domination problems and Ramsey-type problems. These examples (and many more) show that (hyper)graph packings and coverings are rather general problems and are rich enough models for many important applications. Areas of application include scheduling, database access, assignment of computer registers, data clustering, computer-aided design of printed circuits, positional games, DNA sequencing, etc.The main thrust of the project is to explore a series of extremal packing and covering problems for graphs and hypergraphs, with restrictions on degrees of their vertices. It is expected that the results will make an essential step in understanding extremal packing and covering problems for graphs and hypergraphs.Some proofs can lead to efficient packing and covering algorithms; negative results will impose limits on what can be accomplished. The particular packing problem of equitable coloring has many applications in scheduling, partitioning, and load balancing problems. It will be studied also from an algorithmic viewpoint. A fair amount of the work will be done jointly with graduate students and recent graduates of the University of Illinois at Urbana-Champaign.

一般来说，包装和覆盖是组合优化和组合学中的基本概念。它们是不同的，但又非常密切相关。组合包装问题的一个重要例子是图包装。图的大小为n包，如果存在一个边不相交的所有这些图的位置到完全图的n个顶点。各种经典的组合问题都可以建模为填充或覆盖问题，例如，n-顶点图的生成圈的存在性问题就是n-圈是否与G的补填充的问题.填充和覆盖问题的重要例子是给定子图的存在性问题、着色问题、Turan型问题、控制问题和Ramsey型问题。这些例子（以及更多）表明（超）图填充和覆盖是相当普遍的问题，并且对于许多重要的应用来说是足够丰富的模型。应用领域包括调度、数据库访问、计算机寄存器分配、数据聚类、计算机辅助印刷电路设计、位置游戏、DNA测序等。该项目的主要目的是探索图和超图的一系列极值包装和覆盖问题，并限制其顶点的度。我们期望这些结果将为理解图和超图的极值填充和覆盖问题迈出重要的一步。一些证明可以导致有效的填充和覆盖算法;否定的结果将限制我们所能完成的工作。均匀着色的特殊装箱问题在调度、划分和负载平衡问题中有许多应用。它也将从算法的角度进行研究。相当多的工作将与伊利诺伊大学厄巴纳-香槟分校的研究生和应届毕业生共同完成。