Kolloquiumsvortrag: The Cyclic Cutwidth and Vertex Bisection Mininimization Problems
Institut für Informatik, Ludewig-Meyn-Str. 2, Übungsraum 2
Prof. Gursaran (Deemed University, Agra, India)
"The Cyclic Cutwidth and Vertex Bisection Mininimization Problems"
Graph layout problems are a class of combinatorial optimization problems whose goal is to find a layout of an input graph to optimize a certain objective function. A layout is the embedding of graph G into a host graph H and is defined as a bijective function mapping the vertices of G to the vertices of H and associating a path in H for each edge of G. These problems have been shown to be NP-complete in the general case. Cyclic cutwidth minimization problem and Vertex bisection minimization are two such problems.
Cyclic Cutwidth (ccw) Minimization Problem consists of embedding a graph onto a cycle such that the maximum cut in a region is minimized. Exact results have been proved for some standard graphs such as complete graphs, complete bipartite graphs, hypercubes, 2-dimensional cylindrical meshes, 2-dimensional meshes and partial results have been proved for 3-dimensional meshes.
Using layout based arguments, we have proved optimal results of cyclic cutwidth for some classes of graphs such as (m,n)-Tadpole graph, m-book graph, n-sun graph, cone graph, fan graph, crown graph, web graph, friendship graph, gear graph. Upper bounds for king graph, join of hypercubes, toroidal mesh, d-dimensional c-ary cliques, complete split graph and Halin graph have also been proved. We have also proposed a memetic algorithm for cyclic cutwidth minimization problem in which we have designed six construction heuristics to generate a good initial population and a local search operator to improve the solutions in each generational phase.
Vertex Bisection Minimization Problem (VBMP) consists of finding a linear layout which minimizes the number of vertices in the left half of the layout from which there are edges in the right half of the layout. This problem can also be defined as partitioning the vertex set V of size n into two sets B and B′ where such that is minimized where λB denotes the vertex width. NP-completeness of this problem has been proved and also it has been proved that this problem is polynomially solvable for trees and hypercubes.
We have proved optimal results for vertex bisection minimization problem for some classes of graphs such as complete bipartite graph, complete d-ary tree, threshold graph, complete split graph, m-book graph, friendship graph, 2-dimensional ordinary meshes. We have also designed a branch and bound algorithm in which we have proposed a strategy to find the lower bound and a greedy heuristic to find the upper bound in the initial phase.
The lecture will,
• Introduce the graph layout problem with particular emphasis on the cyclic cutwidth and vertex bisection problems
• Present some exact results and upper bounds for the cyclic cutwidth minimization problem
• Describe the memetic algorithm implementation for the cyclic cutwidth minimization problem
• Discuss some optimal results for the vertex bisection minimization problem, and
• Present the branch and bound implementation for the vertex bisection minimization problem.