16. COCOON 2010: Nha Trang, Vietnam

Invited Talks

• Manuel Blum:
  Understanding and Inductive Inference. 1
  
• Oscar H. Ibarra:
  Computing with Cells: Membrane Systems. 2
  

Complexity and Inapproximability

• Abhijin Adiga, Diptendu Bhowmick, L. Sunil Chandran:
  Boxicity and Poset Dimension. 3-12
  
• Chi-Jen Lu, Hsin-Lung Wu:
  On the Hardness against Constant-Depth Linear-Size Circuits. 13-22
  
• Ricky Rosen:
  A K-Provers Parallel Repetition Theorem for a Version of No-Signaling Model. 23-33
  
• Henning Fernau, Fedor V. Fomin, Geevarghese Philip, Saket Saurabh:
  The Curse of Connectivity: t-Total Vertex (Edge) Cover. 34-43
  
• Andreas Krebs, Nutan Limaye, Meena Mahajan:
  Counting Paths in VPA Is Complete for #NC¹. 44-53
  
• Rahul Jain, Hartmut Klauck, Shengyu Zhang:
  Depth-Independent Lower Bounds on the Communication Complexity of Read-Once Boolean Formulas. 54-59
  

Approximation Algorithms

• Anke van Zuylen:
  Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing. 60-69
  
• Frans Schalekamp, Michael Yu, Anke van Zuylen:
  Clustering with or without the Approximation. 70-79
  
• Sayaka Kamei, Hirotsugu Kakugawa, Stéphane Devismes, Sébastien Tixeuil:
  A Self-stabilizing 3-Approximation for the Maximum Leaf Spanning Tree Problem in Arbitrary Networks. 80-89
  
• John Augustine, David Eppstein, Kevin A. Wortman:
  Approximate Weighted Farthest Neighbors and Minimum Dilation Stars. 90-99
  
• Yong Zhang, Francis Y. L. Chin, Hing-Fung Ting:
  Approximated Distributed Minimum Vertex Cover Algorithms for Bounded Degree Graphs. 100-109
  

Graph Theory and Algorithms

• Aimal Rextin, Patrick Healy:
  Maximum Upward Planar Subgraph of a Single-Source Embedded Digraph. 110-119
  
• Maxim A. Babenko, Alexey Gusakov, Ilya P. Razenshteyn:
  Triangle-Free 2-Matchings Revisited. 120-129
  
• Tobias Friedrich, Thomas Sauerwald:
  The Cover Time of Deterministic Random Walks. 130-139
  
• Doron Nussbaum, Shuye Pu, Jörg-Rüdiger Sack, Takeaki Uno, Hamid Zarrabi-Zadeh:
  Finding Maximum Edge Bicliques in Convex Bipartite Graphs. 140-149
  
• Mingyu Xiao:
  A Note on Vertex Cover in Graphs with Maximum Degree 3. 150-159
  
• Giorgio Ausiello, Paolo Giulio Franciosa, Giuseppe F. Italiano, Andrea Ribichini:
  Computing Graph Spanners in Small Memory: Fault-Tolerance and Streaming. 160-172
  
• Alain Bretto, Yannick Silvestre:
  Factorization of Cartesian Products of Hypergraphs. 173-181
  

Graph Drawing and Coloring

• Sudip Biswas, Debajyoti Mondal, Rahnuma Islam Nishat, Md. Saidur Rahman:
  Minimum-Segment Convex Drawings of 3-Connected Cubic Plane Graphs. 182-191
  
• Josef Cibulka, Jan Kyncl, Viola Mészáros, Rudolf Stolar, Pavel Valtr:
  On Three Parameters of Invisibility Graphs. 192-198
  
• Daniel Lokshtanov, Neeldhara Misra, Saket Saurabh:
  Imbalance Is Fixed Parameter Tractable. 199-208
  
• I. W. Sudarsana, Adiwijaya, S. Musdalifah:
  The Ramsey Number for a Linear Forest versus Two Identical Copies of Complete Graphs. 209-215
  

Computational Geometry

• Mark de Berg, Amirali Khosravi:
  Optimal Binary Space Partitions in the Plane. 216-225
  
• Piotr Berman, Marek Karpinski, Andrzej Lingas:
  Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. 226-234
  
• Shinya Anzai, Jinhee Chun, Ryosei Kasai, Matias Korman, Takeshi Tokuyama:
  Effect of Corner Information in Simultaneous Placement of K Rectangles and Tableaux. 235-243
  
