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.
Author(s): John Hopcroft (auth.), Jan Kratochvíl, Angsheng Li, Jiří Fiala, Petr Kolman (eds.)
Series: Lecture Notes in Computer Science 6108 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 480
Tags: Theory of Computation; Mathematics of Computing; Algorithm Analysis and Problem Complexity; Logics and Meanings of Programs; Mathematical Logic and Formal Languages; Discrete Mathematics in Computer Science
Front Matter....Pages -
New Research Directions in the Information Age....Pages 1-1
The Laplacian Paradigm: Emerging Algorithms for Massive Graphs....Pages 2-14
Proof Complexity of Non-classical Logics....Pages 15-27
Optimal Acceptors and Optimal Proof Systems....Pages 28-39
The Complexity of Geometric Problems in High Dimension....Pages 40-49
Different Approaches to Proof Systems....Pages 50-59
Algebraic Proofs over Noncommutative Formulas....Pages 60-71
Nonlocal Quantum XOR Games for Large Number of Players....Pages 72-83
Nontriviality for Exponential Time w.r.t. Weak Reducibilities....Pages 84-93
Streaming Algorithms for Some Problems in Log-Space....Pages 94-104
Temperature Aware Online Scheduling with a Low Cooling Factor....Pages 105-116
On Solution Concepts for Matching Games....Pages 117-127
Binary De Bruijn Partial Words with One Hole....Pages 128-138
Complexity Invariance of Real Interpretations....Pages 139-150
Pivot and Loop Complementation on Graphs and Set Systems....Pages 151-162
Revisiting the Minimum Breakpoint Linearization Problem....Pages 163-174
An ${\mathcal{O}}(n^2)$ -time Algorithm for the Minimal Interval Completion Problem....Pages 175-186
Centdian Computation for Sensor Networks....Pages 187-198
Twisted Jacobi Intersections Curves....Pages 199-210
L (2,1,1)-Labeling Is NP-Complete for Trees....Pages 211-221
Complexity of Paths, Trails and Circuits in Arc-Colored Digraphs....Pages 222-233
The Max k -Cut Game and Its Strong Equilibria....Pages 234-246
Kernel and Fast Algorithm for Dense Triplet Inconsistency....Pages 247-257
Incremental List Coloring of Graphs, Parameterized by Conservation....Pages 258-270
Schnyder Greedy Routing Algorithm....Pages 271-283
Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width....Pages 284-295
A Note on the Testability of Ramsey’s Class....Pages 296-307
Deterministic Polynomial-Time Algorithms for Designing Short DNA Words....Pages 308-319
Hamiltonian Cycles in Subcubic Graphs: What Makes the Problem Difficult....Pages 320-327
A Dichotomy for k -Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions....Pages 328-339
Graph Sharing Games: Complexity and Connectivity....Pages 340-349
A Visual Model of Computation....Pages 350-360
An Automata-Theoretic Characterization of the Chomsky-Hierarchy....Pages 361-372
Maximum Independent Set in Graphs of Average Degree at Most Three in ${\mathcal O}(1.08537^n)$ ....Pages 373-384
Simultaneity in Event Structures....Pages 385-396
Safety Verification of Non-linear Hybrid Systems Is Quasi-Semidecidable....Pages 397-408
Closed Rectangle-of-Influence Drawings for Irreducible Triangulations....Pages 409-418
Recovering Social Networks from Contagion Information....Pages 419-430
Two-Layer Planarization Parameterized by Feedback Edge Set....Pages 431-442
A Categorical View of Timed Weak Bisimulation....Pages 443-454
Community Structure in Large Complex Networks....Pages 455-466
Generating Internally Triconnected Rooted Plane Graphs....Pages 467-478
Back Matter....Pages -
