↓ Skip to main content
What is this page? Embed badge

Theory and Applications of Models of Computation

Overview of attention for book
Cover of 'Theory and Applications of Models of Computation'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 Designing Algorithms with Limited Work Space
  3. Altmetric Badge
    Chapter 2 Group-Theoretic Lower Bounds for the Complexity of Matrix Multiplication
  4. Altmetric Badge
    Chapter 3 A Real Elementary Approach to the Master Recurrence and Generalizations
  5. Altmetric Badge
    Chapter 4 Multiprocessor Speed Scaling for Jobs with Arbitrary Sizes and Deadlines
  6. Altmetric Badge
    Chapter 5 Approximating Edge Dominating Set in Dense Graphs
  7. Altmetric Badge
    Chapter 6 Near Approximation of Maximum Weight Matching through Efficient Weight Reduction
  8. Altmetric Badge
    Chapter 7 Approximability of the Subset Sum Reconfiguration Problem
  9. Altmetric Badge
    Chapter 8 An Improved Kernel for Planar Connected Dominating Set
  10. Altmetric Badge
    Chapter 9 Fast Exact Algorithm for L (2,1)-Labeling of Graphs
  11. Altmetric Badge
    Chapter 10 An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree
  12. Altmetric Badge
    Chapter 11 A Compact Encoding of Unordered Binary Trees
  13. Altmetric Badge
    Chapter 12 Low Distortion Metric Embedding into Constant Dimension
  14. Altmetric Badge
    Chapter 13 A Better Upper Bound on Weights of Exact Threshold Functions
  15. Altmetric Badge
    Chapter 14 Submodular Function Minimization under a Submodular Set Covering Constraint
  16. Altmetric Badge
    Chapter 15 Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions
  17. Altmetric Badge
    Chapter 16 Energy and Fan-In of Threshold Circuits Computing Mod Functions
  18. Altmetric Badge
    Chapter 17 NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o (loglog n ) Depth
  19. Altmetric Badge
    Chapter 18 Quantum Complexity: Some Recent Results, Some Open Problems, Some Thoughts
  20. Altmetric Badge
    Chapter 19 Non-adaptive Complex Group Testing with Multiple Positive Sets
  21. Altmetric Badge
    Chapter 20 How to Cut a Graph into Many Pieces
  22. Altmetric Badge
    Chapter 21 Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet
  23. Altmetric Badge
    Chapter 22 Integer Representations towards Efficient Counting in the Bit Probe Model
  24. Altmetric Badge
    Chapter 23 Closed Left-R.E. Sets
  25. Altmetric Badge
    Chapter 24 $\it \Pi^0_1$ Sets and Tilings
  26. Altmetric Badge
    Chapter 25 Intuitive Probability Logic
  27. Altmetric Badge
    Chapter 26 An Algebraic Characterization of Strictly Piecewise Languages
  28. Altmetric Badge
    Chapter 27 Deterministic Algorithms for Multi-criteria TSP
  29. Altmetric Badge
    Chapter 28 Extending Partial Representations of Interval Graphs
  30. Altmetric Badge
    Chapter 29 Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way
  31. Altmetric Badge
    Chapter 30 The Complexity and Approximability of Minimum Contamination Problems
  32. Altmetric Badge
    Chapter 31 On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric
  33. Altmetric Badge
    Chapter 32 Lower Bounds for Testing Computability by Small Width OBDDs
  34. Altmetric Badge
    Chapter 33 On the Amount of Nonconstructivity in Learning Recursive Functions
  35. Altmetric Badge
    Chapter 34 A Bad Instance for k-Means++
  36. Altmetric Badge
    Chapter 35 Catching a Fast Robber on Interval Graphs
  37. Altmetric Badge
    Chapter 36 Some Tractable Win-Lose Games
  38. Altmetric Badge
    Chapter 37 A Note on Obfuscation for Cryptographic Functionalities of Secret-Operation Then Public-Encryption
  39. Altmetric Badge
    Chapter 38 Grey-Box Steganography
  40. Altmetric Badge
    Chapter 39 Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models
  41. Altmetric Badge
    Chapter 40 The Hardness of Median in the Synchronized Bit Communication Model
  42. Altmetric Badge
    Chapter 41 Lower Bounds for the Smoothed Number of Pareto Optimal Solutions
  43. Altmetric Badge
    Chapter 42 Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands
  44. Altmetric Badge
    Chapter 43 Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects
  45. Altmetric Badge
    Chapter 44 Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
  46. Altmetric Badge
    Chapter 45 Switching to Hedgehog-Free Graphs Is NP-Complete
  47. Altmetric Badge
    Chapter 46 Locally Injective Homomorphism to the Simple Weight Graphs
  48. Altmetric Badge
    Chapter 47 Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
  49. Altmetric Badge
    Chapter 48 Hide-and-Seek: Algorithms for Polygon Walk Problems
  50. Altmetric Badge
    Chapter 49 Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory
  51. Altmetric Badge
    Chapter 50 On the Polynomial Depth of Various Sets of Random Strings
  52. Altmetric Badge
    Chapter 51 Edge Contractions in Subclasses of Chordal Graphs
  53. Altmetric Badge
    Chapter 52 Planarity Testing Revisited
  54. Altmetric Badge
    Chapter 53 Generalized Satisfiability for the Description Logic $\mathcal{ALC}$
Overall attention for this book and its chapters
Altmetric Badge

Mentioned by

twitter
2 X users

Citations

dimensions_citation
1 Dimensions

Readers on

mendeley
1 Mendeley
Summary X Dimensions citations
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Title
Theory and Applications of Models of Computation
Published by
Springer Berlin Heidelberg, April 2011
DOI 10.1007/978-3-642-20877-5
ISBNs
978-3-64-220876-8, 978-3-64-220877-5
Editors

Ogihara, Mitsunori, Tarui, Jun, Ogihara, Mitsunori, Tarui, Jun

View on publisher site
X Demographics

X Demographics

The data shown below were collected from the profiles of 2 X users who shared this research output. Click here to find out more about how the information was compiled.

This page is provided by Altmetric.