| Description |
1 online resource (xv, 564 pages) : illustrations |
| 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.
|
| 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 |
| 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 |
| Bibliography |
Includes bibliographical references and author index |
| Notes |
Print version record |
| Subject |
Computer science -- Mathematics -- Congresses
|
|
Computational complexity -- Congresses
|
|
Computable functions -- Congresses
|
|
Informatique.
|
|
Computable functions
|
|
Computational complexity
|
|
Computer science -- Mathematics
|
| Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
| Form |
Electronic book
|
| Author |
Ogihara, Mitsunori, 1963- editor.
|
|
Tarui, Jun, editor
|
| ISBN |
9783642208775 |
|
3642208770 |
|
3642208762 |
|
9783642208768 |
|