• Bojan Djordjevic, Joachim Gudmundsson:
  Detecting Areas Visited Regularly. 244-253
  
• Marek Chrobak, Christoph Dürr, Flavio Guiñez, Antoni Lozano, Nguyen Kim Thang:
  Tile-Packing Tomography Is \mathbbNP{\mathbb{NP}}-hard. 254-263
  
• Vladimir Estivill-Castro, Apichat Heednacram, Francis Suraweera:
  The Rectilinear k-Bends TSP. 264-277
  
• Oleksiy Busaryev, Tamal K. Dey, Yusu Wang:
  Tracking a Generator by Persistence. 278-287
  
• Alejandro Erickson, Frank Ruskey, Mark Schurch, Jennifer Woodcock:
  Auspicious Tatami Mat Arrangements. 288-297
  

Automata, Logic, Algebra and Number Theory

• Alexander E. Holroyd, Frank Ruskey, Aaron Williams:
  Faster Generation of Shorthand Universal Cycles for Permutations. 298-307
  
• Xue Chen, Guangda Hu, Xiaoming Sun:
  The Complexity of Word Circuits. 308-317
  
• Michael Hartwig:
  On the Density of Regular and Context-Free Languages. 318-327
  
• Rustem Takhanov:
  Extensions of the Minimum Cost Homomorphism Problem. 328-337
  
• Amr Elmasry:
  The Longest Almost-Increasing Subsequence. 338-347
  
• Satoshi Tayu, Shota Fukuyama, Shuichi Ueno:
  Universal Test Sets for Reversible Circuits. 348-357
  
• Miklós Csürös:
  Approximate Counting with a Floating-Point Counter. 358-367
  

Network Optimization and Scheduling Algorithm

• Yu-Hsuan Su, Ching-Chi Lin, D. T. Lee:
  Broadcasting in Heterogeneous Tree Networks. 368-377
  
• Antonio Fernández Anta, Miguel A. Mosteiro:
  Contention Resolution in Multiple-Access Channels: k-Selection in Radio Networks. 378-388
  
• Stanley P. Y. Fung:
  Online Preemptive Scheduling with Immediate Decision or Notification and Penalties. 389-398
  

Computational Biology and Bioinformatics

• Muhammad Nur Yanhaona, Md. Shamsuzzoha Bayzid, Md. Saidur Rahman:
  Discovering Pairwise Compatibility Graphs. 399-408
  
• Lusheng Wang:
  Near Optimal Solutions for Maximum Quasi-bicliques. 409-418
  
• Yunlong Liu, Xiaodong Wu:
  Fast Coupled Path Planning: From Pseudo-Polynomial to Polynomial. 419-428
  
• Bin Fu, Lusheng Wang:
  Constant Time Approximation Scheme for Largest Well Predicted Subset. 429-438
  
• Xin Chen:
  On Sorting Permutations by Double-Cut-and-Joins. 439-448
  
• Zhi-Zhong Chen, Bin Ma, Lusheng Wang:
  A Three-String Approach to the Closest String Problem. 449-458
  
• Jianer Chen, Jie Meng:
  A 2k Kernel for the Cluster Editing Problem. 459-468
  

Data Structure and Sampling Theory

• Sylvain Lazard, Christophe Weibel, Sue Whitesides, Linqiao Zhang:
  On the Computation of 3D Visibility Skeletons. 469-478
  
• Amr Elmasry:
  The Violation Heap: A Relaxed Fibonacci-Like Heap. 479-488
  
• Eric Bach, Shuchi Chawla, Seeun Umboh:
  Threshold Rules for Online Sample Selection. 489-499
  
• Meng-Tsung Tsai, Da-Wei Wang, Churn-Jung Liau, Tsan-sheng Hsu:
  Heterogeneous Subset Sampling. 500-509
  

Cryptography, Security, Coding and Game Theory

• Lei Zhang, Qianhong Wu, Bo Qin, Josep Domingo-Ferrer:
  Identity-Based Authenticated Asymmetric Group Key Agreement Protocol. 510-519
  
• Sherman S. M. Chow, Changshe Ma, Jian Weng:
  Zero-Knowledge Argument for Simultaneous Discrete Logarithms. 520-529
  
• Michal Kolarz:
  Directed Figure Codes: Decidability Frontier. 530-539
  

Last update Thu May 24 04:15:03 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page