Conference program


The conference will run for three days (August 20-22). Each day will start with a 1-hour invited talk followed by four sessions of 20-minute contributed talks. Coffee and lunch will be served outside the conference venue. For a detail schedule, scroll down in this page.

In addition to the scientific program, we will have two social events:

  • Reception: The day before the conference (Aug 19) at 19:00.
  • Conference dinner: On the second day of the conference (Aug 21) at 19:00.

Registration opens on August 20 at 8:00 at the conference venue.

Scientific program


First Day (20 August 2011)

Invited talk 8:30 Geometric Network Optimization
Joseph Mitchell
Session 1 9:30 A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree with Positive Vertex Weights
Binay Bhattacharya and Tsunehiko Kameda
9:50 A simple D^2-sampling based PTAS for k-means
Ragesh Jaiswal, Amit Kumar and Sandeep Sen
Break 10:10 Coffee Break
Session 2 10:30 Speed Scaling for Maximum Lateness
Evripidis Bampis, Dimitrios Letsios, Ioannis Milis and Georgios Zois
10:50 Induced subgraph isomorphism: Are some patterns substantially easier than others?
Peter Floderus, Miroslaw Kowaluk, Andrzej Lingas and Eva-Marta Lundell
11:10 Contiguous min single-source-multi-sink cuts in weighted planar graphs
Ivona Bezakova and Zach Langley
11:30 Online Knapsack Problem with Removal Cost
Xin Han, Yasushi Kawase and Kazuhisa Makino
11:50 An Improved Exact Algorithm for TSP in Degree-4 Graphs
Mingyu Xiao and Hiroshi Nagamochi
Lunch 12:10 Lunch Period
Session 3 13:30 Dynamic Programming for $H$-minor-free Graphs
Juanjo Rué, Ignasi Sau and Dimitrios Thilikos
13:50 Restricted Max-Min Fair Allocations with Inclusion-free Intervals
Monaldo Mastrolilli and Georgios Stamoulis
14:10 An Improved Algorithm for Packing $T$-Paths in Inner Eulerian Networks
Maxim Babenko, Kamil Salikhov and Stepan Artamonov.
14:30 Towards Optimal and Expressive Kernelization for d-Hitting Set
René Van Bevern
14:50 Maximum number of minimal feedback vertex sets in chordal graphs and cographs
Jean-François Couturier, Pinar Heggernes, Pim Van 'T Hof and Yngve Villanger
Break 15:10 Coffee Break
Session 4 15:30 A local algorithm for finding dense bipartite-like subgraphs
Pan Peng
15:50 Algorithms for the Strong Chromatic Index of Halin Graphs, Distance-hereditary Graphs and Maximal Outerplanner Graphs
Ton Kloks, Sheung-Hung Poon, Chin-Ting Ung and Yue-Li Wang
16:10 On the Minimum Degree Hypergraph Problem with Subset Size two and the Red-Blue Hitting Set Problem with the Consecutive Ones Property
Biing-Feng Wang and Chih-Hsuan Li
16:30 Rainbow Colouring of Split and Threshold Graphs
L. Sunil Chandran and Deepak Rajendraprasad
16:50 Approximating the rainbow - better lower and upper bounds
Alexandru Popa

Second Day (21 August 2011)

Invited talk 8:30 Extremal problems for geometric graphs---new methods
Janos Pach
Session 5 9:30 Ramsey numbers for line graphs and perfect graphs
Remy Belmonte, Pinar Heggernes, Pim Van T Hof and Reza Saei.
9:50 Geodesic Order Types
Oswin Aichholzer, Matias Korman, Alexander Pilz and Birgit Vogtenhuber
Break 10:10 Coffee Break
Session 6 10:30 Computing Partitions of Rectilinear Polygons with Minimum Stabbing Number
Stephane Durocher and Saeed Mehrabi
10:50 Monotone paths in planar convex subdivisions
Adrian Dumitrescu, Günter Rote and Csaba Toth
11:10 Complementary vertices and adjacency testing in polytopes
Benjamin A. Burton
11:30 Optimally solving a transportation problem using Voronoi diagrams
Darius Geiß, Rolf Klein and Rainer Penninger.
11:50 Unexplored Steiner Ratios in Geometric Networks
Lilach Chaitman-Yerushalmi and Paz Carmi
Lunch 12:10 Lunch Period
Session 7 13:30 Geometric RAC Simultaneous Drawings of Graphs
Evmorfia Argyriou, Michael Bekos, Michael Kaufmann and Antonios Symvonis.
13:50 Simultaneous Embeddings with Vertices Mapping to Pre-Specified Points
Taylor Gordon
14:10 Multilevel Drawings of Clustered Graphs
Fabrizio Frati
14:30 Outerplanar graph drawings with few slopes
Kolja Knauer, Piotr Micek and Bartosz Walczak
14:50 Fary's Theorem for 1-Planar Graphs
Seok-Hee Hong, Peter Eades, Giuseppe Liotta and S Poon
Break 15:10 Coffee Break
Session 8 15:30 Constant Time Enumeration of Bounded-Size Subtrees in Trees and Its Application
Kunihiro Wasa, Takeaki Uno and Hiroki Arimura
15:50 External Memory Soft Heap, and Hard Heap, a Meldable Priority Queue
Alka Bhushan and Sajith Gopalan
16:10 Partially Specified Nearest Neighbor Search
Marcel Schoengens and Tomas Hruz
16:30 Multi-Pattern Matching with Bidirectional Indexes
Simon Gog, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen and Niko Välimäki.
16:50 Succinct Representations of Binary Trees for Range Minimum Queries
Pooya Davoodi, Rajeev Raman and Srinivasa Rao Satti

Third Day (22 August 2011)

Invited talk 8:30 Online matching
Kamal Jain
Session 9 9:30 Lower Bounds against Weakly Uniform Circuits
Ruiwen Chen and Valentine Kabanets
9:50 On TC0 Lower Bounds for the Permanent
Jeff Kinne
Break 10:10 Coffee Break
Session 10 10:30 Formula Complexity of Ternary Majorities
Kenya Ueno
10:50 On the kernelization complexity of problems on graphs without long odd cycles
Fahad Panolan and Ashutosh Rai
11:10 The Complexity of Unary Subset Sum
Nutan Limaye, Meena Mahajan and Karteek Sreenivasaiah
11:30 On the Advice Complexity of Tournaments
Sebastian Ben Daniel
11:50 A remark on one-wayness versus pseudorandomness
Periklis Papakonstantinou and Guang Yang
Lunch 12:10 Lunch Period
Session 11 13:30 Integral Mixed Unit Interval Graphs
Van Bang Le and Dieter Rautenbach
13:50 The cost of bounded curvature
Hyo-Sil Kim and Otfried Cheong
14:10 Online Coloring of Bipartite Graphs With and Without Advice
Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovic and Lucia Keller
14:30 Deep Coalescence Reconciliation with Unrooted Gene Trees: Linear Time Algorithms
Pawel Gorecki and Oliver Eulenstein
14:50 On the $2$-Central Path Problem
Yongding Zhu and Jinhui Xu
Break 15:10 Coffee Break
Session 12 15:30 Making Profit in a Prediction Market
Jen-Hou Chou, Chi-Jen Lu and Mu-En Wu
15:50 Computing Shapley Value in Supermodular Coalitional Games
David Liben-Nowell, Alexa Sharp, Tom Wexler and Kevin Woods
16:10 Equilibria of GSP for range auction
H.F. Ting and Xiangzhong Xiang
16:30 Stretch in Bottleneck Games
Costas Busch and Rajgopal Kannan