Category Archives: Schedule

Program

WALCOM 2016 PROGRAM

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

 

Accepted Papers

3) Matthias Mnich: “Large Independent Sets in Subquartic Planar Graphs”

8) Morito Oomine, Aleksander Shurbevski and Hiroshi Nagamochi:“Parameterization of Strategy-Proof Mechanisms in the Obnoxious Facility Game”

12)Shun Hasegawa and Toshiya Itoh: “Optimal Online Algorithms for the Multi-Objective Time Series Search Problem”

13) Hwan-Gue Cho, William Evans, Noushin Saeedi and Chan-Su Shin: “Covering Points with Convex Sets of Minimum Size”

16) Tiziana Calamoneri, Angelo Monti and Rossella Petreschi: “ Dynamically mantaining minimal integral separator for Threshold and Difference Graphs”

19) Stefan Felsner and Daniel Heldt:“Mixing Times of Markov Chains of 2-Orientations”

23) Farah Chanchary and Anil Maheshwari: “Counting Subgraphs in Relational Event Graphs”

25) Mike Behrisch, Miki Hermann, Stefan Mengel and Gernot Salzer: “As Close As It Gets”

27) Sang Won Bae: “Computing a Minimum-Width Square Annulus in Arbitrary Orientation”

29)  Biswajit Sanyal, Subhashis Majumder and Wing-kai Hon: “Efficient Generation of Top-k Procurements in a Multi-Item Auction”

35) Varunkumar Jayapaul, Venkatesh Raman and Srinivasa Rao Satti: “Finding mode using equality comparisons”

38) Takeshi Yamada and Ryuhei Uehara:“Shortest Reconfiguration of Sliding Tokens on a Caterpillar”

42) Barun Gorain, Partha Sarathi Mandal and Krishnendu Mukhopadhyaya:” Approximation Algorithms
for Generalized Bounded Tree Cover”

43) Franz Brandenburg, Alexander Esch and Daniel Neuwirth:” On Aligned Bar 1-Visibility Graphs”

44) Oliver Czibula, Hanyu Gu and Yakov Zinder: “A Lagrangian Relaxation-based Heuristic to Solve
Large Extended Graph Partitioning Problems”

45) Toshihiro Fujito and Daichi Suzuki: “ Fast and Simple Local Algorithms for 2-Edge Dominating
Sets and 3-Total Vertex Covers”

46) Patrizio Angelini, Michael Bekos, Michael Kaufmann and Vincenzo Roselli: “Vertex-Coloring
with Star-Defects”

47)Jean-Alexandre Angles d’Auriac, Csilia Bujtas, Hakim El Maftouhi, Marek Karpinski, Yannis Manoussakis, Leandro Montero, Narayanan Narayanan, Laurent Rosaz, Johan Tapper and Zsolt Tuza:“Tropical Dominating Sets in Vertex-Coloured Graphs”

48) Pavel Emelyanov: “LP Upper Bound for the Length of Snake-in-the-Box”

49) Dipan Lal Shaw, M. Sohel Rahman, A. S. M. Sohidull Islam and Shuvasish Karmaker: “Approximation Algorithms for Three Dimensional Protein Folding”

53) Md. Iqbal Hossain, Sammi Abida Salma and Md. Saidur Rahman:“A Necessary Condition
and a Sufficient Condition for Pairwise Compatibility Graphs”

54) K.Subramani and Piotr Wojciechowski: “An optimal algorithm for computing the integer
closure of UTVPI constraints”

56) Devsi Bantva: “On hamiltonian colorings of block graphs”

63) Alejandro Lopez-Ortiz and Daniela Maftuleac:“Lower Bounds for Graph Exploration Using Local Policies”

64) Alejandro Lopez-Ortiz and Daniela Maftuleac:“Optimal Distributed Searching in the Plane with
and without Uncertainty”

67) Krishnendu Mukhopadhyaya, Subhash Bhagat and Sruti Gan Chaudhuri: “Formation of General
Position by Asynchronous Mobile Robots Under One-axis Agreement”

68) Prosenjit Bose and Jean-Lou De Carufel: “A General Framework for Searching on a Line”

70) Alonso Gragera and Vorapong Suppakitpaisarn:“Semimetric Properties of Sørensen-Dice
and Tversky Indices”

Venue

The workshop will be held at the Asian Institute of Technology and Management, Khumaltar Height, Lalitpur, Nepal

Important Dates

Paper Submission: October 17, 2015 (Extended Deadline)
Notification of Acceptance: November 28, 2015
Camera-ready Version: December 12, 2015
Conference: March 29-31, 2016