5 citations · 5 across the 4 of their papers we have counts for
6 papers · 1 filter
Hardness and approximation for the geodetic set problem in some graph classes
Dibyayan Chakraborty, Florent Foucaud, Harmender Gahlawat +2
In this paper, we study the computational complexity of finding the \emph{geodetic number} of graphs. A set of vertices of a graph is a \emph{geodetic set} if any vertex of…
Approximating Minimum Dominating Set on String Graphs
Dibyayan Chakraborty, Sandip Das, Joydeep Mukherjee
In this paper, we give approximation algorithms for the \textsc{Minimum Dominating Set (MDS)} problem on \emph{string} graphs and its subclasses. A \emph{path} is a simple curve ma…
On the stab number of rectangle intersection graphs
Dibyayan Chakraborty, Mathew C. Francis
We introduce the notion of \emph{stab number} and \emph{exact stab number} of rectangle intersection graphs, otherwise known as graphs of boxicity at most 2. A graph is said to…
On bounds on bend number of split and cocomparability graphs
Dibyayan Chakraborty, Sandip Das, Joydeep Mukherjee +1
A path is a simple, piecewise linear curve made up of alternating horizontal and vertical line segments in the plane. A -bend path is a path made up of at most line segm…
On local structures of cubicity 2 graphs
Sujoy Kumar Bhore, Dibyayan Chakraborty, Sandip Das +1
A 2-stab unit interval graph (2SUIG) is an axes-parallel unit square intersection graph where the unit squares intersect either of the two fixed lines parallel to the -axis, dis…
On a special class of boxicity 2 graphs
Sujoy Kumar Bhore, Dibyayan Chakraborty, Sandip Das +1
We define and study a class of graphs, called 2-stab interval graphs (2SIG), with boxicity 2 which properly contains the class of interval graphs. A 2SIG is an axes-parallel rectan…