Blar i Bergen Open Research Archive på forfatter "Philip, Geevarghese"

Viser treff 1-8 av 8

    • A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion 

      Lokshtanov, Daniel; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Journal article; Peer reviewed, 2020)
      In the Split Vertex Deletion (SVD) problem, the input is an n-vertex undirected graph G and a weight function w: V(G) → ℕ, and the objective is to find a minimum weight subset S of vertices such that G-S is a split graph ...

    • B-chromatic number: Beyond NP-hardness 

      Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Peer reviewed; Journal article, 2015)
      The b-chromatic number of a graph G, chi_b(G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other ...

    • Diverse Collections in Matroids and Graphs 

      Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Journal article; Peer reviewed, 2021)
      We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the Weighted Diverse ...

    • Diverse Pairs of Matchings 

      Fomin, Fedor; Golovach, Petr; Jaffke, Lars; Philip, Geevarghese; Sagunov, Danil (Journal article; Peer reviewed, 2020)
      We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse ...

    • 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 even subgraphs even faster 

      Goyal, Prachi; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Peer reviewed; Journal article, 2015)
      Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on n vertices and a positive integer parameter k, find if there exist k ...

    • FPT Algorithms for Diverse Collections of Hitting Sets 

      Baste, Julien; Jaffke, Lars; Masařík, Tomáš; Philip, Geevarghese; Rote, Günter (Peer reviewed; Journal article, 2019-11-27)
      In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of ...

    • Structural parameterizations of clique coloring 

      Jaffke, Lars; Lima, Paloma T.; Philip, Geevarghese (Journal article; Peer reviewed, 2020)
      A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether ...