Skip to main content
SpringerLink
Log in
Book cover

Computing and Combinatorics

20th International Conference, COCOON 2014, Atlanta, GA, USA, August 4-6, 2014, Proceedings

  • Conference proceedings
  • © 2014

Overview

Editors:
  1. Zhipeng Cai

    1. Department of Computer Science, Georgia State University, Atlanta, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Alex Zelikovsky

    1. Department of Computer Science, Georgia State University, Atlanta, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Anu Bourgeois

    1. Department of Computer Science, Georgia State University, Atlanta, USA

    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 8591)

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

Included in the following conference series:

Conference proceedings info: COCOON 2014.

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

  1. Front Matter

    Download chapter PDF

  2. Sampling and Randomized Methods

    1. Building above Read-once Polynomials: Identity Testing and Hardness of Representation

      • Meena Mahajan, B. V. Raghavendra Rao, Karteek Sreenivasaiah
      Pages 1-12

    2. Sampling from Dense Streams without Penalty

      • Vladimir Braverman, Gregory Vorsanger
      Pages 13-24

    3. L  ∞ -Discrepancy Analysis of Polynomial-Time Deterministic Samplers Emulating Rapidly Mixing Chains

      • Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita
      Pages 25-36

    4. Sampling Query Feedback Restricted Repairs of Functional Dependency Violations: Complexity and Algorithm

      • Dongjing Miao, Xianmin Liu, Jianzhong Li
      Pages 37-48

  3. Logic, Algebra and Automata

    1. Online Prediction Problems with Variation

      • Chia-Jung Lee, Shi-Chun Tsai, Ming-Chuan Yang
      Pages 49-60

    2. Nondeterministic Automatic Complexity of Almost Square-Free and Strongly Cube-Free Words

      • Kayleigh K. Hyde, Bjørn Kjos-Hanssen
      Pages 61-70

    3. An Axiomatization for Cylinder Computation Model

      • Nan Zhang, Zhenhua Duan, Cong Tian
      Pages 71-83

    4. Normal Form Expressions of Propositional Projection Temporal Logic

      • Zhenhua Duan, Cong Tian, Nan Zhang
      Pages 84-93

  4. Database and Data Structures

    1. On the Smoothed Heights of Trie and Patricia Index Trees

      • Weitian Tong, Randy Goebel, Guohui Lin
      Pages 94-103

    2. One-Dimensional k-Center on Uncertain Data

      • Haitao Wang, Jingru Zhang
      Pages 104-115

    3. The Range 1 Query (R1Q) Problem

      • Michael A. Bender, Rezaul A. Chowdhury, Pramod Ganapathi, Samuel McCauley, Yuan Tang
      Pages 116-128

    4. Competitive Cost-Savings in Data Stream Management Systems

      • Christine Chung, Shenoda Guirguis, Anastasia Kurdia
      Pages 129-140

  5. Parameterized Complexity and Algorithms(I)

    1. On the Kernelization Complexity of String Problems

      • Manu Basavaraju, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan, Saket Saurabh
      Pages 141-153

    2. Complexity of Dense Bicluster Editing Problems

      • Peng Sun, Jiong Guo, Jan Baumbach
      Pages 154-165

    3. Parameterized Complexity of Edge Interdiction Problems

      • Jiong Guo, Yash Raj Shrestha
      Pages 166-178

    4. Vertex Cover Gets Faster and Harder on Low Degree Graphs

      • Akanksha Agrawal, Sathish Govindarajan, Neeldhara Misra
      Pages 179-190

  6. Computational Complexity

    1. A Protocol for Generating Random Elements with Their Probabilities

      • Thomas Holenstein, Robin Künzler
      Pages 191-202

    2. A New View on Worst-Case to Average-Case Reductions for NP Problems

      • Thomas Holenstein, Robin Künzler
      Pages 203-214

    3. The Power of Duples (in Self-Assembly): It’s Not So Hip to Be Square

      • Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers, Scott M. Summers
      Pages 215-226
Back to top

Other volumes

  1. Computing and Combinatorics

Keywords

About this book

This book constitutes the refereed proceedings of the 20th International Conference on Computing and Combinatorics, COCOON 2014, held in Atlanta, GA, USA, in August 2014. The 51 revised full papers presented were carefully reviewed and selected from 110 submissions. There was a co-organized workshop on computational social networks (CSoNet 2014) where 8 papers were accepted. The papers cover the following topics: sampling and randomized methods; logic, algebra and automata; database and data structures; parameterized complexity and algorithms; computational complexity; computational biology and computational geometry; approximation algorithm; graph theory and algorithms; game theory and cryptography; scheduling algorithms and circuit complexity and CSoNet.

Editors and Affiliations

  • Department of Computer Science, Georgia State University, Atlanta, USA

    Zhipeng Cai, Alex Zelikovsky, Anu Bourgeois

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation