Blar i Faculty of Mathematics and Natural Sciences på emneord "Algorithms"

Viser treff 1-5 av 5

    • Computation of Treespan. A Generalization of Bandwidth to Treelike Structures 

      Dregi, Markus Sortland (Master thesis, 2012-06-14)
      Motivated by a search game, Fomin, Heggernes and Telle [Algorithmica, 2005] defined the graph parameter treespan, a generalization of the well studied parameter bandwidth. Treespan is the maximum number of appearances of ...

    • Independent Set on P5-free graphs, an empirical study 

      Haug, Håvard Karim (Master thesis, 2015-11-20)
      We implement the recent polynomial time algorithm for the independent set problem on P5-free graphs, and study the performance of this algorithm on graphs of size up to 50. Our empirical results show that the algorithm is ...

    • Kernelization for Balanced Graph Clustering 

      Steinvik, Andreas (Master thesis, 2020-10-03)
      The problems of Balanced Graph Clustering ask whether it is possible to modify a graph such that it becomes a cluster graph where no cluster has a size larger than a given multiplicative factor or absolute difference ...

    • A Note on Exact Algorithms for Vertex Ordering Problems on Graphs 

      Bodlaender, Hans L.; Fomin, Fedor; Koster, Arie M.C.A.; Kratsch, Dieter; Thilikos, Dimitrios M. (Peer reviewed; Journal article, 2011-01-21)
      In this note, we give a proof that several vertex ordering problems can be solved in O ∗(2 n ) time and O ∗(2 n ) space, or in O ∗(4 n ) time and polynomial space. The algorithms generalize algorithms for the Travelling ...

    • A polynomial-time solvable case for the NP-hard problem Cutwidth 

      Lilleeng, Simen (Master thesis, 2014-06-02)
      The Cutwidth problem is a notoriously hard problem, and its complexity is open on several interesting graph classes. Motivated by this fact we investigate the problem on superfragile graphs, a graph class on which the ...