Preface
Chapter 1Introduction
1.1Algorithmic aspects of some vertex partitioning problems
1.1.1Monochromatic clique and rainbow cycle partitions
1.1.2Injective coloring problems
1.1.3Max hypergraph cut with limited unbalance
1.2Structural aspects of some edge partitioning and related problems
1.2.1Minim size of n-factor-critical and k-extendable graphs
1.2.2Matching alternating Hamilton cycles and directed Hamilton cycles
内容介绍
这项研究工作主要介绍了近几年我们从组合优化、算法、计算复杂性及结构图论领域的图划分问题和与匹配问题相关的系列问题中选择出的若干重要问题的研究成果。全书内容共分为七章，对全书的结构、各部分的关联和主要结论进行总体介绍，其余六章内容均可独立成篇（已发表在重要SCI学术期刊上），其中前三章主要介绍若干顶点划分问题的计算复杂性和算法分析，后三章主要对与匹配问题相关的若干重要图论问题进行结构研究，其中匹配问题也可看作是一种边划分问题。
This work is our selected results of research on graph partitioning and matching problems in the field of theoretical computer science and structural graph theory in recent years. After an introductory chapter， the reader will find six chapters， each of which is written as a self-contained content. In the first part of the work， Chapter 2 through 4， we concentrate on the complexity， inapproximability， approximation algorithms and on-line algorithms of some graph vertex partitioning problems. In the second part of the work， Chapter 5 through 7， we focus on the structural properties of some graph problems related to matching wluch can be regarded as edge partitioning problems. We refer to the listed chapters for the details of the results.
Chapter 1 contains a short general introduction to the topics of the book and gives an overview of the main results， together with some motivation and connections to and relationships with older results. Specific terminology and notation can be found just before each of the topic8.
In Chapter 2， we first investigate the computational complexity of problems of determining the minimum number of monochromatic cliques or rainbow cycles that， respe
评论晒单