6. TAMC 2009: Changsha, China

Plenary Talks

• Leslie G. Valiant:
  Neural Computations That Support Long Mixed Sequences of Knowledge Acquisition Tasks. 1-2
  
• Moshe Y. Vardi:
  Constraints, Graphs, Algebra, Logic, and Complexity. 3
  
• Matthew Hennessy:
  Distributed Systems and Their Environments. 4-5
  

Invited Special Session: Models of Computation

• Alessandra Carbone, Lynda Dib:
  Co-evolution and Information Signals in Biological Sequences. 6-17
  
• S. Barry Cooper:
  The Extended Turing Model as Contextual Tool. 18-28
  
• Andrea Sorbi:
  Strong Positive Reducibilities. 29-38
  

Invited Special Session: Algorithms and Complexity

• Jiong Guo:
  Fixed-Parameter Algorithms for Graph-Modeled Date Clustering. 39-48
  
• Iyad A. Kanj:
  On Spanners of Geometric Graphs. 49-58
  
• Henning Fernau, Daniel Raible:
  Searching Trees: An Essay. 59-70
  
• Binhai Zhu:
  Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems. 71-80
  

Contributed Papers

• Faisal N. Abu-Khzam:
  A Quadratic Kernel for 3-Set Packing. 81-87
  
• Klaus Ambos-Spies, Thorsten Kräling:
  Quantitative Aspects of Speed-Up and Gap Phenomena. 88-97
  
• Ei Ando, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita:
  Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG. 98-107
  
• Evangelos Bampas, Andreas-Nikolas Göbel, Aris Pagourtzis, Aris Tentes:
  On the Connection between Interval Size Functions and Path Counting. 108-117
  
• Sergey Bereg, Minghui Jiang, Boting Yang, Binhai Zhu:
  On the Red/Blue Spanning Tree Problem. 118-127
  
• Jasper Berendsen, Taolue Chen, David N. Jansen:
  Undecidability of Cost-Bounded Reachability in Priced Probabilistic Timed Automata. 128-137
  
• Jin-yi Cai, Pinyan Lu, Mingji Xia:
  A Computational Proof of Complexity of Some Restricted Counting Problems. 138-149
  
• Maw-Shang Chang, Ling-Ju Hung, Ton Kloks, Sheng-Lung Peng:
  Block-Graph Width. 150-157
  
• Ruei-Yuan Chang, Guanling Lee, Sheng-Lung Peng:
  Minimum Vertex Ranking Spanning Tree Problem on Permutation Graphs. 158-167
  
• Jianer Chen, Iyad A. Kanj, Ge Xia:
  On Parameterized Exponential Time Complexity. 168-177
  
• Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai:
  Best-Order Streaming Model. 178-191
  
• Ernst-Erich Doberkat:
  Behavioral and Logical Equivalence of Stochastic Kripke Models in General Measurable Spaces. 192-200
  
• Michael Elberfeld, Ilka Schnoor, Till Tantau:
  Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data. 201-210
  
• Qilong Feng, Yang Liu, Songjian Lu, Jianxin Wang:
  Improved Deterministic Algorithms for Weighted Matching and Packing Problems. 211-220
  
• Jirí Fiala, Petr A. Golovach, Jan Kratochvíl:
  Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover. 221-230
  
• Bin Fu, Ming-Yang Kao, Lusheng Wang:
  Discovering Almost Any Hidden Motif from Multiple Sequences in Polynomial Time with Low Sample Complexity and High Success Probability. 231-240
  
• Pinar Heggernes, Daniel Meister, Charis Papadopoulos:
  A Complete Characterisation of the Linear Clique-Width of Path Powers. 241-250
  
• Markus Hinkelmann, Andreas Jakoby:
  Preserving Privacy versus Data Retention. 251-260
  
• Marc Kaplan, Sophie Laplante:
  Kolmogorov Complexity and Combinatorial Methods in Communication Complexity. 261-270
  
• Grégory Lafitte, Michael Weiss:
  An Almost Totally Universal Tile Set. 271-280
  
• Daniel Lokshtanov, Matthias Mnich, Saket Saurabh:
  Linear Kernel for Planar Connected Dominating Set. 281-290
  
• Maren Martens:
  A Simple Greedy Algorithm for the k-Disjoint Flow Problem. 291-300
  
• Takaaki Mizuki, Hitoshi Tsubata, Takao Nishizeki:
  Minimizing AND-EXOR Expressions for Multiple-Valued Two-Input Logic Functions. 301-310
  
• Paulo Eustáquio Duarte Pinto, Fábio Protti, Jayme Luiz Szwarcfiter:
  Exact and Experimental Algorithms for a Huffman-Based Error Detecting Code. 311-324
  
• Christoph Schubert:
  Terminal Coalgebras for Measure-Polynomial Functors. 325-334
  
• Andrea Sorbi, Guohua Wu, Yue Yang:
  High Minimal Pairs in the Enumeration Degrees. 335-344
  
• Bo Jiang, Xuehou Tan:
  Searching a Circular Corridor with Two Flashlights. 345-359
  
• Sophie Toulouse, Roberto Wolfler Calvo:
  On the Complexity of the Multiple Stack TSP, kSTSP. 360-369
  
• Anke van Zuylen:
  Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments. 370-379
  
• Fangju Wang, Kyle Swegles:
  An Online Algorithm for Applying Reinforcement Learning to Handle Ambiguity in Spoken Dialogues. 380-389
  
• Jianxin Wang, Guohong Jiang:
  A Fixed-Parameter Enumeration Algorithm for the Weighted FVS Problem. 390-399
  
• Lusheng Wang, Binhai Zhu:
  On the Tractability of Maximal Strip Recovery. 400-409
  
• Carsten Witt:
  Greedy Local Search and Vertex Cover in Sparse Random Graphs. 410-419
  
• Douglas Cenzer, Johanna N. Y. Franklin, Jiang Liu, Guohua Wu:
  Embedding the Diamond Lattice in the c.e. tt-Degrees with Superhigh Atoms. 420-429
  
• Zhilin Wu, Stéphane Grumbach:
  Feasibility of Motion Planning on Directed Graphs. 430-439
  
• Xiao Yin, Daming Zhu:
  Polynomial-Time Algorithm for Sorting by Generalized Translocations. 440-449
  
• John Z. Zhang:
  The Two-Guard Polygon Walk Problem. 450-459
  
• Peng Zhang, Jin-yi Cai, Linqing Tang, Wenbo Zhao:
  Approximation and Hardness Results for Label Cut and Related Problems. 460-469
  
• Zongyang Zhang, Zhenfu Cao, Rong Ma:
  An Observation on Non-Malleable Witness-Indistinguishability and Non-Malleable Zero-Knowledge. 470-479