Algorithmic aspects of some vertex ordering problems

Author: 
Date created: 
2016-08-11
Identifier: 
etd9743
Keywords: 
Combinatorial Optimization
Vertex Ordering Problems
Directed Feedback Arc Set
Minimum Linear Arrangement
Bipartite Ordering Problem
Abstract: 

Combinatorial Optimization problems play central role in applied mathematics and computer science. A particular class of combinatorial optimization problems is vertex ordering problems whose goal is to find an ordering on vertices of an input graph in such way that a certain objective cost is optimized. This thesis focuses on three different vertex ordering problems. First, we consider a variant of Directed Feedback Arc Set problem with applications in computational biology. We present an efficient heuristic algorithm for this problem. Next, we concentrate on parameterized complexity of Minimum Linear Arrangement problem while the parameter is size of vertex cover. We formulate the problem as Quadratic Integer Programming and propose two new techniques to tackle the problem. Finally, we introduce a vertex ordering problem on bipartite graphs with applications in different areas. We give a general algorithmic strategy for the problem, as well as, polynomial-time algorithms for three classes of graphs.

Document type: 
Thesis
Rights: 
This thesis may be printed or downloaded for non-commercial research and scholarly purposes. Copyright remains with the author.
File(s): 
Senior supervisor: 
Ladislav Stacho
Cedric Chauve
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.
Statistics: