Asian Institute of Technology & Management, Khumaltar, Lalitpur

29-31 March 2016

 Download PDF

Pre Workshop Day: March 28, 2016 (Monday) 
17.00-21.00 Registration & Reception
Day 1: March 29, 2016 (Tuesday)
8.30-9.30 Registration
9.30-10.00 Inauguration
Invited Talk I (Chair: Rossella Petreschi)
10.00-11.00 Popping Super bubbles and Discovering Clumps: Recent Developments in Biological Sequence Analysis

-          Costas Iliopoulos

11.00-11.30 Refreshment
Session 1: Graphs Colouring (Chair: Franz Brandenburg)
11.30-11.55 Tropical Dominating Sets in Vertex-Coloured Graphs

-          J.A. Angles d’Auriac, C. Bujtas, H. El Maftouhi,M. Karpinski, Y. Manoussakis, L. Montero,N. Narayanan, L. Rosaz, J. Tapper and Z. Tuza

11.55 – 12.20 On hamiltonian colorings of block graphs-          Devsi Bantva
12.20 – 12.45 Vertex-Coloring with Star-Defects-          Patrizio Angelini, Michael Bekos, Michael Kaufmann and Vincenzo Roselli
12.45-14.00 Working Lunch



Session 2: Graphs Exploration (Chair: Ryuhei Uehara)
14.00-14.25 Lower Bounds for Graph Exploration Using Local Policies

-             Aditya Kumar Akash, Sandor Fekete, Seoung Kyou Lee, Alejandro Lopez-Ortiz, Daniela Maftulea and James McLurkin

14.25-14.50 Formation of General Position by Asynchronous Mobile Robots Under One-axis Agreement-            Subhash Bhagat, Sruti Gan Chaudhuri and Krishnendu Mukhopadhyaya
14.50-15.15 Optimal Distributed Searching in the Plane with and without Uncertainty-            Alejandro Lopez-Ortiz and Daniela Maftuleac
15.15-15.35 Tea Break
Invited Talk II (Chair: Mohammad Kaykobad)
15.35-16.35  2-Edge and 2-Vertex Connectivity Problems in Directed Graphs

-          Giuseppe F.Italiano

16.35-16.45 Break
Session 3: Graphs Algorithms (Chair: Giuseppe F. Italiano)
16.45-17.10  On Aligned Bar 1-Visibility Graph

-          Franz Brandenburg, Alexander Esch and Daniel Neuwirth

17.10-17.35 A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs-          Md. Iqbal Hossain, Sammi Abida Salma and Md. Saidur Rahman
17.35-18.00 Mixing Times of Markov Chains of 2-Orientations-          Stefan Felsner and Daniel Heldt
18.00-21.00 Business Meeting & Dinner






Day 2: March 30, 2016 (Wednesday)
Session 4: Computational Geometry (Chair: Md. Sohel Rahman)
9.00-9.25 Computing a Minimum-Width Square Annulus in Arbitrary Orientation

-          Sang Won Bae

9.25-9.50 A General Framework for Searching on a Line-          Prosenjit Bose and Jean-Lou De Carufel
9.50-10.15 An optimal algorithm for computing the integer closure of UTVPI constraints-          K. Subramani and Piotr Wojciechowski
10.15-10.40 Covering Points with Convex Sets of Minimum Size-          Hwan-Gue Cho, William Evans, Noushin Saeedi and Chan-Su Shin
10.40-11.00 Tea Break
 Invited Talk III (Chair: Ljiljana Brankovic)


11.00-12.00 Beyond Cyber-Physical Era: What’s Next?

-          Sajal Das

Session 5: Data Structures (Chair: Yannis Manoussakis)
12.00-12.25 Efficient Generation of Top-k Procurements in a Multi-Item Auction

-          Biswajit Sanyal, Subhashis Majumder and Wing-Kai Hon

12.25-12.50 Counting Subgraphs in Relational Event Graphs-          Farah Chanchary and Anil Maheshwari
12.50-14.05 Working Lunch
Session 6: Computational Complexity (Chair: Vangelis Paschos)
14.05-14.30 Large Independent Sets in Subquartic Planar Graphs

-          Matthias Mnich

14.30-14.55 As Close As It Gets-          Mike Behrisch, Miki Hermann, Stefan Mengel and Gernot Salzer
14.55-15.20 Shortest Reconfiguration of Sliding Tokens on a Caterpillar-          Takeshi Yamada and Ryuhei Uehara
15.20-15.40 Tea Break


Session 7 Approximation Algorithms (Chair: Sajal Das)
15.40-16.05 Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers

-          Toshihiro Fujito and Daichi Suzuki

16.05-16.30 Approximation Algorithms for Generalized Bounded Tree Cover-          Barun Gorain, Partha Sarathi, Mandaland and Krishnendu Mukhopadhyaya
16.30-16.55 Approximation Algorithms for Three Dimensional Protein Folding-          Dipan Lal Shaw, Md. Sohel Rahman, A. S. M. Sohidull Islam and Shuvasish Karmaker
16.55-17.20 Parameterization of Strategy-Proof Mechanisms in the Obnoxious Facility Game-          Morito Oomine, Aleksandar Shurbevski and Hiroshi Nagamochi
19.00-21.00 Banquet



Day 3: March 31, 2016 (Thursday)
Session 8: On-line Algorithms (Chair: Pramod Pradhan)
9.00-9.25 Optimal Online Algorithms for the Multi-Objective Time Series Search Problem

-          Shun Hasegawa and Toshiya Itoh

9.25-9.50 Fully Dynamically maintaining minimal integral separator for Threshold and Difference Graphs-          Tiziana Calamoneri, Angelo Monti and Rossella Petreschi
9.50-10.10 Tea Break
Invited Talk IV (Chair: Md. Saidur Rahaman)
10.10-11.10 Social Pressure can Subvert Majority in Social Networks

-          Giuseppe Persiano

11.10-11.20 Break
Session 9: Algorithms (Chair: Giuseppe Persiano)
11.20-11.45 A Lagrangian Relaxation-based Heuristic to Solve Large Extended Graph Partitioning Problems

-          Oliver Czibula, Hanyu Gu and Yakov Zinder

11.45-12.10 Semimetric Properties of Sørensen-Dice and Tversky Indices-          Alonso Gragera and Vorapong Suppakitpaisarn
12.10-12.35 Finding mode using equality comparisons-          Varunkumar Jayapaul, Venkatesh Raman and Srinivasa Rao Satti
12.35—– Lunch & Tour