12. COCOON 2006: Taipei, Taiwan

Invited Talks

• Franco P. Preparata:
  The Unpredictable Deviousness of Models. 1
  
• Mikhail J. Atallah:
  Security Issues in Collaborative Computing. 2
  

Computational Economics, Finance, and Management

• Xi Chen, Xiaotie Deng:
  A Simplicial Approach for Discrete Fixed Point Theorems. 3-12
  
• Xi Chen, Xiaotie Deng, Becky Jie Liu:
  On Incentive Compatible Competitive Selection Protocol. 13-22
  
• George Karakostas, Stavros G. Kolliopoulos:
  Edge Pricing of Multicommodity Networks for Selfish Users with Elastic Demands. 23-32
  
• Shigeaki Harada, Eiji Takimoto, Akira Maruoka:
  Aggregating Strategy for Online Auctions. 33-41
  

Graph Algorithms

• Chandan K. Dubey, Shashank K. Mehta:
  On Indecomposability Preserving Elimination Sequences. 42-51
  
• Hung-I Yu, Tzu-Chin Lin, Biing-Feng Wang:
  Improved Algorithms for the Minmax Regret 1-Median Problem. 52-62
  
• Takehiro Ito, Kazuya Goto, Xiao Zhou, Takao Nishizeki:
  Partitioning a Multi-weighted Graph to Connected Subgraphs of Almost Uniform Size. 63-72
  
• Min Chih Lin, Jayme Luiz Szwarcfiter:
  Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs. 73-82
  

Computational Complexity and Computability

• Marats Golovkins, Jean-Eric Pin:
  Varieties Generated by Certain Models of Reversible Finite Automata. 83-93
  
• Ian McQuillan, Kai Salomaa, Mark Daley:
  Iterated TGR Languages: Membership Problem and Effective Closure Properties. 94-103
  
• Takayuki Sato, Kazuyuki Amano, Akira Maruoka:
  On the Negation-Limited Circuit Complexity of Sorting and Inverting k-tonic Sequences. 104-115
  

Quantum Computing

• Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi, Katsumasa Watanabe:
  Robust Quantum Algorithms with epsilon-Biased Oracles. 116-125
  
• Vikraman Arvind, Bireswar Das, Partha Mukhopadhyay:
  The Complexity of Black-Box Ring Problems. 126-135
  

Computational Biology and Medicine

• Xiuzhen Huang:
  Lower Bounds and Parameterized Approach for Longest Common Subsequence. 136-145
  
• M. Sohel Rahman, Costas S. Iliopoulos, Inbok Lee, Manal Mohamed, William F. Smyth:
  Finding Patterns with Variable Length Gaps or Don't Cares. 146-155
  
• Xin Dou, Xiaodong Wu, John E. Bayouth, John M. Buatti:
  The Matrix Orthogonal Decomposition Problem in Intensity-Modulated Radiation Therapy. 156-165
  

Computational Geometry

• Marc Benkert, Joachim Gudmundsson, Christian Knauer, Esther Moet, René van Oostrum, Alexander Wolff:
  A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem. 166-175
  
• Sergey Bereg, Ovidiu Daescu, Minghui Jiang:
  A PTAS for Cutting Out Polygons with Lines. 176-185
  
• Sheung-Hung Poon:
  On Unfolding Lattice Polygons/Trees and Diameter-4 Trees. 186-195
  
• Mattias Andersson, Joachim Gudmundsson, Christos Levcopoulos:
  Restricted Mesh Simplification Using Edge Contractions. 196-204
  

Graph Theory

• David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-ichi Tanigawa:
  Enumerating Non-crossing Minimally Rigid Frameworks. 205-215
  
• Zvi Lotker, Debapriyo Majumdar, N. S. Narayanaswamy, Ingmar Weber:
  Sequences Characterizing k-Trees. 216-225
  
• Yong Gao:
  On the Threshold of Having a Linear Treewidth in Random Graphs. 226-234
  

Computational Biology

• Wen-Chieh Chang, Oliver Eulenstein:
  Reconciling Gene Trees with Apparent Polytomies. 235-244
  
• Zhixiang Chen, Richard H. Fowler, Bin Fu, Binhai Zhu:
  Lower Bounds on the Approximation of the Exemplar Conserved Interval Distance Problem of Genomes. 245-254
  
