7. COCOON 2001: Guilin, China

Complexity Theory

• Markus Bläser:
  Complete Problems for Valiant's Class of qp-Computable Families of Polynomials. 1-10
  
• Michal Koucký:
  Log-Space Constructible Universal Traversal Sequences for Cycles of Length O(n^4.03). 11-20
  
• Nicholas Tran:
  On Universally Polynomial Context-Free Languages. 21-27
  
• Kazuo Iwama, Yasuo Okabe, Toshiro Takase:
  Separating Oblivious and Non-oblivious BPs. 28-38
  
• Iain A. Stewart:
  Program Schemes, Queues, the Recursive Spectrum and Zero-One Laws. 39-48
  
• Lane A. Hemaspaandra, Harald Hempel, Arfst Nickelsen:
  Algebraic Properties for P-Selectivity. 49-58
  
• Carla Denise Castanho, Wei Chen, Koichi Wada, Akihiro Fujiwara:
  Parallelizability of Some P-Complete Geometric Problems in the EREW-PRAM. 59-63
  

Computational Biology

• Samuel A. Heath, Franco P. Preparata:
  Enhanced Sequence Reconstruction with DNA Microarray Application. 64-74
  
• Bodo Siebert:
  Non-approximability of Weighted Multiple Sequence Alignment. 75-85
  
• Shiquan Wu, Xun Gu:
  A Greedy Algorithm for Optimal Recombination. 86-90
  

Computational Geometry

• Xiang-Yang Li:
  Generating Well-Shaped d-dimensional Delaunay Meshes. 91-100
  
• Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser, Ferran Hurtado:
  Towards Compatible Triangulations. 101-110
  
• Abdullah N. Arslan, Ömer Egecioglu:
  An Improved Upper Bound on the Size of Planar Convex-Hulls. 111-120
  
• Sergei Bespamyatnikh, Zhixiang Chen, Kanliang Wang, Binhai Zhu:
  On the Planar Two-Watchtower Problem. 121-130
  
• Shin-Ichi Nakano:
  Efficient Generation of Triconnected Plane Triangulations. 131-141
  
• Prosenjit Bose, Pat Morin, Antoine Vigneron:
  Packing Two Disks into a Polygonal Environment. 142-149
  
• Danny Z. Chen, Xiaobo Hu, Xiaodong Wu:
  Maximum Red/Blue Interval Matching with Applications. 150-158
  
• Otfried Cheong, Chan-Su Shin, Antoine Vigneron:
  Computing Farthest Neighbors on a Convex Polytope. 159-169
  
• Xuehou Tan:
  Finding an Optimal Bridge between Two Polygons. 170-180
  
• Xiang-Yang Li, Yu Wang:
  How Good Is Sink Insertion? 181-190
  
• Rob Duncan, Jianbo Qian, Binhai Zhu:
  Polynomial Time Algorithms for Three-Label Point Labeling. 191-200
  
• Xuehou Tan:
  Approximation Algorithms for the Watchman Route and Zookeeper's Problems. 201-206
  

Data Structures and Algorithms

• Wen-Lian Hsu:
  PC-Trees vs. PQ-Trees. 207-217
  
• Holger Petersen:
  Stacks versus Deques. 218-227
  
• H. K. Dai:
  Optimizing a Computational Method for Length Lower Bounds for Reflecting Sequences. 228-236
  

Games and Combinatorics

• Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai J. Golin, René van Oostrum:
  Competitive Facility Location along a Highway. 237-246
  
• Qizhi Fang, Shanfeng Zhu, Mao-cheng Cai, Xiaotie Deng:
  Membership for Core of LP Games and Other Games. 247-256
  
• Pino Caballero-Gil, Candelaria Hernández-Goya:
  Strong Solutions to the Identification Problem. 257-261
  
