↓ Skip to main content

Mathematical Foundations of Computer Science 2012

Overview of attention for book
Cover of 'Mathematical Foundations of Computer Science 2012'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 On the Complexity of Ontological Reasoning under Disjunctive Existential Rules
  3. Altmetric Badge
    Chapter 2 New Races in Parameterized Algorithmics
  4. Altmetric Badge
    Chapter 3 Scott Is Always Simple
  5. Altmetric Badge
    Chapter 4 A Toolkit for Proving Limitations of the Expressive Power of Logics
  6. Altmetric Badge
    Chapter 5 How to Reconstruct a Genome
  7. Altmetric Badge
    Chapter 6 Simple Models for Recursive Schemes
  8. Altmetric Badge
    Chapter 7 Transportation under Nasty Side Constraints
  9. Altmetric Badge
    Chapter 8 Computation of Least Fixed Points
  10. Altmetric Badge
    Chapter 9 Unordered Constraint Satisfaction Games
  11. Altmetric Badge
    Chapter 10 A Polynomial-Time Algorithm for Computing the Maximum Common Subgraph of Outerplanar Graphs of Bounded Degree
  12. Altmetric Badge
    Chapter 11 Reductions to the Set of Random Strings: The Resource-Bounded Case
  13. Altmetric Badge
    Chapter 12 Approximate Graph Isomorphism
  14. Altmetric Badge
    Chapter 13 Near-Optimal Expanding Generator Sets for Solvable Permutation Groups
  15. Altmetric Badge
    Chapter 14 Generating Functions of Timed Languages
  16. Altmetric Badge
    Chapter 15 The Robust Set Problem: Parameterized Complexity and Approximation
  17. Altmetric Badge
    Chapter 16 Mortality for 2 ×2 Matrices Is NP-Hard
  18. Altmetric Badge
    Chapter 17 Solving Counter Parity Games
  19. Altmetric Badge
    Chapter 18 Drawing Planar Graphs on Points Inside a Polygon
  20. Altmetric Badge
    Chapter 19 New Advances in Reoptimizing the Minimum Steiner Tree Problem
  21. Altmetric Badge
    Chapter 20 Smoothed Complexity Theory
  22. Altmetric Badge
    Chapter 21 Abelian Pattern Avoidance in Partial Words
  23. Altmetric Badge
    Chapter 22 The Complexity of Rerouting Shortest Paths
  24. Altmetric Badge
    Chapter 23 Computing with Large Populations Using Interactions
  25. Altmetric Badge
    Chapter 24 Pancake Flipping Is Hard
  26. Altmetric Badge
    Chapter 25 In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses
  27. Altmetric Badge
    Chapter 26 Model Checking Stochastic Branching Processes
  28. Altmetric Badge
    Chapter 27 Parameterized Study of the Test Cover Problem
  29. Altmetric Badge
    Chapter 28 Sitting Closer to Friends Than Enemies, Revisited
  30. Altmetric Badge
    Chapter 29 A Dichotomy Theorem for Homomorphism Polynomials
  31. Altmetric Badge
    Chapter 30 Finite State Transducers for Modular Möbius Number Systems
  32. Altmetric Badge
    Chapter 31 Zero-Knowledge Proofs via Polynomial Representations
  33. Altmetric Badge
    Chapter 32 Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
  34. Altmetric Badge
    Chapter 33 On the Impact of Fair Best Response Dynamics
  35. Altmetric Badge
    Chapter 34 Fast Balanced Partitioning Is Hard Even on Grids and Trees
  36. Altmetric Badge
    Chapter 35 A Characterization of Bispecial Sturmian Words
  37. Altmetric Badge
    Chapter 36 Online Sum-Radii Clustering
  38. Altmetric Badge
    Chapter 37 Observe and Remain Silent (Communication-Less Agent Location Discovery)
  39. Altmetric Badge
    Chapter 38 Mathematical Foundations of Computer Science 2012
  40. Altmetric Badge
    Chapter 39 Strategy Machines and Their Complexity
  41. Altmetric Badge
    Chapter 40 Coloring Graphs Characterized by a Forbidden Subgraph
  42. Altmetric Badge
    Chapter 41 Obtaining Planarity by Contracting Few Edges
  43. Altmetric Badge
    Chapter 42 Light Spanner and Monotone Tree
  44. Altmetric Badge
    Chapter 43 Planarizing Gadgets for Perfect Matching Do Not Exist
  45. Altmetric Badge
    Chapter 44 Kernels for Edge Dominating Set: Simpler or Smaller
  46. Altmetric Badge
    Chapter 45 Categories of Coalgebraic Games
  47. Altmetric Badge
    Chapter 46 Quasi-recognizable vs MSO Definable Languages of One-Dimensional Overlapping Tiles
  48. Altmetric Badge
    Chapter 47 An Improved Approximation Scheme for Variable-Sized Bin Packing
  49. Altmetric Badge
    Chapter 48 Gathering an Even Number of Robots in an Odd Ring without Global Multiplicity Detection
  50. Altmetric Badge
    Chapter 49 Reversal Hierarchies for Small 2DFAs
  51. Altmetric Badge
    Chapter 50 Strictness of the Collapsible Pushdown Hierarchy
  52. Altmetric Badge
    Chapter 51 Computational Complexity of Smooth Differential Equations
  53. Altmetric Badge
    Chapter 52 The Lower Reaches of Circuit Uniformity
  54. Altmetric Badge
    Chapter 53 The Join Levels of the Trotter-Weil Hierarchy Are Decidable
  55. Altmetric Badge
    Chapter 54 Equations X + A = B and (X + X) + C = (X − X) + D over Sets of Natural Numbers
  56. Altmetric Badge
    Chapter 55 Weakly-Synchronized Ground Tree Rewriting
  57. Altmetric Badge
    Chapter 56 Descriptional Complexity of Deterministic Regular Expressions
  58. Altmetric Badge
    Chapter 57 Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs
  59. Altmetric Badge
    Chapter 58 Fine and Wilf’s Theorem and Pseudo-repetitions
  60. Altmetric Badge
    Chapter 59 Taking It to the Limit: Approximate Reasoning for Markov Processes
  61. Altmetric Badge
    Chapter 60 Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games
  62. Altmetric Badge
    Chapter 61 Between Tree Patterns and Conjunctive Queries: Is There Tractability beyond Acyclicity?
  63. Altmetric Badge
    Chapter 62 Reducing a Target Interval to a Few Exact Queries
  64. Altmetric Badge
    Chapter 63 Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs
  65. Altmetric Badge
    Chapter 64 A Finite Basis for ‘Almost Future’ Temporal Logic over the Reals
  66. Altmetric Badge
    Chapter 65 Constructing Premaximal Ternary Square-Free Words of Any Level
  67. Altmetric Badge
    Chapter 66 Regularity Problems for Weak Pushdown ω-Automata and Games
  68. Altmetric Badge
    Chapter 67 Computational Aspects of Cellular Automata on Countable Sofic Shifts
  69. Altmetric Badge
    Chapter 68 Computing Lempel-Ziv Factorization Online
  70. Altmetric Badge
    Chapter 69 On Two Stronger Versions of Dejean’s Conjecture
  71. Altmetric Badge
    Chapter 70 Probabilistic Automata and Probabilistic Logic
  72. Altmetric Badge
    Chapter 71 A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments
