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:
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