• Hyun-Sung Kim, Kee-Young Yoo:
  Area Efficient Exponentiation Using Modular Multiplier/Squarer in GF(2^m. 262-267
  

Graph Algorithms and Complexity

• Valerie King, Mikkel Thorup:
  A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms. 268-277
  
• Enrico Nardelli, Guido Proietti, Peter Widmayer:
  Finding the Most Vital Node of a Shortest Path. 278-287
  
• Xiao Zhou, Takao Nishizeki:
  Algorithm for the Cost Edge-Coloring of Trees. 288-297
  
• Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos:
  Counting H-Colorings of Partial k-Trees. 298-307
  
• L. Sunil Chandran:
  A Linear Time Algorithm for Enumerating All the Minimum and Minimal Separators of a Chordal Graph. 308-317
  
• Jochen Alber, Henning Fernau, Rolf Niedermeier:
  Graph Separators: A Parameterized View. 318-327
  
• N. S. Narayanaswamy, C. E. Veni Madhavan:
  On Assigning Prefix Free Codes to the Vertices of a Graph. 328-337
  
• Chin Lung Lu, Zheng-Yao Su, Chuan Yi Tang:
  A New Measure of Edit Distance between Labeled Trees. 338-348
  
• Dingjun Lou, Ning Zhong:
  A Highly Efficient Algorithm to Determine Bicritical Graphs. 349-356
  

Graph Drawing

• Irene Finocchi:
  Layered Drawings of Graphs with Crossing Constraints. 357-367
  
• Irene Finocchi, Rossella Petreschi:
  On the Validity of Hierarchical Decompositions. 368-374
  

Graph Theory

• Liying Kang, Hong Qiao, Erfang Shan, Ding-Zhu Du:
  Lower Bounds on the Minus Domination and k-Subdomination Numbers. 375-383
  
• L. Sunil Chandran:
  Edge Connectivity vs Vertex Connectivity in Chordal Graphs. 384-389
  
• Ting-Yi Sung, Jeng-Jung Wang:
  Changing the Diameter of Graph Products. 390-394
  
• Baogang Xu:
  Plane Graphs with Acyclic Complex. 395-399
  
• Yosuke Kikuchi, Yukio Shibata:
  On the Domination Numbers of Generalized de Bruijn Digraphs and Generalized Kautz Digraphs. 400-408
  
• Milind Dawande:
  A Notion of Cross-Perfect Bipartite Graphs. 409-413
  
• Haodi Feng:
  Some Results on Orthogonal Factorizations. 414-419
  
• Myra B. Cohen, Charles J. Colbourn, Dalibor Froncek:
  Cluttered Orderings for the Complete Graph. 420-431
  

Online Algorithms

• Wun-Tat Chan, Tak Wah Lam, Hing-Fung Ting, Prudence W. H. Wong:
  Improved On-Line Stream Merging: From a Restricted to a General Setting. 432-442
  
• Jae-Hoon Kim, Kyung-Yong Chwa:
  On-Line Deadline Scheduling on Multiple Resources. 443-452
  
• Ee-Chien Chang, Chee-Keng Yap:
  Competitive Online Scheduling with Level of Service. 453-462
  
• Leah Epstein:
  On-Line Variable Sized Covering. 463-472
  

Randomized and Average-Case Algorithms

• Jin-yi Cai, Eric Bach:
  On Testing for Zero Polynomials by a Set of Points with Bounded Precision. 473-482
  
• Marek Chrobak, Leszek Gasieniec, Wojciech Rytter:
  A Randomized Algorithm for Gossiping in Radio Networks. 483-492
  
• Kyoichi Okamoto, Osamu Watanabe:
  Deterministic Application of Grover's Quantum Search Algorithm. 493-501
  
• Mitsuo Motoki:
  Random Instance Generation for MAX 3SAT. 502-508
  

Steiner Trees

• Ding-Zhu Du, Lusheng Wang, Baogang Xu:
  The Euclidean Bottleneck Steiner Tree and Steiner Tree with Minimum Number of Steiner Points. 509-518
  
• Guangting Chen, Guoliang Xue:
  An FPTAS for Weight-Constrained Steiner Trees in Series-Parallel Graphs. 519-528
  

Systems Algorithms and Modeling

• Zhe Dang, Oscar H. Ibarra, Richard A. Kemmerer:
  Decidable Approximations on Generalized and Parameterized Discrete Timed Automata. 529-539
  
• Zhixiang Chen:
  Multiplicative Adaptive Algorithms for User Preference Retrieval. 540-549
  
• K. Subramani:
  Parametric Scheduling for Network Constraints. 550-560
  
• Kaile Su, Xudong Luo, Huaiqing Wang, Chengqi Zhang, Shichao Zhang, Qingfeng Chen:
  A Logical Framework for Knowledge Sharing in Multi-agent Systems. 561-570
  
• Kumiko Obokata, Michiko Omori, Kazuhiro Motegi, Yoshihide Igarashi:
  A Lockout Avoidance Algorithm without Using Time-Stamps for the k-Exclusion Problem. 571-575
  

Computability

• Guohua Wu:
  Prefix-Free Languages and Initial Segments of Computably Enumerable Degrees. 576-585
  
• Robert Rettinger, Xizhong Zheng, Romain Gengler, Burchard von Braunmühl:
  Weakly Computable Real Numbers and Total Computable Real Functions. 586-595
  
• Klaus Weihrauch, Ning Zhong:
  Turing Computability of a Nonlinear Schrödinger Propagator. 596-600
  

Last update Mon May 20 22:38:48 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page