Browsing Bergen Open Research Archive by Author "Misra, Pranabendu"

Now showing items 1-7 of 7

    • 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 ...

    • Fault tolerant subgraphs with applications in kernelization 

      Lochet, William; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav (Journal article; Peer reviewed, 2020)
      In the past decade, the design of fault tolerant data structures for networks has become a central topic of research. Particular attention has been given to the construction of a subgraph H of a given digraph D with as ...

    • 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 ...

    • On the Complexity of Recovering Incidence Matrices 

      Fomin, Fedor; Golovach, Petr; Misra, Pranabendu; Ramanujan, M.S. (Journal article; Peer reviewed, 2020)
      The incidence matrix of a graph is a fundamental object naturally appearing in many applications, involving graphs such as social networks, communication networks, or transportation networks. Often, the data collected about ...

    • Parameterized Complexity of Directed Spanner Problems 

      Fomin, Fedor; Golovach, Petr; Lochet, William; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2020)
      We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance ...

    • Parameterized Complexity of Directed Spanner Problems 

      Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2021)
      We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance ...

    • Quick separation in chordal and split graphs 

      Misra, Pranabendu; Panolan, Fahad; Rai, Ashutosh; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2020)
      In this paper we study two classical cut problems, namely Multicut and Multiway Cut on chordal graphs and split graphs. In the Multicut problem, the input is a graph G, a collection of 𝓁 vertex pairs (si, ti), i ∈ [𝓁], ...