Theory and Applications of Models of Computation: 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings

Theory and Applications of Models of Computation: 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings


$124.80 $129.00 Save 3% Current price is $124.8, Original price is $129. You Save 3%.
Choose Expedited Shipping at checkout for guaranteed delivery by Thursday, January 30
5 New & Used Starting at $83.28


This book constitutes the refereed proceedings of the 7th International
Conference on Theory and Applications of Models of Computation, TAMC
2010, held in Prague, Czech Republic, in June 2010.

The 35 revised full papers presented together with 5 contributions of special sessions as well as 2 plenary talks were carefully reviewed and selected from 76 submissions. The papers address the three main themes of the conference which were computability, complexity, and algorithms and present current research in these fields with aspects to theoretical computer science, algorithmic mathematics, and applications to the physical sciences.

Product Details

ISBN-13: 9783642135613
Publisher: Springer Berlin Heidelberg
Publication date: 07/16/2010
Series: Lecture Notes in Computer Science , #6108
Edition description: 2010
Pages: 480
Product dimensions: 6.20(w) x 9.20(h) x 1.10(d)

Table of Contents

Plenary Talks

New Research Directions in the Information Age John E. Hopcroft 1

The Laplacian Paradigm: Emerging Algorithms for Massive Graphs Shang-Hua Teng 2

Special Sessions

Proof Complexity of Non-classical Logics Olaf Beyersdorff 15

Optimal Acceptors and Optimal Proof Systems Edward A. Hirsch 28

The Complexity of Geometric Problems in High Dimension Christian Knauer 40

Different Approaches to Proof Systems Olaf Beyersdorff Sebastian Müller 50

Algebraic Proofs over Noncommutative Formulas Iddo Tzameret 60

Contributed Papers

Nonlocal Quantum XOR Games for Large Number of Players Andris Ambainis Dmitry Kravchenko Nikolajs Nahimovs Alexander Rivosh 72

Nontriviality for Exponential Time w.r.t. Weak Reducibilities Klaus Ambos-Spies Timur Bakibayev 84

Streaming Algorithms for Some Problems in Log-Space Ajesh Babu Nutan Limaye Girish Varma 94

Temperature Aware Online Scheduling with a Low Cooling Factor Martin Birks Stanley P.Y. Fung 105

On Solution Concepts for Matching Games Péter Biró Walter Kern Danië Paulusma 117

Binary De Bruijn Partial Words with One Hole Francine Blanchet-Sadri Jarett Schwartz Slater Stich Benjamin J. Wyatt 128

Complexity Invariance of Real Interpretations Guillaume Bonfante Florian Deloup 139

Pivot and Loop Complementation on Graphs and Set Systems Robert Brijder Hendrik Jan Hoogeboom 151

Revisiting the Minimum Breakpoint Linearization Problem Laurent Bulteau Guillaume Fertin Irena Rusu 163

An O(n2)-Time Algorithm for the Minimal Interval Completion Problem Christophe Crespelle Ioan Todinca 175

Centdian Computation for Sensor Networks Boaz Ben-Moshe Amit Dvir Michael Segal Arie Tamir 187

Twisted Jacobi Intersections Curves Rongquan Feng Menglong Nie Hongfeng Wu 199

L (2,1,1)-Labeling Is NP-Complete for Trees Petr A. Golovach Bernard Lidický Daniël Paulusma 211

Complexity of Paths, Trails and Circuits in Arc-Colored Digraphs Laurent Gourvès Adria Lyra Carlos Martinhon Jéôme Monnot 222

The Max k-Cut Game and Its Strong Equilibria Laurent Gourvès Jérôme Monnot 234

Kernel and Fast Algorithm for Dense Triplet Inconsistency Sylvain Guillemot Matthias Mnich 247

Incremental List Coloring of Graphs, Parameterized by Conservation Sepp Hartung Rolf Niedermeier 258

Schnyder Greedy Routing Algorithm Xin He Huaming Zhang 271

Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width Pinar Heggernes Daniel Meister Udi Rotics 284

A Note on the Testability of Ramsey's Class Charles Jordan Thomas Zeugmann 296

Deterministic Polynomial-Time Algorithms for Designing Short DNA Words Ming-Yang Kao Henry C.M. Leung He Sun Yong Zhang 308

Hamiltonian Cycles in Subcubic Graphs: What Makes the Problem Difficult Nicholas Korpelainen Vadim V. Lozin Alexander Tiskin 320

A Dichotomy for k-Regular Graphs with {0,1}-Vertex Assignments and Real Edge Functions Jin-Yi Cai Michael Kowalczyk 328

Graph Sharing Games: Complexity and Connectivity Josef Cibulka Jan Kyncl Viola Mészáros Rudolf Stolar Pavel Valtr 340

A Visual Model of Computation Ian Mackie 350

An Automata-Theoretic Characterization of the Chomsky-Hierarchy Benedek Nagy 361

Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537n) Nicolas Bourgeois Bruno Escoffier Vangelis Th, Paschos Johan M.M. van Rooij 373

Simultaneity in Event Structures G. Michele Pinna Andrea Saba 385

Safety Verification of Non-linear Hybrid Systems is Quasi-Semidecidable Stefan Ratschan 397

Closed Rectangle-of-Influence Drawings for Irreducible Triangulations Sadish Sadasivam Huaming Zhang 409

Recovering Social Networks from Contagion Information Sucheta Soundarajan John E. Hopcroft 419

Two-Layer Planarization Parameterized by Feedback Edge Set Johannes Uhlmann Mathias Weller 431

A Categorical View of Timed Weak Bisimulation Natalya Gribovskaya Irina Virbitskaite 443

Community Structure in Large Complex Networks Liaoruo Wang John E. Hopcroft 455

Generating Internally Triconnected Rooted Plane Graphs Bingbing Zhuang Hiroshi Nagamochi 467

Author Index 479

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews