Abstract
Original language  Undefined 

Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  9 May 2014 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036536264 
DOIs  
Publication status  Published  9 May 2014 
Keywords
 METIS303483
 IR90624
 MSC05C
 EWI24778
Cite this
}
Algorithmic and structural aspects of graph partitioning and related problems. / Zhang, X.
Enschede : Universiteit Twente, 2014. 158 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT
TY  THES
T1  Algorithmic and structural aspects of graph partitioning and related problems
AU  Zhang, X.
PY  2014/5/9
Y1  2014/5/9
N2  Graph partitioning problems enjoy many practical applications as well as algorithmic and theoretical challenges. This motivates the topics of this thesis that is composed of two parts. The first part of the thesis consists of Chapters 2 to 4. In this part, we present results on the complexity and inapproximability of some vertex partitioning problems, and we give approximation algorithms and online algorithms for some other vertex partitioning problems. We will start by investigating the inapproximability and complexity of the problems of finding the minimum number of monochromatic cliques and rainbow cycles that, respectively, partition V (G), where the graph G avoids some forbidden induced subgraphs. Secondly, we study the complexity, and develop approximation algorithms and online algorithms for injective coloring problems, to be defined later. Finally, we consider the design of a semidefinite programming based approximation algorithm for a variant of the max hypergraph cut problem. The second part of the thesis consists of Chapters 5 to 7. In this part, we turn our attention to structural properties of some problems that are related to matching problems which be regarded as edge partitioning problems. Firstly, we determine the minimum size of a kextendable bipartite graph and that of an nfactorcritical graph, and we study the problem of determining the minimum size of a kextendable nonbipartite graph. We solve this problem for k = 1 and k = 2, and we pose a conjecture related to the problem for general k. Secondly, we improve two equivalent structural results due to Woodall and Las Vergnas on the existence of a directed Hamilton cycle in a digraph and the containment of every perfect matching in a Hamilton cycle in a balanced (undirected) bipartite graph, respectively. Finally, we study a generalization of the maximum matching problem called the maximum triangle set problem, in which the aim is to find the maximum number of vertexdisjoint triangles of a given graph. We present a necessary and sufficient condition for augmenting triangle sets, analogous to the wellknown augmenting path result for matchings.
AB  Graph partitioning problems enjoy many practical applications as well as algorithmic and theoretical challenges. This motivates the topics of this thesis that is composed of two parts. The first part of the thesis consists of Chapters 2 to 4. In this part, we present results on the complexity and inapproximability of some vertex partitioning problems, and we give approximation algorithms and online algorithms for some other vertex partitioning problems. We will start by investigating the inapproximability and complexity of the problems of finding the minimum number of monochromatic cliques and rainbow cycles that, respectively, partition V (G), where the graph G avoids some forbidden induced subgraphs. Secondly, we study the complexity, and develop approximation algorithms and online algorithms for injective coloring problems, to be defined later. Finally, we consider the design of a semidefinite programming based approximation algorithm for a variant of the max hypergraph cut problem. The second part of the thesis consists of Chapters 5 to 7. In this part, we turn our attention to structural properties of some problems that are related to matching problems which be regarded as edge partitioning problems. Firstly, we determine the minimum size of a kextendable bipartite graph and that of an nfactorcritical graph, and we study the problem of determining the minimum size of a kextendable nonbipartite graph. We solve this problem for k = 1 and k = 2, and we pose a conjecture related to the problem for general k. Secondly, we improve two equivalent structural results due to Woodall and Las Vergnas on the existence of a directed Hamilton cycle in a digraph and the containment of every perfect matching in a Hamilton cycle in a balanced (undirected) bipartite graph, respectively. Finally, we study a generalization of the maximum matching problem called the maximum triangle set problem, in which the aim is to find the maximum number of vertexdisjoint triangles of a given graph. We present a necessary and sufficient condition for augmenting triangle sets, analogous to the wellknown augmenting path result for matchings.
KW  METIS303483
KW  IR90624
KW  MSC05C
KW  EWI24778
U2  10.3990/1.9789036536264
DO  10.3990/1.9789036536264
M3  PhD Thesis  Research UT, graduation UT
SN  9789036536264
PB  Universiteit Twente
CY  Enschede
ER 