Sounaka Mishra

activity

20142023

most citedFO and MSO approach to Some Graph Problems: Approximation and Poly time Results

1 citations · 1 across the 6 of their papers we have counts for

collaborators

7 papers

cs.CC2023

Disjoint Dominating and 2-Dominating Sets in Graphs: Hardness and Approximation results

Soumyashree Rana, Sounaka Mishra, Bhawani Sankar Panda

A set $D \subseteq V$ of a graph $G = (V, E)$ is a dominating set of $G$ if each vertex $v \in V ∖ D$ is adjacent to at least one vertex in $D,$ whereas a set $D_{2} \subseteq V$ …

cs.DS2023

On minimum $t$ -claw deletion in split graphs

Sounaka Mishra

For $t \geq 3$ , $K_{1, t}$ is called $t$ -claw. In minimum $t$ -claw deletion problem (\texttt{Min- $t$ -Claw-Del}), given a graph $G = (V, E)$ , it is required to find a vertex set $S$ of…

cs.DS2023

On the Complexity of Co-secure Dominating Set Problem

B S Panda, Soumyashree Rana, Sounaka Mishra

A set $D \subseteq V$ of a graph $G = (V, E)$ is a dominating set of $G$ if every vertex $v \in V ∖ D$ is adjacent to at least one vertex in $D .$ A set $S \subseteq V$ is a co-…

math.CO2023

Complexity of Near-3-Choosability Problem

Sounaka Mishra, Rohini S, Sagar S. Sawant

It is currently an unsolved problem to determine whether a $△$ -free planar graph $G$ contains an independent set $A$ such that $G [V_{G} ∖ A]$ is $2$ -choosable. However…

cs.DS2017

The Complexity of Maximum $k$ -Order Bounded Component Set Problem

Sounaka Mishra, Shijin Rajakrishnan

Given a graph $G = (V, E)$ and a positive integer $k$ , in Maximum $k$ -Order Bounded Component Set (Max- $k$ -OBCS), it is required to find a vertex set $S \subseteq V$ of maximum size…

cs.LO2017★ 1 cited

FO and MSO approach to Some Graph Problems: Approximation and Poly time Results

Kona Harshita, Sounaka Mishra, Renjith. P +1

The focus of this paper is two fold. Firstly, we present a logical approach to graph modification problems such as minimum node deletion, edge deletion, edge augmentation problems…

cs.DS2014

On the Complexity of Making a Distinguished Vertex Minimum or Maximum Degree by Vertex Deletion

Sounaka Mishra, Ashwin Pananjady, N Safina Devi

In this paper, we investigate the approximability of two node deletion problems. Given a vertex weighted graph $G = (V, E)$ and a specified, or "distinguished" vertex $p \in V$ , MDD(m…