Hangzhou Bay Bridge, 36 KM
The 2nd Annual Meeting of
Asian Association for Algorithms and Computation
-- AAAC 2009 --


April 11-12, 2009
Hangzhou, China
Campus of Zhejiang University

 

Navigations

AAAC 2009

Important Dates

Keynote Speakers

Program Committee

Call for Papers

Paper Submission

Accepted Papers

Programme

Registration

Venue

Accommodation

Visa Requirment

Organize Committee


Previous Event

AAAC 2008

 

Tentative Program of AAAC 2009

Registration,2009

Time: Friday, April 10: 14:00 ~ 17:00
Place: The lobby of the Hotel

Saturday, April 11,2009

8:30-8:40

Opening

8:40-9:40

Session 1: Invited Talk I

9:40-10:10

Tea Break

10:10-12:10

Session 2  

12:10-13:50

Lunch

13:50-15:50

Session 3-A

Complexity

Session 3-B

Graph-1

Session 3-C

Combinatorial Algorithms

15:50-16:20

Tea Break

16:20-18:00

Session 4-A

Computational Geometry

Session 4-B

Graph-2

Session 4-C

Bioinformatics and Data Structure

19:20-21:30

Banquet

Sunday, April 12, 2009

8:40-9:40

Session 5: Invited Talk II

9:40-10:10

Tea Break

10:10-12:10

Session 6

12:10-13:50

Lunch

13:50-15:30

Session 7-A

Online Algorithms

Session 7-B

Networks

15:30

Closing

Saturday, April 11, 2009

Session 1

8:40-9:40

Xiaotie Deng. On Complexity of Envy-Free Cake-Cutting

Session 2

10:10-10:40

Yuichi Yoshida, Masaki Yamamoto and Hiro Ito. Constant-Time Approximations Using Minimum Value Search for Independent Sets and Matchings

10:40-11:10

Siu-Wing Cheng and Man Kwun Chiu. Dimension Detection via Slivers

11:10-11:40

Pinyan Lu. The Complexity of Counting Problems and Holographic Algorithms

11:40-12:10

Ning Chen, Nicole Immorlica, Anna Karlin, Mohammad Mahdian and Atri Rudra. Approximating Matches Made in Heaven

Session 3-A: Complexity

13:50-14:10

 

Francis Chin, Zeyu Guo and He Sun. Minimum Manhattan Network is NP-Complete

14:10-14:30

 

Yuichi Asahiro, Eiji Miyano and Kazuaki Samizo. Complexity of Max d-Diameter Subgraph Problems on Chordal Graphs

14:30-14:50

 

Hideaki Fukuhara and Eiji Takimoto. Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators

14:50-15:10

 

Taisuke Izumi, Tomoko Suzuki, Sayaka Kamei and Fukuhito Ooshita. Probabilistic Gathering of Mobile Robots with Weak Multiplicity-Detection Capabilities

15:10-15:30

 

Tomoyuki Hayasaka. Yet Another Reduction from Graph to Ring Isomorphism Problems

15:30-15:50

 

Mikael Onsjö, Robert Berke and Osamu Watanabe. Belief Propagation and Heavy Connectivity in Random Graphs

Session 3-B: Graph-1

13:50-14:10

 

Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono and Yushi Uno. A Faster Algorithm for $L(2,1)$-labeling of Trees

14:10-14:30

 

Rudolf Fleischer and Xi Wu. Experimental Study of FPT Algorithms for the Directed Feedback Vertex Set Problem

14:30-14:50

 

Rudolf Fleischer and Youdong Miao. A New FPT Algorithm for the Edge Dominating Set Problem

14:50-15:10

 

Matias Korman and Takeshi Tokuyama. An Improved Algorithm for Inserting a Highway in a City Metric Based on Minimization of Quasiconvex Functions

15:10-15:30

 

Ei Ando, Hirotaka Ono, Kunihiko Sadakane and Masafumi Yamashita. An Exact Algorithm for the Stochastic Longest Path Problem in a DAG

15:30-15:50

 

 Jiexun Wang, Hiroshi Nagamochi, Liang Zhao and Tatsuya Akutsu. Enumerating Colored and Rooted Cacti with Bounds on Vertex/Edge Colors

Session 3-C: Combinatorial Algorithms

13:50-14:10

 

Caoan Wang. A Bound for Sum of Square Roots of Special Integers

14:10-14:30

 

Xiangtong Qi. A Subcontractor's Pricing Game in Production Scheduling

14:30-14:50

 

Mao-Cheng Cai and Xiaoguang Yang. Restricted Partial Inverse Minimum Base Problem of a Matroid

14:50-15:10

 

Donglei Du, Ruixing Lu and Dachuan Xu. A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties

15:10-15:30

 

Kerui Min, He Sun and Hong Zhu. Finding Real Icebergs in Internet Traffic

