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

by Jan Kratochvil (Editor), Angsheng Li (Editor), Jiri Fiala (Editor), Petr Kolman (Editor)

Overview

The 7th Annual Conference on Theory and Applications of Models of Compu- tion was held during June 7-11, 2010 in Prague. After six successful conferences held in 2004-2009 in China (Beijing, Kunming, Beijing, Shanghai, Xi'an, and ChangSha) TAMC left Asia for the ?rst time, aiming at the "heart of Europe. " Changingthegeographicallocationdidnotbringanychangestothescopeofthe conference. Its three main themes continued to be Computability, Complexity, and Algorithms. The conference aims to bring together researchersfrom all over the world with interests in theoretical computer science, algorithmic mathem- ics, andapplicationsto thephysicalsciences. Thisyearwesawmoreparticipants from Europe and the Americas, but we were very happy that we could also w- come to Prague traditional participants from Asia (China, Japan, and India) to continue enhancing the collaboration among the theoretical computer science communities of these continents. After hard work the Program Committee decided to accept 35 papers out of 76 submitted to TAMC 2010. Each submission was reviewed by at least three, Program Committee members. All actions of the Program Committee were - ordinated via ?awlessly and e?ciently running EasyChair. We congratulate the authors of accepted contributions and thank all authors who submitted their papers. They all contributed to a successful event. We extend our thanks to the distinguished plenary speakers who accepted our invitation to deliver plenary talks - John Hopcroft from Cornell University and Shang-Hua Teng from University of Southern California. Their talks "New Research Directions in the Information Age" and "The Laplacian Paradigm: Emerging Algorithms for Massive Graph" were highlights of the conference.

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(n²)-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.08537ⁿ) 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