Short Bio

Since August, 2023, I have been a Lecturer at the University of Leeds as part of Algorithms and Complexity team in the School of Computing.

From October 2021 to August 2023, I was a LABEX-MILYON postdoctoral fellow in the MC2 team of LIP, ENS de Lyon, mentored by Édouard Bonnet.

From December, 2020 to August, 2021, I was a C.V. Raman Postdoctoral Fellow at the Indian Institute of Science, Bengaluru (IISc) mentored by Prof. L.S. Chandran.

From July, 2020 to November, 2020, I was a Senior Research Fellow at Indraprastha Institute of Information Technology, Delhi (IIITD) under the supervision of Prof. Rajiv Raman and Prof. Syamantak Das.

From July, 2014 to March, 2020, I completed my PhD from the department of Advanced Computing and Microelectronics Unit (ACMU), Indian Statistical Institute, Kolkata (ISI-Kolkata) under the supervision of Prof. Sandip Das.

From July, 2012 to July, 2014, I was a master's student (CS) at Ramakrishna Mission Vivekananda Educational & Research Institute .

July, 2009 to July, 2012, I was an undergraduate student (CS) @ Ramakrishna Mission Vidyamandira ( University of Calcutta )

Research interests

My broad interests lie in graph theory and graph algorithms. Currently, I am mostly working on the following topics:

• Graph theory
• Graph algorithms
• Algorithmic and structural aspects of geometric intersection graphs
• Approximation algorithms

Scientific activities

I am involved in the following funded research projects:

• AGraHom ("Applications of Graph Homomorphisms"), IFCAM-CEFIPRA, 2018-2021.
  Coordinators: Reza Naserasr and Sagnik Sen.

I have been a member of the programme committee of the following event:

• ALGOSENSORS 2021 (Lisboa, Portugal - online).

I have reviewd papers from the following journals:

• Algorithmica, Theoretical Computer Science, Discrete Applied Mathematics.

Publications

Submitted to Journal/Conferences

• DC, Carl Feghali , Reem Mahmoud. Kempe Equivalent List Colorings Revisited. [Arxiv]


• DC, Kshitij Gajjar, Irena Rusu. Recognizing Geometric Intersection Graphs Stabbed by a Line. [Arxiv]


• DC, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou. Algorithms and complexity for geodetic sets on interval and chordal graphs.


• DC, Harmender Gahlawat, Bodhayan Roy. Algorithms and complexity for geodetic sets on partial grids.

Journal Publications

• DC, Kshitij Gajjar. Finding Geometric Representations of Apex Graphs is NP-Hard. Theoretical Computer Science


• DC, Sandip Das, Joydeep Mukherjee. On dominating set of some subclasses of string graphs. Computational Geometry. 107: 101884 (2022). [www | Arxiv]


• DC, Sandip Das, Srijit Mukherjee, Uma kant Sahoo, Sagnik Sen. Triangle-free projective-planar graphs with diameter two: domination and characterization. Discrete Applied Mathematics (to appear) [Arxiv ]


• DC, Sandip Das, Mathew Francis, Sagnik Sen. On rectangle intersection graphs with stab number at most two. Discrete Applied Mathematics 289: 354-365 (2021) [www]


• DC, Mathew Francis. On the Stab Number of Rectangle Intersection Graphs . Theory of Computing Systems 64(5): 681-734 (2020) [www | Arxiv]


• A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, DC. Bottleneck bichromatic full Steiner trees. Information Processing Letters 142: 14-19 (2019) [www]


• DC, Sandip Das, Joydeep Mukherjee, Uma kant Sahoo. Bounds on the Bend Number of Split and Cocomparability Graphs. Theory of Computing Systems 63(6): 1336-1357 (2019) [www | Arxiv]


• DC, Partha Pratim Roy, Rajkumar Saini, Jose M. Alvarez, Umapada Pal. Frame selection for OCR from video stream of book flipping. Multimedia Tools Applications 77(1): 985-1008 (2018) [www]


• DC, Umapada Pal. Baseline detection of multi-lingual unconstrained handwritten text lines. Pattern Recognition Letters 74: 74-81 (2016) [www]

Conference publications

• DC, Jérémie Chalopin , Florent Foucaud, and Yann Vaxès. Isometric path complexity of graphs. MFCS, 2023. [Arxiv]


• Édouard Bonnet, DC, and Julien Duron. Cutting Barnette graphs perfectly is hard. WG, 2023. [Arxiv]


• DC, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat and Subir Kumar Ghosh. Complexity and algorithms for ISOMETRIC PATH COVER on chordal graphs and beyond. ISAAC, 2022. [HAL]


• Édouard Bonnet, DC, Eun Jung Kim, Noleen Köhler, Raul Lopes, Stéphan Thomassé. Twin-width VIII: delineation and win-wins. IPEC, 2022 (to appear) [Arxiv]


• DC, L. Sunil Chandran, Sajith Padinhatteeri, Raji R. Pillai. s-Club Cluster Vertex Deletion on Interval and Well-Partitioned Chordal Graphs. WG 2022.


• DC, Kshitij Gajjar. Finding Geometric Representations of Apex Graphs is NP-Hard. WALCOM 2022 [www]


• DC, L. Sunil Chandran, Sajith Padinhatteeri, Raji R. Pillai. Algorithms and Complexity of s-Club Cluster Vertex Deletion. IWOCA 2021: 152-164. [www]


• DC, Florent Foucaud, Harmender Gahlawat, and Bodhayan Roy. Hardness and Approximation for the Geodetic Set Problem in Some Graph Classes. CALDAM 2020: 102-115. [www]


• DC, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou and Bodhayan Roy. Algorithms and complexity for geodetic sets on planar and chordal graphs. ISAAC 2020. [www]


• DC, Sandip Das, Mathew Francis, Sagnik Sen. On rectangle intersection graphs with stab number at most two. CALDAM 2019 [www]


• DC, Sandip Das, Joydeep Mukherjee. Dominating Set on Overlap Graphs of Rectangles Intersecting a Line.. COCOON 2019. [www]


• DC, Sandip Das, Joydeep Mukherjee. Approximating Minimum Dominating Set on String Graphs.. WG 2019. [www]


• A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, DC. Bottleneck bichromatic full Steiner trees. CCCG 2017.


• Sujoy Bhore, DC, Sandip Das, Sagnik Sen. On Local Structures of Cubicity 2 Graphs. COCOA 2016: 254-269


• Sujoy Bhore, DC, Sandip Das, Sagnik Sen. On a Special Class of Boxicity 2 Graphs. CALDAM 2015: 157-168


• DC, Partha Pratim Roy, Jose M. Alvarez, Umapada Pal. OCR from Video Stream of Book Flipping. ACPR 2013: 130-134.


• DC, Partha Pratim Roy, Jose M. Alvarez, Umapada Pal. Duplicate open page removal from video stream of book flipping. NCVPRIPG 2013: 1-4.
  

Talks

• WG 2022. Title: s-Club Cluster Vertex Deletion on Interval and Well-Partitioned Chordal Graphs.


• Graphs@Lyon, 2022. Title: Finding Geometric Representations of Apex Graphs is NP-Hard.


• Metric Graph Theory, 2021. Title: Recent advances on algorithms for geodetic sets.


• International Conference on Emerging Trends in Mathematical Sciences & Computing, 2020 , Title: On geodetic sets of graphs.


• CALDAM, 2019 , Title: On rectangle intersection graphs with stab number at most two.


• COCOA, 2016 , Title: On Local Structures of Cubicity 2 Graphs.


• CALDAM, 2015 , Title: On a Special Class of Boxicity 2 Graphs.

Contacts

• Email: D.chakraborty@leeds.ac.uk