15:30-15:50

 

Anthony Man-Cho So. Probabilistic Analysis of the Semidefinite Relaxation Detector in Digital Communications

Session 4-A: Computational Geometry

16:20-16:40

Rudolf Fleischer and Yihui Wang. On the Camera Placement Problem

16:40-17:00

Hee-Kap Ahn and Yoshio Okamoto. An Adaptive Algorithm for the Planar Convex Hull

17:00-17:20

Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron and Yajun Wang. Approximate Homotopic Shortest Paths in Anisotropic Regions with Symmetric Cost

17:20-17:40

Keigo Kinpara, Tomoko Izumi, Taisuke Izumi and Koichi Wada. Space-Efficient Self-Stabilizing Counting Protocol on Mobile Sensor Networks with a Base Station

17:40-18:00

Takashi Horiyama and Masato Samejima. Enumeration of Polyominoes for p4 Isohedral Tiling by the Reverse Search

Session 4-B: Graphs-2

16:20-16:40

Kazuo Iwama, Kazuhisa Seto and Suguru Tamaki. The Planar Hajos Calculus for Bounded Degree Graphs

16:40-17:00

Yusuke Hosaka, Hirotaka Ono, Kunihiko Sadakane and Masafumi Yamashita. Faster Random Walks on Biconnected Series-Parallel Graphs

17:00-17:20

He Sun and Hong Zhu. On Construction of Almost-Ramanujan Graphs

17:20-17:40

Yunfeng Xu and He Sun. Approximating the Spectral Gap of Expanders in the Data Stream Model

17:40-18:00

Mingyu Xiao. New Branching Rules: Improvements on Independent Set and Vertex Cover in Sparse Graphs

Session 4-C: Bioinformatics and Data Structure

16:20-16:40

Zhewei Wei, Ke Yi and Qin Zhang. Dynamic External Hashing: The Limit of Buffering

16:40-17:00

Kunsoo Park, Joo Young Yoon, Sunho Lee, Eunok Paek, Heejin Park, Sang-Won Lee and Hee-Jung Jung. RAPID: Fast and Accurate Determination of Monoisotopic Masses of Polypeptides

17:00-17:20

Naoki Katoh and Shin-ichi Tanigawa. Combinatorial Rigidity of Molecular Structures and the Molecular Conjecture

17:20-17:40

Yaw-Ling Lin. Algorithms for Haplotype Block Partitioning and Tag SNP Selection Problems Under Various Constraints

17:40-18:00

Louxin Zhang. Estimating the Accuracy of the Parsimony and ML Methods for Reconstruction of Ancestral States

Sunday, April 12, 2009

Session 5

8:40-9:40

Gerhard Woeginger. Analysis of Three Assignment Problems

Session 6

10:10-10:40

Mordecai Golin, Xiaoming Xu and Jiajin Yu. Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding

10:40-11:10

Yoshiaki Nonaka, Hirotaka Ono, Kunihiko Sadakane and Masafumi Yamashita. A Tight Upper Bound on the Cover Time of Metropolis Walks

11:10-11:40

Andreas Dress. Topological Approaches to Tree Reconstruction

11:40-12:10

Bo Chen, Xujin Chen and Xiaodong Hu. Good Nash Equilibria in Selfish Ring Routing

Session 7-A: Online Algorithms

13:50-14:10

Shuichi Miyazaki, Naoyuki Morimoto and Yasuo Okabe. An Optimal Online Algorithm for the Graph Exploration Problem on Unweighted Graphs

14:10-14:30

Rudolf Fleischer and Tao Zhang. Two Online Maximization Problems with Look-Ahead

14:30-14:50

Xin Han and Kazuhisa Makino. Online Knapsack Problems: A Survey

14:50-15:10

Francis Chin, Hing-Fung Ting and Yong Zhang. 1-Space Bounded Algorithms for 2-Dimensional Bin Packing

15:10-15:30

Deshi Ye, Guochuan Zhang and Xin Han. On-Line Multiple Strips Packing

Session 7-B: Networks (Complex, Sensor, Social)

13:50-14:10

Xiaodong Hu. Steiner Tree Problems in Computer Communication Networks

14:10-14:30

Qiang Jiang and Andreas Dress. Detecting Community Structures in Complex networks: a spectral clustering-based framework

14:30-14:50

Samia Souissi, Taisuke Izumi and Koichi Wada. Crash-Tolerant Flocking of Mobile Robots with Eventually Perfect Failure Detectors

14:50-15:10

Yizhi Ren, Mingchu Li and Kouichi Sakurai. Toward the Evolving Trust Overlay: An Evolutionary Game View

15:10-15:30

Chunhua Su and Kouichi Sakurai. A Secure and Efficient Solution for Distributed Association Rules Mining

 
  Since Aug. 28, 2008.