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

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

• 批准号: 0650784
• 负责人: Alexandr Kostochka
• 金额: $ 15.77万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-06-01 至 2010-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0650784&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测序等。该项目的主要目的是探索图和超图的一系列极值包装和覆盖问题，并对其顶点度进行限制。预计这些结果将在理解极值填充和涵盖图和超图的问题方面迈出重要的一步。一些证明可以导致有效的打包和覆盖算法；消极的结果会限制我们所能取得的成就。公平着色的特殊包装问题在调度、分区和负载平衡问题中有许多应用。我们也将从算法的角度来研究它。相当数量的工作将与伊利诺伊大学厄巴纳-香槟分校的研究生和应届毕业生共同完成。