9 citations · 22 across the 21 of their papers we have counts for
26 papers
Parameterized Complexity of Isometric Path Cover: Treewidth and Diameter
Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud +2
We study the fixed-parameter tractability of the \textsc{Isometric Path Cover} problem where, given an integer and a simple, undirected, and unweighted graph , the objective…
Additive Quasi-isometry via rooted graph partitions and layering partition
Dibyayan Chakraborty, Yann Vaxès
For a graph , denotes the class of all subdivisions of and denotes the treewidth of . In this paper, we prove the following. For $k\geq 1, R\g…
Minimum eccentricity shortest paths of -minor-free graphs
Dibyayan Chakraborty, Sandip Das, Sk Samim Islam +2
Given a simple, undirected, and unweighted graph , and an integer , the objective of the \textsc{Minimum Eccentricity Shortest Path (MESP)} is to decide whether there exists…
Algorithms and complexity for geodetic sets on interval and chordal graphs
Dibyayan Chakraborty, Sandip Das, Florent Foucaud +2
We study the computational complexity of finding the geodetic number of a graph on chordal graphs and interval graphs. A set of vertices of a graph is a \textit{geodetic se…
Parameterized complexity of isometric path partition: treewidth and diameter
Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud +2
We investigate the parameterized complexity of the Isometric Path Partition problem when parameterized by the treewidth () of the input graph, arguably one of the most…
Distance-based (and path-based) covering problems for graphs of given cyclomatic number
Dibyayan Chakraborty, Florent Foucaud, Anni Hakanen
We study a large family of graph covering problems, whose definitions rely on distances, for graphs of bounded cyclomatic number (that is, the minimum number of edges that need to…
-induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two
Dibyayan Chakraborty
A graph is an \emph{induced minor} of a graph if can be obtained from by a sequence of edge contractions and vertex deletions. Otherwise, is \emph{-induced m…
Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
Dibyayan Chakraborty, Florent Foucaud
The (strong) isometric path complexity is a recently introduced graph invariant that captures how arbitrary isometric paths (i.e., shortest paths) of a graph can be viewed as a uni…
Additive approximation algorithm for geodesic centers in -hyperbolic graphs
Dibyayan Chakraborty, Yann Vaxès
For an integer , the objective of \textsc{-Geodesic Center} is to find a set of isometric paths such that the maximum distance between any vertex …
Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud +1
In this paper, we study a dynamic analogue of the Path Cover problem, which can be solved in polynomial-time in directed acyclic graphs. A temporal digraph has an arc set that chan…
-binding functions for squares of bipartite graphs and its subclasses
Dibyayan Chakraborty, L. Sunil Chandran, Dalu Jacob +1
A class of graphs is -bounded if there exists a function such that for each graph , where and are the chro…
Cutting Barnette graphs perfectly is hard
Édouard Bonnet, Dibyayan Chakraborty, Julien Duron
A perfect matching cut is a perfect matching that is also a cutset, or equivalently a perfect matching containing an even number of edges on every cycle. The corresponding algorith…
Isometric path complexity of graphs
Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud +1
A set of isometric paths of a graph is ``-rooted'', where is a vertex of , if is one of the endpoints of all the isometric paths in . The isometric path co…
Triangle-free projective-planar graphs with diameter two: domination and characterization
Dibyayan Chakraborty, Sandip Das, Srijit Mukherjee +2
In 1975, Plesník characterized all triangle-free planar graphs as having a diameter . We characterize all triangle-free projective-planar graphs having a diameter and discus…
Kempe Equivalent List Colorings Revisited
Dibyayan Chakraborty, Carl Feghali, Reem Mahmoud
A \emph{Kempe chain} on colors and is a component of the subgraph induced by colors and . A \emph{Kempe change} is the operation of interchanging the colors of some…
s-Club Cluster Vertex Deletion on Interval and Well-Partitioned Chordal Graphs
Dibyayan Chakraborty, L. Sunil Chandran, Sajith Padinhatteeri +1
In this paper, we study the computational complexity of \textsc{-Club Cluster Vertex Deletion}. Given a graph, \textsc{-Club Cluster Vertex Deletion (-CVD)} aims to delete…
Recognizing Geometric Intersection Graphs Stabbed by a Line
Dibyayan Chakraborty, Kshitij Gajjar, Irena Rusu
In this paper, we determine the computational complexity of recognizing two graph classes, \emph{grounded L}-graphs and \emph{stabbable grid intersection} graphs. An L-shape is mad…
Twin-width VIII: delineation and win-wins
Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim +3
We introduce the notion of delineation. A graph class is said delineated if for every hereditary closure of a subclass of , it holds that $\ma…
Finding Geometric Representations of Apex Graphs is NP-Hard
Dibyayan Chakraborty, Kshitij Gajjar
Planar graphs can be represented as intersection graphs of different types of geometric objects in the plane, e.g., circles (Koebe, 1936), line segments (Chalopin \& Gon{ç}alves, 2…
Algorithms and complexity for geodetic sets on planar and chordal graphs
Dibyayan Chakraborty, Harmender Gahlawat, Bodhayan Roy
A set of vertices of a graph is a \emph{geodetic set} if every vertex of lies in a shortest path between some pair of vertices of . The \textsc{Minimum Geodetic Set…
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…