Author

Sort by: Order: Results:

  • Domination and Cut Problems on Chordal Graphs with Bounded Leafage 
    Galby, Esther; Marx, Dániel; Schepper, Philipp; Sharma, Roohani; TALE, PRAFULLKUMAR (Dagstuhl Publishing, 2022)
    The leafage of a chordal graph G is the minimum integer ℓ such that G can be realized as an intersection graph of subtrees of a tree with ℓ leaves. We consider structural parameterization by the leafage of classical ...
  • Romeo and Juliet Meeting in Forest like Regions 
    Misra, Neeldhara; Mulpuri, Manas; TALE, PRAFULLKUMAR; Viramgami, Gaurav (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2022-12)
    The game of rendezvous with adversaries is a game on a graph played by two players: Facilitator and Divider. Facilitator has two agents and Divider has a team of k ≥ 1 agents. While the initial positions of Facilitator’s ...
  • Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters 
    Galby, Esther; Khazaliya, Liana; Inerney, Fionn Mc; Sharma, Roohani; TALE, PRAFULLKUMAR (Society for Industrial and Applied Mathematics, 2023)
    For a graph G , a subset S⊆V(G) is called a resolving set if for any two vertices u, v∈ V (G) , there exists a vertex w ∈ S such that d(w,u)≠d(w,v) . The METRIC DIMENSION problem takes as input a graph G and a positive ...
  • A single exponential-time FPT algorithm for cactus contraction 
    Krithika, R.; Misra , Pranabendu; TALE, PRAFULLKUMAR (Elsevier B.V., 2023-04)
    For a collection F of graphs, the F-CONTRACTION problem takes a graph G and an integer k as input and decides if G can be modified to some graph in F using at most k edge contractions. The F-CONTRACTION problem is NP-Complete ...
  • Reducing the vertex cover number via edge contractions 
    Lima, Paloma T.; Santos, Vinicius F. dos; Sau, Ignasi; Souza, Uéverton S.; TALE, PRAFULLKUMAR (Elsevier B.V., 2023-09)
    Given a graph G on n vertices and two integers k and d, the Contraction(vc) problem asks whether one can contract at most k edges to reduce the vertex cover number of G by at least d. Recently, Lima et al. [JCSS 2021] ...
  • Parameterized complexity of multicut in weighted trees 
    Galby, Esther; Marx, Daniel; Schepper, Philipp; Sharma, Roohani; TALE, PRAFULLKUMAR (Elsevier B.V., 2023-11)
    In the Multicut problem, given an undirected graph G, a set of pairs of vertices P, and a budget k, the goal is to determine if there is a set S of at most k edges such that for each (s, t) is an element of P, the graph G ...
  • Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction 
    Krithika, R.; Malu, V. K. Kutty; Sharma, Roohani; TALE, PRAFULLKUMAR (Schloss Dagstuhl, 2023-12)
    A bipartite graph is called a biclique if it is a complete bipartite graph and a biclique is called a balanced biclique if it has equal number of vertices in both parts of its bipartition. In this work, we initiate the ...
  • Problems in NP Can Admit Double-Exponential Lower Bounds When Parameterized by Treewidth 
    Foucaud, Florent; Galby, Esther; Khazaliya, Liana; Li, Shaohua; Inerney, Fionn Mc; Sharma, Roohani; TALE, PRAFULLKUMAR (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2024-07)
    Treewidth serves as an important parameter that, when bounded, yields tractability for a wide class of problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and Quantified SAT or, more ...
  • Metric Dimension and Geodetic Set Parameterized by Vertex Cover 
    Foucaud, Florent; Galby, Esther; Khazaliya, Liana; Li, Shaohua; Inerney, Fionn Mc; Sharma, Roohani; TALE, PRAFULLKUMAR (Dagstuhl Publishing, 2025-02)
    For a graph G, a subset S ⊆ V (G) is called a resolving set of G if, for any two vertices u, v ∈ V (G), there exists a vertex w ∈ S such that d(w, u)̸ = d(w, v). The Metric Dimension problem takes as input a graph G on ...
  • Structural Parameterization of Locating-Dominating Set and Test Cover 
    Chakraborty, Dipayan; Foucaud, Florent; Majumdar, Diptapriyo; TALE, PRAFULLKUMAR (Springer Nature, 2025-05)
    We investigate structural parameterizations for two identification problems in graphs and set systems: Locating-Dominating Set and Test Cover. In the first problem, an input is a graph G and an integer k, and one asks ...

Search Repository


Advanced Search

Browse

My Account