Browsing Bergen Open Research Archive by Author "Rosamond, Frances"

Now showing items 1-3 of 3

    • Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory 

      Baste, Julien; Fellows, Michael Ralph; Jaffke, Lars; Masařík, Tomáš; Oliveira, Mateus De Oliveira; Philip, Geevarghese; Rosamond, Frances (Journal article; Peer reviewed, 2022)
      When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse ...

    • Finding k Disjoint Triangles in an Arbitrary Graph 

      Fellows, Mike; Heggernes, Pinar; Rosamond, Frances; Sloper, Christian; Telle, Jan Arne (Journal article; Peer reviewed, 2004)
      We consider the NP-complete problem of deciding whether an input graph on n vertices has k vertex-disjoint copies of a fixed graph H. For H=K 3 (the triangle) we give an O(22klog k + 1.869k n 2) algorithm, and for general ...

    • What Is Known About Vertex Cover Kernelization? 

      Fellows, Michael R.; Jaffke, Lars; Király, Aliz Izabella; Rosamond, Frances; Weller, Mathias (Peer reviewed; Journal article, 2018)
      We are pleased to dedicate this survey on kernelization of the Vertex Cover problem, to Professor Juraj Hromkovič on the occasion of his 60th birthday. The Vertex Cover problem is often referred to as the Drosophila of ...