Author

Sort by: Order: Results:

  • Parameterized Complexity of Satisfactory Partition Problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN; TRIPATHI, SHUVAM KANT (Springer Nature, 2020-12)
    The Satisfactory Partition problem consists in deciding if the set of vertices of a given undirected graph can be partitioned into two nonempty parts such that each vertex has at least as many neighbours in its part as in ...
  • Parameterized Complexity of Locally Minimal Defensive Alliances 
    GAIKWAD, AJINKYA; MAITY, SOUMEN; TRIPATHI, SHUVAM KANT (Springer Nature, 2021-01)
    A defensive alliance in a graph G=(V,E) is a set of vertices S satisfying the condition that every vertex v∈S has at least as many neighbours (including itself) in S as it has in V∖S . We consider the notion of local ...
  • Parameterized Complexity of Defensive and Offensive Alliances in Graphs 
    GAIKWAD, AJINKYA; MAITY, SOUMEN; TRIPATHI, SHUVAM KANT (Springer Nature, 2021-01)
    In this paper we study the problem of finding small defensive and offensive alliances in a simple graph. Given a graph G=(V,E) and a subset S⊆V(G) , we denote by dS(v) the degree of a vertex v∈V in G[S], the subgraph of G ...
  • The Balanced Satisfactory Partition Problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN; TRIPATHI, SHUVAM KANT (Springer Nature, 2021-01)
    The Satisfactory Partition problem asks whether it is possible to partition the vertex set of a given undirected graph into two parts such that each vertex has at least as many neighbours in its own part as in the other ...
  • On Structural Parameterizations of the Offensive Alliance Problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Springer Nature, 2021-12)
    The OFFENSIVE ALLIANCE problem has been studied extensively during the last twenty years. A set S⊆V of vertices is an offensive alliance in an undirected graph G=(V,E) if each v∈N(S) has at least as many neighbours in S ...
  • Parameterized Intractability of Defensive Alliance Problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN; TRIPATHI, SHUVAM KANT (Springer Nature, 2022-01)
    The DEFENSIVE ALLIANCE problem has been studied extensively during the last twenty years. A set R of vertices of a graph is a defensive alliance if, for each element of R, the majority of its neighbours are in R. The problem ...
  • On the Harmless Set Problem Parameterized by Treewidth 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Springer Nature, 2022-03)
    Given a graph G=(V,E), a threshold function t : V→N and an integer k, we study the HARMLESS SET problem, where the goal is to find a subset of vertices S⊆V of size at least k such that every vertex v in V has less than ...
  • Parameterized Complexity of the Th+1 -Free Edge Deletion Problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Springer Nature, 2023-09)
    Given an undirected graph G=(V,E) and two integers k and h, we study Th+1 -FREE EDGE DELETION, where the goal is to remove at most k edges such that the resulting graph does not contain any tree on h+1 vertices as a ...
  • Parameterized Complexity of the -Free Edge Deletion Problem Th+1 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Springer Nature, 2023-09)
    Given an undirected graph and two integers k and h, we study -FREE EDGE DELETION, where the goal is to remove at most k edges such that the resulting graph does not contain any tree on vertices as a (not necessarily ...

Search Repository


Advanced Search

Browse

My Account