Attention for Chapter 12: Approximate Graph Isomorphism
Altmetric Badge

About this Attention Score

  • Average Attention Score compared to outputs of the same age
  • Above-average Attention Score compared to outputs of the same age and source (58th percentile)

Mentioned by

q&a
1 Q&A thread

Citations

dimensions_citation
2 Dimensions

Readers on

mendeley
26 Mendeley
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.
Chapter title
Approximate Graph Isomorphism
Chapter number 12
Book title
Mathematical Foundations of Computer Science 2012
Published in
Lecture notes in computer science, January 2012
DOI 10.1007/978-3-642-32589-2_12
Book ISBNs
978-3-64-232588-5, 978-3-64-232589-2
Authors

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Yadu Vasudev, Johannes Köbler

Editors

Branislav Rovan, Vladimiro Sassone, Peter Widmayer

Mendeley readers

Mendeley readers

The data shown below were compiled from readership statistics for 26 Mendeley readers of this research output. Click here to see the associated Mendeley record.

Geographical breakdown

Country Count As %
United States 2 8%
India 1 4%
Russia 1 4%
Unknown 22 85%

Demographic breakdown

Readers by professional status Count As %
Student > Ph. D. Student 8 31%
Student > Master 4 15%
Researcher 4 15%
Professor > Associate Professor 3 12%
Student > Doctoral Student 2 8%
Other 3 12%
Unknown 2 8%
Readers by discipline Count As %
Computer Science 13 50%
Mathematics 3 12%
Business, Management and Accounting 2 8%
Agricultural and Biological Sciences 1 4%
Sports and Recreations 1 4%
Other 1 4%
Unknown 5 19%
Attention Score in Context

Attention Score in Context

This research output has an Altmetric Attention Score of 3. This is our high-level measure of the quality and quantity of online attention that it has received. This Attention Score, as well as the ranking and number of research outputs shown below, was calculated when the research output was last mentioned on 02 June 2013.
All research outputs
#12,878,328
of 22,714,025 outputs
Outputs from Lecture notes in computer science
#3,774
of 8,124 outputs
Outputs of similar age
#142,992
of 244,168 outputs
Outputs of similar age from Lecture notes in computer science
#196
of 490 outputs
Altmetric has tracked 22,714,025 research outputs across all sources so far. This one is in the 42nd percentile – i.e., 42% of other outputs scored the same or lower than it.
So far Altmetric has tracked 8,124 research outputs from this source. They receive a mean Attention Score of 5.0. This one has gotten more attention than average, scoring higher than 51% of its peers.
Older research outputs will score higher simply because they've had more time to accumulate mentions. To account for age we can compare this Altmetric Attention Score to the 244,168 tracked outputs that were published within six weeks on either side of this one in any source. This one is in the 40th percentile – i.e., 40% of its contemporaries scored the same or lower than it.
We're also able to compare this research output to 490 others from the same source and published within six weeks on either side of this one. This one has gotten more attention than average, scoring higher than 58% of its contemporaries.