COCOON 2001 Program

---

August 19 (Sunday)

9:00am-8:00pm:	Registration
7:00pm-10:00pm:	Reception

August 20 (Monday)

Session A.1: Complexity Theory. Chair: K.-I. Ko

8:20-8:45:	Complete Problems for Valiant's Class of qp-Computable Families of Polynomials
		Markus Blaeser

8:45-9:10:	Log-space Constructible Universal Traversal Sequences for Cycles of 
		Length $O(n^{4.03})$
		Michal Koucky

9:10-9:35:	On Universally Polynomial Context-Free Languages
		Nicholas Tran

Session B.1: Computational Biology. Chair: T. Jiang

8:20-8:45:	Enhanced Sequence Reconstruction with DNA Microarray Application		
		Samuel A. Heath, Franco P. Preparata
		
8:45-9:10:	Non-Approximability of Weighted Multiple Sequence Alignment
		Bodo Siebert
		
9:10-9:35:	A Greedy Algorithm for Optimal Recombination
		Shiquan Wu, Xun Gu

Session A.2: Steiner Trees. Chair: D.T. Lee

10:05-10:30:	The Euclidean Bottleneck Steiner Tree and Steiner Tree with 
		Minimum Number of Steiner Points
		Ding-Zhu Du, Lusheng Wang, Baogang Xu
		
10:30-10:55:	An FPTAS for Weight-Constrained Steiner Trees in Series-Parallel Graphs
		Guangting Chen, Guoliang Xue

Session B.2: Graph Drawing. Chair: Sharon Hu

10:05-10:30:	Irene Finocchi
		Layered Drawings of Graphs with Crossing Constraints

10:30-10:55:	Irene Finocchi, Rossella Petreschi
		On the Validity of Hierarchical Decompositions

Invited Lecture. Chair: Y. Gurevich

11:00-12:00:	The Digital Envelope--A Crash Course in Modern Cryptography
		Avi Wigderson, IAS, Princeton & Hebrew University, Jerusalem
		
		Abstract: The talk is planned for a general audience, and no 
		particular background is assumed.
		    While Cryptography has existed for millenia, the basic theory 
		which underlies all security on the internet and electronic 
		commerce today has been developed within Theoretical Computer 
		Science in a dazzling brief time span starting in the late 70's.
		    In this talk I will try to describe the fundamental assumptions
		of this (complexity-based cryptography) theory, the exciting 
		developement of ideas and notions (like one-way functions
		and zero-knowledge proofs), and how they enable basic tasks
		(like secure communication), as well as arbitrarily complex 
		tasks (like playing a game of Poker over the telephone).

Session A.3: Graph Algorithms & Complexity. Chair: R. Reischuk

1:30-1:55:	A Space Saving Trick for Directed Dynamic Transitive Closure 
		and Shortest Path Algorithms
		Valerie King, Mikkel Thorup

1:55-2:20:	Finding the Most Vital Node of a Shortest Path
		Enrico Nardelli, Guido Proietti, Peter Widmayer

2:20-2:45:	Algorithm for the Cost Edge-Coloring of Trees
		Xiao Zhou, Takao Nishizeki

2:45-3:10:	Counting $H$-Colorings of Partial $k$-Trees 
		Josep Diaz, Maria Serna, Dimitrios M. Thilikos

Session B.3: Online Algorithms. Chair: F. Chin

1:30-1:55:	Improved On-line Stream Merging: from a Restricted to a General Setting
		Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting, Wai-Ha Wong

1:55-2:20:	On-line Deadline Scheduling on Multiple Resources
		Jae-Hoon Kim, Kyung-Yong Chwa

2:20-2:45:	Competitive Online Scheduling with Level of Service
		Ee-Chien Chang, Chee Yap

2:45-3:10:	On-line Variable Sized Covering
		Leah Epstein

Session A.4 Computational Geometry. Chair: D.Z. Chen

3:40-4:05:	On the Planar Two-Watchtower Problem
		Sergei Bespamyatnikh, Zhixiang Chen, Kanliang Wang, Binhai Zhu

4:05-4:30:	Efficient Generation of Triconnected Plane Triangulations
		Shin-ichi Nakano

4:30-4:55:	Packing Two Disks into a Polygonal Environment
		Prosenjit Bose, Pat Morin, Antoine Vigneron

4:55-5:20:	How Good Is Sink Insertion?
		Xiang-Yang Li, Yu Wang

Session B.4: Graph Theory. Chair: K.-Y. Chwa

3:40-4:05:	Cluttered Orderings for the Complete Graph
		Myra Cohen, Charles Colbourn, Dalibor Froncek

4:05-4:30:	On the Domination Numbers of Generalized de Bruijn Digraphs 
		and Generalized Kautz Digraphs
		Yosuke Kikuchi, Yukio Shibata

4:30-4:55:	A Notion of Cross-Perfect Bipartite Graphs
		Milind Dawande

4:55-5:20:	Some Results on Orthogonal Factorizations
		Haodi Feng

August 21 (Tuesday)

Session A.5: Computational Geometry. Chair: B. Chazelle

8:20-8:45:	Generating Well-Shaped d-Dimensional Delaunay Meshes
		Xiang-Yang Li

8:45-9:10:	Towards Compatible Triangulations
		Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser, Ferran Hurtado

9:10-9:35:	An Improved Upper Bound on the Size of Planar Convex-Hulls
		Abdullah N. Arslan, Ömer Egecioglu

Session B.5: Data Structures and Algorithms. Chair: R. Reischuk

8:20-8:45:	PC-Trees vs. PQ-Trees
		Wen-Lian Hsu

8:45-9:10:	Stacks versus Deques
		Holger Petersen

9:10-9:35:	Optimizing a Computational Method for Length Lower Bounds for
		Reflecting Sequences
		H. K. Dai

Session A.6: Graph Algorithms and Complexity. Chair: F. Chin

10:05-10:30:	A New Measure of Edit Distance Between Labeled Trees
		Chin Lung Lu, Zheng-Yao Su, Chuan Yi Tang

10:30-10:55:	A Linear Time Algorithm for Enumerating All the Minimum and 
		Minimal Separators of A Chordal Graph
		L. Sunil Chandran

Session B.6: Systems Algorithms and Modeling. Chair: D.T. Lee

10:05-10:30:	Decidable Approximations on Generalized and Parameterized
		Discrete Timed Automata
		Zhe Dang, Oscar H. Ibarra, Richard A. Kemmerer

10:30-10:55:	Multiplicative Adaptive Algorithms for User Preference Retrieval
		Zhixiang Chen

Invited Lecture. Chair: J. Wang

11:00-12:00	A Few Fundamental Open Questions in Computational Geometry
		Bernard Chazelle, Princeton University, USA

Session A.7: Complexity Theory. Chair: L. Wang

1:30-1:55:	Separating Oblivious and Non-Oblivious BPs
		Kazuo Iwama, Yasuo Okabe, Toshiro Takase

1:55-2:20:	Program Schemes, Queues, the Recursive Spectrum and Zero-One Laws 
		Iain A. Stewart

2:20-2:45:	Algebraic Properties for P-Selectivity
		Lane Hemaspaandra, Harald Hempel, Arfst Nickelsen

2:45-3:10:	Parallelizability of Some P-Complete Geometric Problems in the EREW-PRAM
		Carla Denise Castanho, Wei Chen, Koichi Wada, Akihiro Fujiwara

Session B.7: Randomized and Average-Case Algorithms. Chair: B. Chazelle

1:30-1:55:	On Testing for Zero Polynomials by a Set of Points with Bounded Precision
		Jin-Yi Cai, Eric Bach

1:55-2:20:	A Randomized Algorithm for Gossiping in Radio Networks
		Marek Chrobak, Leszek Gasieniec, Wojciech Rytter

