ISAAC 2012 Conference Program

PDF version

 

Tuesday, December 18, 2012

18:00-

Reception

GIS NTU Convention Center

Wednesday, December 19, 2012

9:00-9:10

Opening

Der-Tsai Lee

9:10-10:10

 

Invited Talk (I) – Future Directions in Computer Science Research

John E. Hopcroft

10:10-10:30

Coffee Break

10:30-11:50

Session 1A – Graph Algorithms (I)

Session 1B – Online and Streaming Algorithm

11:50-13:50

Lunch Break

13:50-15:10

Session 2A – Combinatorial Optimization (I)

Session 2B – Computational Complexity (I)

15:10-15:30

Coffee Break

15:30-16:30

Session 3A – Computational Geometry (I)

Session 3B – String Algorithms

Thursday, December 20, 2012

9:00-10:00

 

Invited Talk (II) – Combinatorial Geometry and Approximation Algorithms

Timothy M. Chan

10:00-10:30

Coffee Break (Taking Group Photos)

10:30-11:50

Session 4A – Computational Complexity (II)

Session 4B – Graph Algorithms (II)

11:50-13:50

Lunch Break

13:50-15:10

Session 5A – Computational Geometry (II)

Session 5B – Approximation Algorithms

15:10-15:30

Coffee Break

15:30-16:50

Session 6A – Graph Algorithms (III)

Session 6B – Computational Complexity (III)

18:00-

Banquet

Café 83, Leader Hotel

Friday, December 21, 2012

9:00-10:00

Invited Talk (III) – Origami Robots and Star Trek Replicators

Erik D. Demaine

10:00-10:30

Coffee Break

10:30-12:10

Session 7A – Graph Drawing

Session 7B – Data Structures

12:10-13:50

Lunch Break

13:50-14:50

Session 8A – Combinatorial Optimization (II)

Session 8B – Computational Geometry (III)

14:50-15:10

Coffee Break

15:10-16:10

Session 9A – Randomized Algorithms

Session 9B – Algorithmic Game Theory

Ø Invited Talks & Sessions A: Socrates Chamber; Sessions B: Locke Chamber

Ø Each paper presentation is given a 20-minutes slot – 17-min talk, 2-min Q&A, and 1-min switch.

Ø Parallel sessions are expected to be synchronized every 20 minutes. We'll synchronize the clocks first.

 

 

Wednesday, December 19, 2012

8:30-

Registration

9:00-9:10

Opening

Der-Tsai Lee

9:10-10:10

 

Invited Talk (I) – Future Directions in Computer Science Research

John E. Hopcroft

Chair: Der-Tsai Lee

10:10-10:30

Coffee Break

10:30-11:50

Session 1A – Graph Algorithms (I)

Chair: Takao Nishizeki

Strong Conflict-free Coloring for Intervals

Panagiotis Cheilaris, Luisa Gargano, Adele A. Rescigno and Shakhar Smorodinsky

Closing Complexity Gaps for Coloring Problems on H-Free Graphs

Petr Golovach, Daniël Paulusma and Jian Song

Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors

Ching-Chen Kuo and Hsueh-I Lu

Reconfiguration of List L(2,1)-Labelings in a Graph

Takehiro Ito, Kazuto Kawamura, Hirotaka Ono and Xiao Zhou

Session 1B – Online and Streaming Algorithm

Chair: Rolf Klein

An 8/3 Lower Bound for Online Dynamic Bin Packing

Prudence W.H. Wong, Fencol C.C. Yung and Mihai Burcea

Computing k-centers over Streaming Data for Small k

Hee-Kap Ahn, Hyo-Sil Kim, Sang-Sub Kim and Wanbin Son

Competitive Design and Analysis for Machine-Minimizing Job Scheduling Problem

Mong-Jen Kao, Jian-Jia Chen, Ignaz Rutter and Dorothea Wagner

Precision vs Confidence Tradeoffs for l2-Based Frequency Estimation in Data Streams

Sumit Ganguly

(Absent, Auto Slide Presentation)

11:50-13:50

Lunch Break

13:50-15:10

Session 2A – Combinatorial Optimization (I)

Chair: John E. Hopcroft

A Partially Ordered Structure and a Generalization of the Canonical Partition for General Graphs with Perfect Matchings

Nanao Kita

Fast and Simple Fully-Dynamic Cut Tree Construction

Tanja Hartmann and Dorothea Wagner

Green Scheduling, Flows and Matchings

 

Evripidis Bampis, Dimitrios Letsios and Giorgio Lucarelli

Popular and Clan-Popular b-Matchings

Katarzyna Paluch

Session 2B – Computational Complexity (I)

Chair: Osamu Watanabe

Kernelization and Parameterized Complexity of Star Editing and Union Editing

Jiong Guo and Yash Raj Shrestha

On the Advice Complexity of Buffer Management

Reza Dorrigiv, Meng He and Norbert Zeh

On the Complexity of the Maximum Common Subgraph Problem for Partial k-Trees of Bounded Degree

Tatsuya Akutsu and Takeyuki Tamura

Speeding up Shortest Path Algorithms

Andrej Brodnik and Marko Grgurovič

15:10-15:30

Coffee Break

15:30-16:30

Session 3A – Computational Geometry (I)

Chair: Dorothea Wagner

How Many Potatoes are in a Mesh?

Marc van Kreveld, Maarten Löffler and János Pach

On the Farthest Line-Segment Voronoi Diagram

Evanthia Papadopoulou and Sandeep Kumar Dey

On Higher Order Voronoi Diagrams of Line Segments

Evanthia Papadopoulou and Maksym Zavershynskyi

Session 3B – String Algorithms

Chair: Kunsoo Park

Computing the Longest Common Subsequence of Two Run-length Encoded Strings

Yoshifumi Sakai

Efficient Counting of Square Substrings in a Tree

Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń

A General Method for Improving Insertion-Based Adaptive Sorting

Riku Saikkonen and Eljas Soisalon-Soininen

 

Enjoy your stay in Taipei!

 

 

Thursday, December 20, 2012

8:30-

Registration

9:00-10:00

 

Invited Talk (II) – Combinatorial Geometry and Approximation Algorithms

Timothy M. Chan

Chair: Tsan-sheng Hsu

10:00-10:30

Coffee Break (Taking Group Photos)

10:30-11:50

Session 4A – Computational Complexity (II)

Chair: Hsu-Chun Yen

Counting Partitions of Graphs

Pavol Hell, Miki Hermann and Mayssam Mohammadi Nevisi

Constant Unary Constraints and Symmetric Real-Weighted Counting CSPs

Tomoyuki Yamakami

Interval Scheduling and Colorful Independent Sets

René Van Bevern, Matthias Mnich, Rolf Niedermeier and Mathias Weller

More on a Problem of Zarankiewicz

Chinmoy Dutta and Jaikumar Radhakrishnan

(Absent, Video Presentation)

Session 4B – Graph Algorithms (II)

Chair: Yoshio Okamoto

Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs

Andreas Brandstädt, Arne Leitert and Dieter Rautenbach

On the Hyperbolicity of Small-World and Tree-Like Random Graphs

Wei Chen, Weijie Fang, Guangda Hu and Michael W. Mahoney

On the Neighbourhood Helly of some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets

Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary and Lhouari Nourine

Induced Immersions

Rémy Belmonte, Pim van 'T Hof and Marcin Kamiński

11:50-13:50

Lunch Break

13:50-15:10


 

Session 5A – Computational Geometry (II)

Chair: Timothy M. Chan

Rectilinear Covering for Imprecise Input Points

Hee-Kap Ahn, Sang Won Bae and Shin-Ichi Tanigawa

Robust Nonparametric Data Approximation of Point Sets via Data Reduction

Stephane Durocher, Alexandre Leblanc, Jason Morrison and Matthew Skala

Optimal Point Movement for Covering Circular Regions

Danny Z. Chen, Xuehou Tan, Haitao Wang and Gangshan Wu

Solving Circular Integral Block Decomposition in Polynomial Time

Yunlong Liu and Xiaodong Wu

Session 5B – Approximation Algorithms

Chair: Siu-Wing Cheng

The Canadian Traveller Problem Revisited

Yamming Huang and Chung-Shou Liao

Vehicle Scheduling on a Graph Revisited

Wei Yu, Mordecai Golin and Guochuan Zhang

A 4.31-Approximation for the Geometric Unique Coverage Problem on Unit Disks

Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno and Yushi Uno

The Minimum Vulnerability Problem

Sepehr Assadi, Ehsan Emamjomeh-Zadeh, Ashkan Norouzi-Fard, Sadra Yazdanbod and Hamid

15:10-15:30

Coffee Break

15:30-16:50

Session 6A – Graph Algorithms (III)

Chair: Takeshi Tokuyama

A Strongly Polynomial Time Algorithm for the Shortest Path Problem on Coherent Planar Periodic Graphs

Norie Fu

Cubic Augmentation of Planar Graphs

Tanja Hartmann, Jonathan Rollin and Ignaz Rutter

On the Number of Upward Planar Orientations of Maximal Planar Graphs

Fabrizio Frati, Joachim Gudmundsson and Emo Welzl

