WAAC06 :: The 9th Japan-Korea Joint Workshop on Algorithms and Computation Program Tuesday, July 4 9:00 - 9:50 Invited talk • On-Line Character Animation Sung Yong Shin 10:05 - 11:45 Session 1 • Queue Layout of Bipartite Graph Subdivisions Miki Miyauchi • Loose Covering by Graphs Satoshi Fujita • Every Starlike Tree Spans Restricted HL-Graphs Jung-Heum Park, Hyeong-Seok Lim and Hee-Chul Kim • Approximating Minimum Cost Multigraphs of Specified Edge-Connectivity under Degree Bounds Takuro Fukunaga and Hiroshi Nagamochi 13:15 - 14:30 Session 2 • Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs Xin Han, Kazuo Iwama, Rolf Klein and Andrzej Lingas • An Argument on Approximate Defective Coloring for k-colorable Graphs Xuzhen Xie, Takao Ono and Tomio Hirata • Sufficient Condition and Algorithm for List Total Coloring of Series-Parallel Graphs Yuki Matsuo, Xiao Zhou and Takao Nishizeki 14:45 - 16:00 Session 3 • Constant Time Generation of Integer Partitions Katsuhisa Yamanaka, Shin-ichiro Kawano, Yosuke Kikuch and Shin-ichi Nakano • Enumerating Split Graphs Masashi Kiyomi and Takeaki Uno • Enumerating Non-crossing Minimally Rigid Frameworks David Avis, Naoki Katoh, Makoto Ohsaki, Shin-ichi Tanigawa and Ileana Streinu 16:15 - 17:55 Session 4 • Matching Algorithm for Extended Regular Expressions with Boolean Operations Hiroaki Yamamoto, Yoshifumi Okada and Masayuki Okamoto • Comparisons of Practical Performance for Constructing Compressed Suffix Arrays Chi Seong Park, Minhwan Kim, Heejin Park and Dong Kyue Kim • Approximation Algorithms for Optimal RNA Secondary Structures Common to Multiple Sequences Takeyuki Tamura and Tatsuya Akutsu • Computational Analysis and Modeling of NFkB Activation during Hepatitis B Virus Infection Taehyung Lee, Sung Gyoo Park, Kunsoo Park, Kwang-Hyun Cho and Guhung Jung 18:30– Banquet Wednesday, July 5 9:00 - 10:40 Session 5 • Optimal Construction of the City Voronoi Diagram Sang Won Bae, Jae-Hoon Kim and Kyung-Yong Ghwa • An Efficient Algorithm for Evacuation Problems in a Certain Class of Layered Networks Naoyuki Kamiyama, Naoki Katoh and Atsushi Takizawa • A Novel Cluster-based Architecture and Fast Broadcast for Dynamic Sensor Networks Wei Chen, M.A.K.M.Islam, Mohan Malkani, Amir Shirkhodaie, Koichi Wada and Mohamed Zein-Sabatto • Power Analysis Countermeasure based on Ramp Schemes Tetsuya Izu and Tsuyoshi Takagi 10:55 - 12:35 Session 6 • Provably-Secure Password-Based Group Key Exchange in the Standard Model Using a Constant Number of Rounds Jeong Ok Kwon, Ik Rae Jeong, Kouichi Sakurai and Dong Hoon Lee • Secure Registry Scheme with Randomness Reuse E-Yong Kim and Kunsoo Park • Attack against a Cellular Automata Based Message Authentication Scheme Mun-Kyu Lee and Dowon Hong • Efficient Blind and Partially Blind Signatures Without Random Oracles Tatsuaki Okamoto