Subject

Sort by: Order: Results:

  • Parameterized complexity of fair feedback vertex set problem 
    Kanesh, Lawqueen; MAITY, SOUMEN; Muluk, Komal; Saurabh, Saket (Elsevier B.V., 2021-05)
    Given a graph , a subset is said to be a feedback vertex set of G if is a forest. In the Feedback Vertex Set (FVS) problem, we are given an undirected graph G, and a positive integer k, the question is whether there ...
  • The Small Set Vertex Expansion Problem 
    AGRAWAL, GARIMA; MAITY, SOUMEN (Elsevier B.V., 2021-09)
    In the Small Set Vertex Expansion (SSVE) problem, we are given a graph and a positive integer , the goal is to return a set of k nodes minimizing the vertex expansion . The Small Set Vertex Expansion problem has not been ...
  • Parameterized complexity of satisfactory partition problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN; TRIPATHI, SHUVAM KANT (Elsevier B.V., 2022-03)
    Given an undirected graph G, we study the Satisfactory Partition problem, where the goal is to decide whether it is possible to partition the vertex set of G into two parts such that each vertex has at least as many ...
  • Globally minimal defensive alliances 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Elsevier B.V., 2022-08)
    A defensive alliance in an undirected graph is a nonempty set of vertices S satisfying the condition that every vertex has at least as many neighbours (including itself) in S as it has in . We consider the notion of ...
  • Defensive alliances in graphs 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Elsevier B.V., 2022-09)
    A set S of vertices of a graph is a defensive alliance if, for each element of S, the majority of its neighbours are in S. We study the parameterised complexity of Defensive Alliance, where the aim is to find a minimum ...
  • Further parameterized algorithms for the -free edge deletion problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Elsevier B.V., 2022-10)
    Given a graph �=(�,�) and a set � of forbidden subgraphs, we study the �-FREE EDGE DELETION problem, where the goal is to remove a minimum number of edges such that the resulting graph does not contain any �∈� as a (not ...
  • On Structural Parameterizations of the Harmless Set Problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Springer Nature, 2024-01)
    In this paper, we study the HARMLESS SET problem from a parameterized complexity perspective. Given a graph G=(V,E), a threshold function t : V -> N and an integer k, we study HARMLESS SET, where the goal is to find a ...
  • Offensive alliances in graphs 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Elsevier B.V., 2024-03)
  • Parameterized complexity of locally minimal defensive alliances 
    GAIKWAD, AJINKYA; MAITY, SOUMEN; TRIPATHI, SHUVAM KANT (Elsevier B.V., 2025-09)
    A set S of vertices of a graph is a defensive alliance if, for each element of S, the majority of its neighbours is in S. We consider the notion of local minimality in this paper. We are interested in locally minimal ...

Search Repository


Advanced Search

Browse

My Account