Universal Point Subsets for Planar Graphs

Patrizio Angelini, Carla Binucci, William Evans, Ferran Hurtado, Giuseppe Liotta, Tamara Mchedlidze, Henk Meijer and Yoshio Okamoto

Session 6B – Computational Complexity (III)

Chair: Hee-Kap Ahn

Abstract Flows over Time: A First Step towards Solving Dynamic Packing Problems

Jan-Philipp W. Kappmeier, Jannik Matuschke and Britta Peis

Extending Partial Representations of Subclasses of Chordal Graphs

Pavel Klavík, Jan Kratochvíl, Yota Otachi and Toshiki Saitoh

Isomorphism for Graphs of Bounded Connected-Path-Distance-Width

Yota Otachi

Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph

Danny Hermelin, Romeo Rizzi and Stéphane Vialette

18:00-21:00

Banquet

Café 83, Leader Hotel

² ISAAC 2013

² Best Student Paper Award

² Chinese Musical Instruments Performance -- ChengBei Chinese Orchestra

² Karaoke – All You Can Sing

 

The night has just begun!

 

 

Friday, December 21, 2012

9:00-10:00

Invited Talk (III) – Origami Robots and Star Trek Replicators

Erik D. Demaine

Chair: Kun-Mao Chao

10:00-10:30

Coffee Break

10:30-12:10

Session 7A – Graph Drawing

Chair: Seokhee Hong

Linear Layouts in Submodular Systems

Hiroshi Nagamochi

Segmental Mapping and Distance for Rooted Labeled Ordered Trees

Tomohiro Kan, Shoichi Higuchi and Kouichi Hirata

Detecting Induced Minors in AT-free Graphs

Petr Golovach, Dieter Kratsch and Daniël Paulusma

Degree-constrained Orientations of Embedded Graphs

Yann Disser and Jannik Matuschke

Interval Graph Representation with Given Interval and Intersection Lengths

Johannes Köbler, Sebastian Kuhnert and Osamu Watanabe

Session 7B – Data Structures

Chair: Kunihiko Sadakane

Finger Search in the Implicit Model

Gerth Stølting Brodal, Jesper Sindahl Nielsen and Jakob Truelsen

A Framework for Succinct Labeled Ordinal Trees over Large Alphabets

Meng He, J. Ian Munro and Gelin Zhou

A Space-Efficient Framework for Dynamic Point Location

Meng He, Patrick K. Nicholson and Norbert Zeh

Selection in the Presence of Memory Faults, with Applications to In-place Resilient Sorting

Nimrod Talmon and Tsvi Kopelowitz

An Improved Algorithm for Static 3D Dominance Reporting in the Pointer Machine

Christos Makris and Konstantinos Tsakalidis

12:10-13:50

Lunch Break

13:50-14:50

Session 8A – Combinatorial Optimization (II)

Chair: Erik D. Demaine

The Multi-Service Center Problem

Hung-I Yu and Cheng-Chung Li

Computing Minmax Regret 1-Median on a Tree Network with Positive/Negative Vertex Weights

Binay Bhattacharya, Tsunehiko Kameda and Zhao Song

Fence Patrolling by Mobile Agents with Distinct Speeds

Akitoshi Kawamura and Yusuke Kobayashi

Session 8B – Computational Geometry (III)

Chair: Evanthia Papadopoulou

Weak Visibility Queries of Line Segments in Simple Polygons

Danny Z. Chen and Haitao Wang

Beyond Homothetic Polygons: Recognition and Maximum Clique

Konstanty Junosza-Szaniawski, Jan Kratochvíl, Martin Pergel and Paweł Rzążewski

Area Bounds of Rectilinear Polygons Realized by Angle Sequences

Sang Won Bae, Yoshio Okamoto and Chan-Su Shin

14:50-15:10

Coffee Break

15:10-16:10

Session 9A – Randomized Algorithms

Chair: Yue-Li Wang 

A Time-Efficient Output-Sensitive Quantum Algorithm for Boolean Matrix Multiplication

François Le Gall

On Almost Disjunct Matrices for Group Testing

Arya Mazumdar

Parameterized Clique on Scale-Free Networks

Tobias Friedrich and Anton Krohmer

Session 9B – Algorithmic Game Theory

Chair: Hung-Lung Wang

Multi-Unit Auctions with Budgets and Non-uniform Valuations

H.F. Ting and Xiangzhong Xiang

Efficient Computation of Power Indices for Weighted Majority Games

Takeaki Uno

Revenue Maximization in a Bayesian Double Auction Market

Xiaotie Deng, Paul Goldberg, Bo Tang and Jinshan Zhang

 

See you in Hong Kong next December!