Browsing Bergen Open Research Archive by Author "Misra, Pranabendu"
Now showing items 17 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 nvertex 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 GS 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 tspanner problems on directed graphs. For a positive integer t, a multiplicative tspanner 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 tspanner problems on directed graphs. For a positive integer t, a multiplicative tspanner 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 ∈ [𝓁], ...