Theory and Applications of Models of Computation
13th Annual Conference, TAMC 2016, Xi'an, China, July 20-22, 2016, Proceedings
Published on 17. August 2016
Book
Paperback/Softback
337 pages
978-3-319-43345-5 (ISBN)
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.
More details
Series
Edition
1st ed. 2016
Language
English
Place of publication
Cham
Switzerland
Target group
Professional and scholarly
Illustrations
60 s/w Abbildungen
60 black & white illustrations, biography
Dimensions
Height: 235 mm
Width: 155 mm
ISBN-13
978-3-319-43345-5 (9783319433455)
DOI
10.1007/978-3-319-43346-2
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Persons
Content
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.