Skip to main content
SpringerLink
Log in
Book cover

Theory and Applications of Models of Computation

8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011, Proceedings

  • Conference proceedings
  • © 2011

Overview

Editors:
  1. Mitsunori Ogihara

    1. Department of Computer Science, University of Miami, Coral Gables, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Jun Tarui

    1. Department of Information and Communication Engineering, University of Electro-Comm, Tokyo, Japan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • State-of-the-art research
  • Fast-track conference proceedings
  • Unique visibility

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

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

Included in the following conference series:

Conference proceedings info: TAMC 2011.

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 (53 papers)

  1. Front Matter

    Download chapter PDF

  2. Invited Talk 1

    1. Designing Algorithms with Limited Work Space

      • Tetsuo Asano
      Pages 1-1

    3. Session 1B: Approximation I

      1. Approximating Edge Dominating Set in Dense Graphs
        • Richard Schmied, Claus Viehmann
        Pages 37-47
      2. Near Approximation of Maximum Weight Matching through Efficient Weight Reduction
        • Andrzej Lingas, Cui Di
        Pages 48-57
      3. Approximability of the Subset Sum Reconfiguration Problem
        • Takehiro Ito, Erik D. Demaine
        Pages 58-69

    4. Session 2A: Graph Algorithms I

      1. An Improved Kernel for Planar Connected Dominating Set
        • Weizhong Luo, Jianxin Wang, Qilong Feng, Jiong Guo, Jianer Chen
        Pages 70-81
      2. Fast Exact Algorithm for <i>L</i>(2,1)-Labeling of Graphs
        • Konstanty Junosza-Szaniawski, Jan Kratochvíl, Mathieu Liedloff, Peter Rossmanith, PaweÅ‚ Rza̧żewski
        Pages 82-93
      3. An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree
        • Takehiro Ito, Kazuto Kawamura, Xiao Zhou
        Pages 94-105

    5. Session 2B: Complexity I

      1. A Compact Encoding of Unordered Binary Trees
        • Kozue Iwata, Shiro Ishiwata, Shin-ichi Nakano
        Pages 106-113
      2. Low Distortion Metric Embedding into Constant Dimension
        • András Faragó
        Pages 114-123
      3. A Better Upper Bound on Weights of Exact Threshold Functions
        • Xue Chen, Guangda Hu, Xiaoming Sun
        Pages 124-132

    6. Session 3A: Optimization I

      1. Submodular Function Minimization under a Submodular Set Covering Constraint
        • Naoyuki Kamiyama
        Pages 133-141
      2. Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions
        • Akiyoshi Shioura, Shunya Suzuki
        Pages 142-153

    7. Session 3B: Circuit Complexity

      1. Energy and Fan-In of Threshold Circuits Computing Mod Functions
        • Akira Suzuki, Kei Uchizawa, Xiao Zhou
        Pages 154-163
      2. NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of <i>o</i>(loglog<i>n</i>) Depth
        • Fengming Wang
        Pages 164-170

  3. Invited Talk 2

    1. Quantum Complexity: Some Recent Results, Some Open Problems, Some Thoughts

      • Richard J. Lipton
      Pages 171-171

    2. Session 4A: Data Structures

      1. Non-adaptive Complex Group Testing with Multiple Positive Sets
        • Francis Y. L. Chin, Henry C. M. Leung, S. M. Yiu
        Pages 172-183
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 8th International Conference on Theory and Applications of Models of Computation, TAMC 2011, held in Tokyo, Japan, in May 2011. The 51 revised full papers presented together with the abstracts of 2 invited talks were carefully reviewed and selected from 136 submissions. The papers address the three main themes of the conference which were computability, complexity, and algorithms and are organized in topical sections on general algorithms, approximation, graph algorithms, complexity, optimization, circuit complexity, data structures, logic and formal language theory, games and learning theory, and cryptography and communication complexity.

Editors and Affiliations

  • Department of Computer Science, University of Miami, Coral Gables, USA

    Mitsunori Ogihara

  • Department of Information and Communication Engineering, University of Electro-Comm, Tokyo, Japan

    Jun Tarui

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation