CALDAM 2022

8th Annual International Conference on Algorithms and Discrete Applied Mathematics

Pondicherry University, Puducherry, India.

February 10-12, 2022


The online proceedings are here. (This URL gives free access to the proceedings for a limited time.)


======================= 10th Feb ========================


9:00-9:30 am IST

Inaugural Session


---------------------------------------------------------

9:30-10:45 am

Google Invited Talk I

Chair: R. Inkulu


Approximation Algorithms for Some Geometric Optimization Problems [abstract]

Joseph S. B. Mitchell


---------------------------------------------------------

10:45-11:00 am

Break

---------------------------------------------------------


COMPUTATIONAL GEOMETRY

Chair: Antoine Vigneron


11:00-11:25 am

Coresets for $(k, \ell)$-Median Clustering under the Fréchet Distance

Maike Buchin, Dennis Rohde*


11:25-11:50 am

Bounds and Algorithms for Geodetic Hulls

Sabine Storandt*


11:50-12:15 pm

Voronoi Games using Geodesics

Arun Kumar Das*, Sandip Das, Anil Maheshwari, Sarvottamananda Swami


---------------------------------------------------------

12:15-2:00 pm

Lunch Break

---------------------------------------------------------


GRAPH ALGORITHMS I

Chair: Van Bang Le


2:00-2:25 pm

Complexity of Paired Domination in AT-free and Planar Graphs

Vikash Tripathi*, Ton Kloks, Arti Pandey, Kaustav Paul, Hung-Lung Wang


2:25-2:50 pm

The Complexity of Star Colouring in Bounded Degree Graphs and Regular Graphs

Shalu M A, Cyriac Antony*


2:50-3:15 pm

On cd-coloring of {P_5, K_4}-free chordal graphs

Shalu M A, Kirubakaran V K*


3:15-3:40 pm

B0-VPG Representation of AT-free Outerplanar Graphs

Sparsh Jain, Sreejith K. Pallathumadam*, Deepak Rajendraprasad


---------------------------------------------------------

3:40-4:00 pm

Break

---------------------------------------------------------


ALGORITHMS AND OPTIMIZATION I

Chair: Martin Furer


4:00-4:25 pm

On Fair Division with Binary Valuations Respecting Social Networks

Neeldhara Misra*, Debanuj Nayak


4:25-4:50 pm

Parameterized Intractability of Defensive Alliance Problem

Soumen Maity, Ajinkya Gaikwad*, Shuvam Kant Tripathi


4:50-5:15 pm

Algebraic algorithms for variants of Subset Sum

Pranjal Dutta*, Mahesh Rajasree


---------------------------------------------------------


5:15-6:00 pm

CALDAM Business Meeting

ACSDM Business Meeting

Chair: Prof. Subir Kumar Ghosh


======================= 11th Feb ========================


9:30-10:45 am

Google Invited Talk II

Chair: Amitabha Bagchi


Linear Programming and its uses in Algorithm Design [abstract]

Daya Gaur


---------------------------------------------------------

10:45-11:00 am

Break

---------------------------------------------------------


ALGORITHMS AND OPTIMIZATION II

Chair: C. R. Subramanian


11:00-11:25 am

Algorithms for Online Car-sharing Problem

Xiangyu Guo, Kelin Luo*


11:25-11:50 am

Covering a Graph with Densest Subgraphs

Riccardo Dondi*, Alexandru Popa


11:50-12:15 pm

Hardness and Approximation Results for Some Variants of Stable Marriage Problem

B.S. Panda, Sachin*


12:15-12:40 pm

Approximation Algorithms in Graphs with Known Broadcast time of the Base Graph

Puspal Bhabak, Hovhannes Harutyunyan*


12:40-1:05 pm

Approximation and parameterized algorithms for balanced connected partition problems

Phablo Moura, Matheus Jun Ota*, Yoshiko Wakabayashi


---------------------------------------------------------

1:05-2:00 pm

Lunch Break

---------------------------------------------------------


GRAPH THEORY

Chair: Iztok Peterin


2:00-2:25 pm

A proof of the multiplicative 1-2-3 conjecture

Julien Bensmail, Hervé Hocquard, Dimitri Lajou*, Éric Sopena


2:25-2:50 pm

Chromatic Bounds for Some Subclasses of $(P_3\cup P_2)$-free Graphs

Athmakoori Prashant*, Francis P, Francis Raj S


2:50-3:15 pm

List homomorphisms to separable signed graphs

Jan Bok, Richard Brewster, Tomás Feder, Pavol Hell, Nikola Jedličková*


3:15-3:40 pm

Some position problems for graphs

James Tuite*, Elias John Thomas, Ullas Chandran S. V.


3:40-4:05 pm

Comparability graphs among cover-incomparability graphs

Arun Anil*, Manoj Changat


======================= 12th Feb ========================


9:30-10:45 am

Google Invited Talk III

Chair: Niranjan Balachandran


All-Pairs Shortest Paths and Fine-Grained Complexity [abstract]

Timothy M. Chan


---------------------------------------------------------

10:45-11:00 am

Break

---------------------------------------------------------


GRAPH ALGORITHMS II

Chair: Francis Raj S


11:00-11:25 am

P versus NPC : Steiner tree in convex split graphs

A Mohanapriya*, Renjith P, sadagopan narasimhan


11:25-11:50 am

On Conflict-Free Spanning Tree: Algorithms and Complexity

Bruno Barros*, Luiz Satoru Ochi, Rian Pinheiro, Ueverton Souza


11:50-12:15 pm

An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs

Andrzej Lingas*, Mia Persson, Dzmitry Sledneu


12:15-12:40 pm

On the approximability of path and cycle problems in arc-dependent networks

Piotr Wojciechowski*, K. Subramani, Alvaro Velasquez, Williamson Matthew


---------------------------------------------------------

12:40-1:00 pm

Concluding Session

---------------------------------------------------------