Theory and Applications of Models of Computation: 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings (Lecture Notes in Computer Science, 6108)

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. 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 - 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 Annotation This Book Constitutes The Refereed Proceedings Of The 7th Internationalconference On Theory And Applications Of Models Of Computation, Tamc2010, Held In Prague, Czech Republic, In June 2010.the 35 Revised Full Papers Presented Together With 5 Contributions Ofspecial Sessions As Well As 2 Plenary Talks Were Carefully Reviewed Andselected From 76 Submissions. The Papers Address The Three Main Themesof The Conference Which Were Computability, Complexity, And Algorithmsand Present Current Research In These Fields With Aspects To Theoreticalcomputer Science, Algorithmic Mathematics, And Applications To Thephysical Sciences. Annotation This book constitutes the refereed proceedings of the 7th InternationalConference on Theory and Applications of Models of Computation, TAMC2010, held in Prague, Czech Republic, in June 2010. The 35 revised full papers presented together with 5 contributions ofspecial sessions as well as 2 plenary talks were carefully reviewed andselected from 76 submissions. The papers address the three main themesof the conference which were computability, complexity, and algorithmsand present current research in these fields with aspects to theoreticalcomputer science, algorithmic mathematics, and applications to thephysical sciences