Skip to main content
SpringerLink
Log in
Book cover

Theory and Applications of Models of Computation

6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings

  • Conference proceedings
  • © 2009

Overview

Editors:
  1. Jianer Chen

    1. Department of Computer Science and Engineering, Texas A&M University, Texas, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. S. Barry Cooper

    1. School of Mathematics, University of Leeds, U.K.

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 5532)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: TAMC 2009.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (49 papers)

  1. Front Matter

    Download chapter PDF

  3. Invited Special Session: Models of Computation

    1. Co-evolution and Information Signals in Biological Sequences

      • Alessandra Carbone, Linda Dib
      Pages 6-17

    2. The Extended Turing Model as Contextual Tool

      • S. Barry Cooper
      Pages 18-28

    3. Strong Positive Reducibilities

      • Andrea Sorbi
      Pages 29-38

  4. Invited Special Session: Algorithms and Complexity

    1. Fixed-Parameter Algorithms for Graph-Modeled Date Clustering

      • Jiong Guo
      Pages 39-48

    2. On Spanners of Geometric Graphs

      • Iyad A. Kanj
      Pages 49-58

    3. Searching Trees: An Essay

      • Henning Fernau, Daniel Raible
      Pages 59-70

    4. Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems

      • Binhai Zhu
      Pages 71-80

  5. Contributed Papers

    1. A Quadratic Kernel for 3-Set Packing

      • Faisal N. Abu-Khzam
      Pages 81-87

    2. Quantitative Aspects of Speed-Up and Gap Phenomena

      • Klaus Ambos-Spies, Thorsten Kräling
      Pages 88-97

    3. Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG

      • Ei Ando, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita
      Pages 98-107

    4. On the Connection between Interval Size Functions and Path Counting

      • Evangelos Bampas, Andreas-Nikolas Göbel, Aris Pagourtzis, Aris Tentes
      Pages 108-117

    5. On the Red/Blue Spanning Tree Problem

      • Sergey Bereg, Minghui Jiang, Boting Yang, Binhai Zhu
      Pages 118-127

    6. Undecidability of Cost-Bounded Reachability in Priced Probabilistic Timed Automata

      • Jasper Berendsen, Taolue Chen, David N. Jansen
      Pages 128-137

    7. A Computational Proof of Complexity of Some Restricted Counting Problems

      • Jin-Yi Cai, Pinyan Lu, Mingji Xia
      Pages 138-149

    8. Block-Graph Width

      • Maw-Shang Chang, Ling-Ju Hung, Ton Kloks, Sheng-Lung Peng
      Pages 150-157

    9. Minimum Vertex Ranking Spanning Tree Problem on Permutation Graphs

      • Ruei-Yuan Chang, Guanling Lee, Sheng-Lung Peng
      Pages 158-167
Back to top

Other volumes

  1. Theory and Applications of Models of Computation

Keywords

About this book

This book constitutes the refereed proceedings of the 6th International Conference on Theory and Applications of Models of Computation, TAMC 2009, held in Changsha, China in May 2009. The 39 full papers presented together with 7 invited papers as well as 3 plenary talks were selected from 86 submissions. The papers address the three main themes of the conference which were Computability, Complexity, and Algorithms. The conference aimed to bring together researchers with interests in theoretical computer science, algorithmic mathematics, and applications to the physical sciences.

Editors and Affiliations

  • Department of Computer Science and Engineering, Texas A&M University, Texas, USA

    Jianer Chen

  • School of Mathematics, University of Leeds, U.K.

    S. Barry Cooper

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation