描述
开 本: 128开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787030495020
编辑推荐
导语_点评_推荐词
内容简介
这项研究工作主要介绍了近几年我们从组合优化、算法、计算复杂性及结构图论领域的图划分问题和与匹配问题相关的系列问题中选择出的若干重要问题的研究成果。《图论中的图分割与图匹配问题（英文版）Some Advanced Topics of Graph Partitioning and Matching Problems》内容共分为七章，**章对《图论中的图分割与图匹配问题（英文版）Some Advanced Topics of Graph Partitioning and Matching Problems》的结构、各部分的关联和主要结论进行总体介绍，其余六章内容均可独立成篇（已发表在重要SCI学术期刊上），其中前三章主要介绍若干顶点划分问题的计算复杂性和算法分析，后三章主要对与匹配问题相关的若干重要图论问题进行结构研究，其中匹配问题也可看作是一种边划分问题。
目 录
Contents
Preface
Chapter 1 Introduction 1
1.1 Algorithmic aspects of some vertex partitioning problems 4
1.1.1 Monochromatic clique and rainbow cycle partitions 4
1.1.2 Injective coloring problems 7
1.1.3 Max hypergraph cut with limited unbalance 9
1.2 Structural aspects of some edge partitioning and related problems 15
1.2.1 Minimum size of n-factor-critical and k-extendable graphs 15
1.2.2 Matching alternating Hamilton cycles and directed Hamilton cycles 16
1.2.3 Structures for augmentation of vertex-disjoint triangle sets 19
Chapter 2 Minimum monochromatic clique partition and rainbow cycle partition 22
2.1 Inapproximability of MCLP on monochromatic-*free graphs 22
2.2 An approximation algorithm for WMCLP 26
2.3 RCYP is NP-complete for triangle-free graphs 30
2.4 Concluding remarks 33
Chapter 3 On the complexity of injective coloring 35
3.1 Off-line injective coloring 35
3.1.1 NP-hardness of injective coloring bipartite graphs 35
3.1.2 On the inapproximability of injective coloring bipartite graphs 37
3.1.3 An approximation algorithm for the max-injective coloring problem 39
3.2 On-line injective coloring 42
3.2.1 P3-free graphs 44
3.2.2 Triangle-free graphs and bipartite graphs 44
3.2.3 Concluding remarks 49
Chapter 4 An approximation algorithm for max hypergraph cut with limited unbalance 50
4.1 An SDP relaxation of MHC-LU 50
4.2 Bound on the expected contribution of an edge by Steps 1-4 56
4.3 Bounding * after Step 5 69
4.4 Bounding * 71
4.5 The quality of the SDP approximation algorithm 75
Chapter 5 Minimum size of n-factor-critical and k-extendable graphs 85
5.1 Minimum size of n-factor-critical graphs and k-extendable bipartite graphs 86
5.2 Minimum size of 1-extendable non-bipartite graphs and 2-extendable non-bipartite graphs 90
5.3 Concluding remarks 101
Chapter 6 Directed Hamilton cycles and matching alternating Hamilton cycles 102
6.1 Main results 102
6.2 Proof of Theorem 6.1.2 106
6.3 Concluding remarks 122
Chapter 7 Triangle strings: structures for augmentation of vertex-disjoint triangle sets 124
7.1 Triangle strings 125
7.2 Union graph of two triangle sets and an augmenting theorem 126
7.3 Triangle sets in triangle strings: an algorithm and a condition for triangle factors 133
References 138
Index 149
Preface
Chapter 1 Introduction 1
1.1 Algorithmic aspects of some vertex partitioning problems 4
1.1.1 Monochromatic clique and rainbow cycle partitions 4
1.1.2 Injective coloring problems 7
1.1.3 Max hypergraph cut with limited unbalance 9
1.2 Structural aspects of some edge partitioning and related problems 15
1.2.1 Minimum size of n-factor-critical and k-extendable graphs 15
1.2.2 Matching alternating Hamilton cycles and directed Hamilton cycles 16
1.2.3 Structures for augmentation of vertex-disjoint triangle sets 19
Chapter 2 Minimum monochromatic clique partition and rainbow cycle partition 22
2.1 Inapproximability of MCLP on monochromatic-*free graphs 22
2.2 An approximation algorithm for WMCLP 26
2.3 RCYP is NP-complete for triangle-free graphs 30
2.4 Concluding remarks 33
Chapter 3 On the complexity of injective coloring 35
3.1 Off-line injective coloring 35
3.1.1 NP-hardness of injective coloring bipartite graphs 35
3.1.2 On the inapproximability of injective coloring bipartite graphs 37
3.1.3 An approximation algorithm for the max-injective coloring problem 39
3.2 On-line injective coloring 42
3.2.1 P3-free graphs 44
3.2.2 Triangle-free graphs and bipartite graphs 44
3.2.3 Concluding remarks 49
Chapter 4 An approximation algorithm for max hypergraph cut with limited unbalance 50
4.1 An SDP relaxation of MHC-LU 50
4.2 Bound on the expected contribution of an edge by Steps 1-4 56
4.3 Bounding * after Step 5 69
4.4 Bounding * 71
4.5 The quality of the SDP approximation algorithm 75
Chapter 5 Minimum size of n-factor-critical and k-extendable graphs 85
5.1 Minimum size of n-factor-critical graphs and k-extendable bipartite graphs 86
5.2 Minimum size of 1-extendable non-bipartite graphs and 2-extendable non-bipartite graphs 90
5.3 Concluding remarks 101
Chapter 6 Directed Hamilton cycles and matching alternating Hamilton cycles 102
6.1 Main results 102
6.2 Proof of Theorem 6.1.2 106
6.3 Concluding remarks 122
Chapter 7 Triangle strings: structures for augmentation of vertex-disjoint triangle sets 124
7.1 Triangle strings 125
7.2 Union graph of two triangle sets and an augmenting theorem 126
7.3 Triangle sets in triangle strings: an algorithm and a condition for triangle factors 133
References 138
Index 149
前 言
序言
媒体评论
评论
书摘插画
评论
还没有评论。