Algorithmic aspects of some vertex ordering problems

Resource type
Thesis type
(Thesis) M.Sc.
Date created
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.
Copyright statement
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Stacho, Ladislav
Thesis advisor: Chauve, Cedric
Member of collection
Attachment Size
etd9743_ARafiey.pdf 779.96 KB