2:20-2:45:	Deterministic Application of Grover's Quantum Search Algorithm
		Kyoichi Okamoto, Osamu Watanabe

2:45-3:10:	Random Instance Generation for MAX 3SAT
		Mitsuo Motoki

Session A.8: Computational Geometry. Chair: J. Wang

3:40-4:05:	Maximum Red/Blue Interval Matching with Applications
		Danny Z. Chen, Xiaobo (Sharon) Hu, Xiaodong Wu

4:05-4:30:	Computing Farthest Neighbors on a Convex Polytope
		Otfried Cheong, Chan-Su Shin, Antoine Vigneron

4:30-4:55:	Polynomial Time Algorithms for Three-Label Point Labeling
		Rob Duncan, Jianbo Qian, Binhai Zhu

4:55-5:20:	Finding An Optimal Bridge Between Two Polygons
		Xuehou Tan

Session B.8: Graph Theory. Chair: K.-Y. Chwa

3:40-4:05:	Lower Bounds on the Minus Domination and $k$-Subdomination Numbers
		Liying Kang, Hong Qiao, Erfang Shan, Ding-Zhu Du

4:05-4:30:	Edge Connectivity vs Vertex Connectivity in Chordal Graphs
		L. Sunil Chandran

4:30-4:55:	Changing the Diameter of Graph Products
		Ting-Yi Sung, Jeng-Jung Wang

4:55-5:20:	Plane Graphs with Acyclic Complex
		Baogang Xu

August 22 (Wednesday): Conference Tour to Yangshuo

August 23 (Thursday)

Session A.9: Games and Combinatorics. Chair: T. Jiang

8:20-8:45:	Competitive Facility Location along a Highway
		Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin, Rene van Oostrum

8:45-9:10:	Membership for Core of LP Games and Other Games
		Qizhi Fang, Shanfeng Zhu, Maocheng Cai, Xiaotie Deng

9:10-9:35:	Strong Solutions to the Identification Problem
		Pino Caballero-Gil, Candelaria Hernandez-Goya

9:35-10:00:	Area Efficient Exponentiation Using Modular Multiplier/Squarer in GF$(2^n)$
		Hyun-Sung Kim, Kee-Young Yoo

Session B.9: Graph Algorithms and Complexity. Chair: D.Z. Chen

8:20-8:45:	Graph Separators: A Parameterized View
		Jochen Alber, Henning Fernau, Rolf Niedermeier

8:45-9:10:	On Assigning Prefix Free Codes to the Vertices of A Graph
		N.S. Narayanaswamy, C.E. Veni Madhavan

9:10-9:35:	A Highly Efficient Algorithm to Determine Bicritical Graphs
		Dingjun Lou, Ning Zhong

9:35-10:00:	Approximation Algorithms for the Watchman Route and Zookeeper's Problems
		Xuehou Tan

Session A.10: Computability. Chair: K.-I. Ko

10:30-10:55:	Prefix-Free Languages and Initial Segments of Computably Enumerable Degrees
		Guohua Wu

10:55-11:20:	Weakly Computable Real Numbers and Total Computable Real Functions
		Robert Rettinger, Xizhong Zheng, Romain Gengler, Burchard von Braunmuhl

11:20-11:45:	Turing Computability of a Nonlinear Schrödinger Propagator
		Klaus Weihrauch, Ning Zhong

Session B.10: Systems Algorithms and Modeling. Chair: L. Wang

10:30-10:55:	Parametric Scheduling for Network Constraints
		K. Subramani

10:55-11:20:	A Logical Framework for Knowledge Sharing in Multi-Agent Systems}
		Kaile Su, Xudong Luo, Huaiqing Wang, Shichao Zhang, Qingfeng Chen

11:20-11:45:	A Lockout Avoidance Algorithm without Using Time-Stamps for 
		the $k$-Exclusion Problem
		Kumiko Obokata, Michiko Omori, Kazuhiro Motegi, Yoshihide Igarashi