Full Description
This book constitutes the refereed proceedings of the 13th Annual Conference on Theory and Applications of Models of Computation, TAMC 2016, held in Xi'an, China, in July 2016. The 23 full papers presented in this volume were carefully reviewed and selected from 35 submissions. They were organized in topical sections named: complexity theory; algorithms; networks and game theory; fixed parameter tractability; and computability theory.
Contents
Complexity theory.- Nondeterministic Communication Complexity of random Boolean functions.- Pebble games over ordered structural abstractions.- The Complexity of Finding Read-Once NAE-Resolution Refutations.- Bounds for Semi-disjoint Bilinear Forms in a Unit-cost Computational Model.- Learning AC0 under k-Dependent Distributions.- Algorithms.- Computing the Rectilinear Center of Uncertain Points in the Plane.- The Smoothed Number of Pareto-optimal Solutions in Non-integer Bicriteria Optimization.- Fast Searching on Cartesian Products of Graphs.- Parikh Images of Matrix Ins-del Systems.- Scheduling Fully Parallel Jobs with Integer Parallel Units.- An O(n2) Algorithm for Computing Optimal Continuous Voltage Schedules.- Continuous Firefighting on Infinite Square Grids.- Multi-interval Pairwise Compatibility Graphs.- Scheduling Tasks to Minimize Active Time on a Processor with Unlimited Capacity.- Efficient algorithms for touring a sequence of convex polygons and related problems.- Networks and game theory.- Hardness of Routing for Minimizing Superlinear Polynomial Cost in Directed Graphs.- P 3-Games.- The Price of Anarchy in Two-Stage Scheduling Games (Extended Abstract).- On Postoptimality Analysis of Maximum Reliability and Maximum Capacity Path Problems: Multiplicative Tolerances.- Fixed parameter tractability.- Kernelization and Parameterized Algorithms for 3-Path Vertex Cover.- Turbo-charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis.- Computability theory.- A Note on Effective Categoricity for Linear Orderings.- Degrees of Word Problem for Algebras without Finitely Presented Expansions.
