Return to home page
Searching: Muskingum library catalog
We are currently experiencing delivery delays for items requested from other institutions while transitioning to a new statewide delivery service. Please contact your library with questions or advice about alternative resources. Thank you for your patience!
  Previous Record Previous Item Next Item Next Record
  Reviews, Summaries, etc...
Conference TAMC (Conference) (8th : 2011 : Tokyo, Japan)
Title Theory and applications of models of computation : 8th annual conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011, proceedings / Mitsunori Ogihara, Jun Tarui (eds.).
Imprint Berlin ; Heidelberg ; New York : Springer, 2011.

View online
View online
Conference TAMC (Conference) (8th : 2011 : Tokyo, Japan)
Series Lecture notes in computer science, 1611-3349 ; 6648
LNCS sublibrary. SL 1, Theoretical computer science and general issues
Lecture notes in computer science ; 6648. 0302-9743
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
Subject Computer science -- Mathematics -- Congresses.
Computational complexity -- Congresses.
Computable functions -- Congresses.
Alt Name Ogihara, Mitsunori, 1963-
Tarui, Jun,
Add Title TAMC 2011
Description 1 online resource (xv, 564 pages) : illustrations
Bibliography Note Includes bibliographical references and author index.
Note Print version record.
Summary This book constitutes the refereed proceedings of the 8th International Conference on Theory and Applications of Models of Computation, TAMC 2011, held in Tokyo, Japan, in May 2011. The 51 revised full papers presented together with the abstracts of 2 invited talks were carefully reviewed and selected from 136 submissions. The papers address the three main themes of the conference which were computability, complexity, and algorithms and are organized in topical sections on general algorithms, approximation, graph algorithms, complexity, optimization, circuit complexity, data structures, logic and formal language theory, games and learning theory, and cryptography and communication complexity.
Contents Machine generated contents note: Designing Algorithms with Limited Work Space (Abstract) / Tetsuo Asano -- Session 1A General Algorithms -- Group-Theoretic Lower Bounds for the Complexity of Matrix Multiplication / Alexey Pospelov -- Real Elementary Approach to the Master Recurrence and Generalizations / Chee Yap -- Multiprocessor Speed Scaling for Jobs with Arbitrary Sizes and Deadlines / Prudence W.H. Wong -- Session 1B Approximation I -- Approximating Edge Dominating Set in Dense Graphs / Claus Viehmann -- Near Approximation of Maximum Weight Matching through Efficient Weight Reduction / Cui Di -- Approximability of the Subset Sum Reconfiguration Problem / Erik D. Demaine -- Session 2A Graph Algorithms I -- Improved Kernel for Planar Connected Dominating Set / Jianer Chen -- Fast Exact Algorithm for L(2,1)-Labeling of Graphs / Pawet Rzazewski -- ̂
Note continued: How to Cut a Graph into Many Pieces / Alexander Grigoriev -- Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet / Satti Srinivasa Rao -- Integer Representations towards Efficient Counting in the Bit Probe Model / Satti Srinivasa Rao -- Session 4B Logic and Formal Language Theory -- Closed Left-R.E. Sets / Jason Teutsch -- II 0 1 Sets and Tilings / Pascal Vanier -- Intuitive Probability Logic / Chunlai Zhou -- Algebraic Characterization of Strictly Piecewise Languages / Herbert G. Tanner -- Session 5A Graph Algorithms II -- Deterministic Algorithms for Multi-criteria TSP / Bodo Manthey -- Extending Partial Representations of Interval Graphs / Tomas Vyskocil -- Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way (Extended Abstract) / Serafino Cicerone -- Session 5B Approximation II -- ̂ Complexity and Approximability of Minimum Contamination Problems / Linqing Tang -- On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric / Rouven Naujoks -- Lower Bounds for Testing Computability by Small Width OBDDs / Chenggang Wu -- Session 6A Games and Learning Theory -- On the Amount of Nonconstructivity in Learning Recursive Functions / Thomas Zeugmann -- Bad Instance for k-Means++ / Heiko Roglin -- Catching a Fast Robber on Interval Graphs / Tomas Gavenciak -- Some Tractable Win-Lose Games / Nagarajan Krishnamurthy -- Session 6B Cryptography and Communication Complexity -- Note on Obfuscation for Cryptographic Functionalities of Secret-Operation Then Public-Encryption / Dawu Gu -- Grey-Box Steganography / Ulrich Wolfel -- Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models / Shengyu Zhang -- Hardness of Median in the Synchronized Bit Communication Model / Karolina Sottys -- Session 7A Optimization II
Note continued: Lower Bounds for the Smoothed Number of Pareto Optimal Solutions / Heiko Roglin -- Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands / Takuro Fukunaga -- Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects / Hiroki Yanagisawa -- Session 7B Complexity II -- Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem / Takeaki Uno -- Switching to Hedgehog-Free Graphs Is NP-Complete / Eva Jelinkova -- Locally Injective Hoinomorphism to the Simple Weight Graphs / Marek Tesar -- Session 8A Graph Algorithms III -- Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width / Takeaki Uno -- Hide-and-Seek: Algorithms for Polygon Walk Problems / Jun Luo -- Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory (Extended Abstract) / Somnath Sikdar -- Session 8B Complexity III -- On the Polynomial Depth of Various Sets of Random Strings / Philippe Moser -- Edge Contractions in Subclasses of Chordal Graphs / Pim van't Hof -- Planarity Testing Revisited / Gautam Prakriya -- Generalized Satisfiability for the Description Logic ACC (Extended Abstract) / Thomas Schneider.
ISBN 9783642208775 (electronic bk.)
3642208770 (electronic bk.)
9783642208768 (print)
3642208762 (Trade Paper)
ISBN/ISSN 10.1007/978-3-642-20877-5
OCLC # 728098412
Additional Format Print version: Theory and applications of models of computation. Berlin : Springer, 2011 9783642208768 (DLC) 2011926299 (OCoLC)724304390

If you experience difficulty accessing or navigating this content, please contact the OPAL Support Team