Algorithmic aspects of some vertex ordering problems

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.