• Fredrik Bengtsson, Jingsen Chen:
  Computing Maximum-Scoring Segments in Almost Linear Time. 255-264
  

Graph Algorithms and Applications

• Daniel Mölle, Stefan Richter, Peter Rossmanith:
  Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants. 265-273
  
• Hiroshi Nagamochi:
  A Detachment Algorithm for Inferring a Graph from Path Frequency. 274-283
  
• Ying Xiao, Christoforos N. Hadjicostis, Krishnaiyan Thulasiraman:
  The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm. 284-298
  
• Iyad A. Kanj, Luay Nakhleh, Ge Xia:
  Reconstructing Evolution of Natural Languages: Complexity and Parameterized Algorithms. 299-308
  

On-Line Algorithms

• Wun-Tat Chan, Prudence W. H. Wong, Fencol C. C. Yung:
  On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis. 309-319
  
• Feifeng Zheng, Stanley P. Y. Fung, Wun-Tat Chan, Francis Y. L. Chin, Chung Keung Poon, Prudence W. H. Wong:
  Improved On-Line Broadcast Scheduling with Deadlines. 320-329
  
• Regant Y. S. Hung, H. F. Ting:
  A Tight Analysis of Most-Requested-First for On-Demand Data Broadcast. 330-339
  
• Mingen Lin, Yang Yang, Jinhui Xu:
  On Lazy Bin Covering and Packing Problems. 340-349
  

Graph Theory

• Vlady Ravelomanana, Alphonse Laza Rijamamy:
  Creation and Growth of Components in a Random Hypergraph Process. 350-359
  
• Rahul Muthu, N. Narayanan, C. R. Subramanian:
  Optimal Acyclic Edge Colouring of Grid Like Graphs. 360-367
  
• Hongbing Fan, Robert Kalbfleisch:
  An Edge Ordering Problem of Regular Hypergraphs. 368-377
  

Algorithms for Security and Systems

• Zheng Gong, Xiangxue Li, Kefei Chen:
  Efficient Partially Blind Signature Scheme with Provable Security. 378-386
  
• Eitan Bachmat, Tao-Kai Lam, Avner Magen:
  A Rigorous Analysis for Set-Up Time Models - A Metric Perspective. 387-397
  

Discrete Geometry and Graph Theory

• L. Sunil Chandran, Naveen Sivadasan:
  Geometric Representation of Graphs in Low Dimension. 398-407
  
• Gill Barequet, Alina Shaikhet:
  The On-Line Heilbronn's Triangle Problem in d Dimensions. 408-417
  
• Gadi Aleksandrowicz, Gill Barequet:
  Counting d-Dimensional Polycubes and Nonrectangular Planar Polyominoes. 418-427
  

Approximation Algorithms

• Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten:
  Approximating Min-Max (Regret) Versions of Some Polynomial Problems. 428-438
  
• E. C. Xavier, Flávio Keidi Miyazawa:
  The Class Constrained Bin Packing Problem with Applications to Video-on-Demand. 439-448
  
• Sun-Yuan Hsieh, Shih-Cheng Yang:
  MAX-SNP Hardness and Approximation of Selected-Internal Steiner Trees. 449-458
  
• Jianbo Li, Mingxia Chen, Jianping Li, Weidong Li:
  Minimum Clique Partition Problem with Constrained Weight for Interval Graphs. 459-468
  

Computational Complexity and Computability

• Yo-Sub Han, Derick Wood:
  Overlap-Free Regular Languages. 469-478
  
• Joel Ratsaby:
  On the Combinatorial Representation of Information. 479-488
  
• Jesper Torp Kristensen, Peter Bro Miltersen:
  Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard. 489-496
  

Experimental Algorithms

• Christoph Buchheim, Michael Jünger, Annette Menze, Merijam Percan:
  Bimodal Crossing Minimization. 497-506
  
• Christoph Buchheim, Lanbo Zheng:
  Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem. 507-516
  
• Dae-Sik Choi, In-Chan Choi:
  On the Effectiveness of the Linear Programming Relaxation of the 0-1 Multi-commodity Minimum Cost Network Flow Problem. 517-526
  

Last update Sat May 18 18:17:14 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page