Skip to main content

6 Result(s)

within Article Remove this filter Pranabendu Misra Remove this filter

and

  1. Article

    Open Access

    Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number

    Fradkin and Seymour (J Comb Theory Ser B 110:19–46, 2015) defined the class of digraphs of bounded independence number as a generalization of the class of tournaments. They argued that the class of digraphs of...

    Pranabendu Misra, Saket Saurabh, Roohani Sharma, Meirav Zehavi in Algorithmica (2023)

    Download PDF (465 KB) View Article

  2. No Access

    Article

    Fast Exact Algorithms for Survivable Network Design with Uniform Requirements

    We design exact algorithms for the following two problems in survivable network design: (i) designing a minimum cost network with a desired value of edge connectivity, which is called Minimum Weight ...

    Akanksha Agrawal, Pranabendu Misra, Fahad Panolan, Saket Saurabh in Algorithmica (2022)

  3. Article

    Open Access

    Parameterized Complexity of Directed Spanner Problems

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

    Fedor V. Fomin, Petr A. Golovach, William Lochet, Pranabendu Misra… in Algorithmica (2022)

    Download PDF (384 KB) View Article

  4. No Access

    Article

    Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized

    Let π be a family of graphs. In the classical π-Vertex Deletion problem, given a graph G and a positive integer k, the objective is to check whether there exists a subset S of at most k vertices such that G − S i...

    Pallavi Jain, Lawqueen Kanesh, Pranabendu Misra in Theory of Computing Systems (2020)

  5. No Access

    Article

    Faster Parameterized Algorithms for Deletion to Split Graphs

    An undirected graph is said to be split if its vertex set can be partitioned into two sets such that the subgraph induced on one of them is a complete graph and the subgraph induced on the other is an independent...

    Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan… in Algorithmica (2015)

  6. No Access

    Article

    A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments

    In the k-Feedback Arc/Vertex Set problem we are given a directed graph D and a positive integer k and the objective is to check whether it is possible to delete at most k arcs/vertices from D to make it acyclic. ...

    Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan… in Theory of Computing Systems (2013)