LNCS 10156 Proceedings (accessible till March 6, 2017)

CALDAM 2017 Program

15 February 2017 

Welcome Dinner at 7.30pm

16 February 2017

Registration and Inauguration : 8-9.00

Invited Talk-Guenter Rote 9.00 - 10.15

Chair - Daya Gaur

Supported by Google

Tea Break 10.15-10.45

Invited talk - Martin Golumbic -10.45- 12.00

Chair - N.S. Naraynaswamy

Supported by Microsoft Research

Lunch 12.00 - 1.15pm

Session I- Approximations, NPC results

Chair - Ramesh Krishnamurthi


Klaus Jansen and Lars Rohwedder. Structured Instances of Restricted Assignment with Two Processing Times


Vladimir Braverman, Harry Lang and Keith Levin. Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams


P Renjith and Narasimhan Sadagopan. Hamiltonicity in Split Graphs- a dichotomy


Ante Custic, Ehsan Iranmanesh and Ramesh Krishnamurti. Analysis of 2-Opt Heuristic for the Winner Determination Problem under the Chamberlin-Courant System

Tea 2.55 - 3.25

Session II- Data Structures

Chair - Sudebkumar Prasant Pal


Arindam Biswas, Varunkumar Jayapaul and Venkatesh Raman. Improved bounds for poset sorting in the forbidden-comparison regime

3.50 - 4.15

Farah Chanchary, Anil Maheshwari and Michiel Smid. Querying Relational Event Graphs using Colored Range Searching Data Structures

4.15- 4.40

Varunkumar Jayapaul, Venkatesh Raman and Dishant Goyal. Elusiveness of finding degrees

Session III - Graph Factors, Hamiltonian Circuits, Tours, Pedigrees

Chair: B.S. Panda

4.40- 5.05

Sizhong Zhou, Tao Zhang and Zurun Xu. Subgraphs with orthogonal $[0,k_{i}]_{1}^{n}$-factorizations in graphs

5.05- 5.25

Sizhong Zhou, Yang Xu and Lan Xu. Stability number and k-Hamiltonian [a,b]-factors

5.25- 5.50

Abdullah Makkeh, Mozhgan Pourmoradnasseri and Dirk Oliver Theis. The Graph of the Pedigree Polytope is Asymptotically Almost Complete


Ulrik Brandes, Moritz Heine, Julian Müller and Mark Ortmann. Positional Dominance: Concepts and Algorithms

Business Meeting - 6.30pm

Chair : Subir Ghosh

17 February 2017

Invited talk- Ola Svensson - 9 - 10.15

Chair - N.S. Narayanaswamy

Supported by Microsoft Research

Tea Break 10.15-10.45

Invited talk - Sumit Ganguly - 10.45 - 12.00

Chair - Daya Gaur

Supported by Google

Lunch : 12-1.15

Session I- Structural Graph Theory

Chair : Satish Govindarajan

1.15 - 1.40

Ajit Diwan and Sai Sandeep. Decomposing semi-complete multigraphs and directed graphs into paths of length two

1.40 - 2.05

Manoj Changat, Ferdoos Hossein Nezhad and Narayanan Narayanan. Axiomatic Characterization of Interval Function of a Bipartite Graph

2.05 - 2.30

Arti Pandey, B.S. Panda, Manav Kashyap and Piyush Dane. Induced matching in some subclasses of bipartite graphs

2.30 - 2.55

Hovhannes A. Harutyunyan and Zhiyuan Li. Broadcast Graphs Using New Dimensional Broadcast Schemes for Kn{\"o}del Graphs

Tea 2.55 - 3.20

Session II- Geometry

Chair : Anil Maheshwari

3.20 - 3.45

Gill Barequet and Minati De. Voronoi Diagram for Convex Polygonal Sites with Convex Polygon-Offset Distance Function

3.45 - 4.10

Ramesh Jallu and Gautam K Das. Liar's Domination in 2D

4.10 - 4.35

Subhash Bhagat and Krishnendu Mukhopadhyaya. Optimum Gathering of Asynchronous Robots

4.35 - 5.00

Datta Krupa R, Aniket Basu Roy, Minati De and Sathish Govindarajan. Demand hitting and covering of intervals

Session III - Graph Algorithms

Chair - Tarkeshwar Singh


Sayan Bandyapadhyay and Aritra Banik. Polynomial Time Algorithms for Bichromatic Problems


Bireswar Das, Murali Krishna Enduri, Neeldhara Misra and Vinod Reddy. On Structural Parameterizations of Graph Motif and Chromatic Number


Diptapriyo Majumdar, Rian Neogi, Venkatesh Raman and Prafullkumar Tale. Exact And Parameterized Algorithms For $(k,i)$-coloring


Tushar Kalra, Rogers Mathew, Sudebkumar Prasant Pal and Vijay Pandey. Maximum weighted independent sets with a budget

Banquet - 7.30pm

18 February 2017

Computational Geometry

Chair: Partha Pratim Goswami


R Inkulu and Nitish Thakur. Incremental algorithms to update visibility polygons


Sandip Das, Ayan Nandy and Sarvottamananda Swami. Optimizing movement in a convex path-network to establish connectivity


Pavan Sangha and Michele Zito. Finding Large Independent Sets in Line of Sight Networks

Tea 10.15-10.30

Session II - Coloring

Chair - C.R. Subramanian

10.30 - 10.55

M A Shalu, S Vijayakumar and T P Sandhya. A lower bound of the cd-chromatic number and its complexity

10.55 - 11.20

Ajit Diwan and Bodhayan Roy. On colouring point visibility graphs

11.20 - 11.45

Sandip Das, Soumen Nandi and Sagnik Sen. On chromatic number of colored mixed graphs

Session III - Codes and Labelings

Chair - Manoj Changat

11.45 - 12.10

Sucheta Dutt and Arpana Garg. On Rank and MDR Cyclic codes of length $2^k$ over $Z_8$

12.10 - 12.35

Jessie Abraham and Micheal Arockiaraj. Optimal embedding of locally twisted cubes into grids

12.35 - 1.00

Aloysius Godinho and Tarkeshwar Singh. Group Distance Magic Labeling of $C_n^r$