↓ Skip to main content

Algorithms and Computation

Overview of attention for book
Cover of 'Algorithms and Computation'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 An Optimal Algorithm for Tiling the Plane with a Translated Polyomino
  3. Altmetric Badge
    Chapter 2 Adaptive Point Location in Planar Convex Subdivisions
  4. Altmetric Badge
    Chapter 3 Competitive Local Routing with Constraints
  5. Altmetric Badge
    Chapter 4 Navigating Weighted Regions with Scattered Skinny Tetrahedra
  6. Altmetric Badge
    Chapter 5 On the Succinct Representation of Unlabeled Permutations
  7. Altmetric Badge
    Chapter 6 How to Select the Top k Elements from Evolving Data?
  8. Altmetric Badge
    Chapter 7 Optimal Search Trees with 2-Way Comparisons
  9. Altmetric Badge
    Chapter 8 Multidimensional Range Selection
  10. Altmetric Badge
    Chapter 9 On the Minimum Cost Range Assignment Problem
  11. Altmetric Badge
    Chapter 10 On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems
  12. Altmetric Badge
    Chapter 11 General Caching Is Hard: Even with Small Pages
  13. Altmetric Badge
    Chapter 12 The Secretary Problem with a Choice Function
  14. Altmetric Badge
    Chapter 13 The Benefit of Recombination in Noisy Evolutionary Search
  15. Altmetric Badge
    Chapter 14 Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples
  16. Altmetric Badge
    Chapter 15 Obtaining a Triangular Matrix by Independent Row-Column Permutations
  17. Altmetric Badge
    Chapter 16 Many-to-one Matchings with Lower Quotas: Algorithms and Complexity
  18. Altmetric Badge
    Chapter 17 Minimizing the Maximum Moving Cost of Interval Coverage
  19. Altmetric Badge
    Chapter 18 Heuristic Time Hierarchies via Hierarchies for Sampling Distributions
  20. Altmetric Badge
    Chapter 19 Unbounded Discrepancy of Deterministic Random Walks on Grids
  21. Altmetric Badge
    Chapter 20 Trading off Worst and Expected Cost in Decision Tree Problems
  22. Altmetric Badge
    Chapter 21 Sliding Token on Bipartite Permutation Graphs
  23. Altmetric Badge
    Chapter 22 Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width
  24. Altmetric Badge
    Chapter 23 Minimum Degree Up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms
  25. Altmetric Badge
    Chapter 24 Exact and FPT Algorithms for Max-Conflict Free Coloring in Hypergraphs
  26. Altmetric Badge
    Chapter 25 Geometric Matching Algorithms for Two Realistic Terrains
  27. Altmetric Badge
    Chapter 26 Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability
  28. Altmetric Badge
    Chapter 27 The 2-Center Problem in a Simple Polygon
  29. Altmetric Badge
    Chapter 28 Choice Is Hard
  30. Altmetric Badge
    Chapter 29 Fully Dynamic Betweenness Centrality
  31. Altmetric Badge
    Chapter 30 When Patrolmen Become Corrupted: Monitoring a Graph Using Faulty Mobile Robots
  32. Altmetric Badge
    Chapter 31 Cops and Robbers on String Graphs
  33. Altmetric Badge
    Chapter 32 Min-Power Covering Problems
  34. Altmetric Badge
    Chapter 33 Minimizing the Diameter of a Spanning Tree for Imprecise Points
  35. Altmetric Badge
    Chapter 34 Model-Based Classification of Trajectories
  36. Altmetric Badge
    Chapter 35 Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures
  37. Altmetric Badge
    Chapter 36 Unfolding Orthogonal Polyhedra with Linear Refinement
  38. Altmetric Badge
    Chapter 37 Colored Non-crossing Euclidean Steiner Forest
  39. Altmetric Badge
    Chapter 38 On a generalization of Nemhauser and Trotter's local optimization theorem
  40. Altmetric Badge
    Chapter 39 Approximation Algorithms in the Successive Hitting Set Model
  41. Altmetric Badge
    Chapter 40 Generating Random Hyperbolic Graphs in Subquadratic Time
  42. Altmetric Badge
    Chapter 41 Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing
  43. Altmetric Badge
    Chapter 42 Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty
  44. Altmetric Badge
    Chapter 43 An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings
  45. Altmetric Badge
    Chapter 44 Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
  46. Altmetric Badge
    Chapter 45 Algorithms and Computation
  47. Altmetric Badge
    Chapter 46 The VC-Dimension of Visibility on the Boundary of a Simple Polygon
  48. Altmetric Badge
    Chapter 47 Quantum Bit Commitment with Application in Quantum Zero-Knowledge Proof (Extended Abstract)
  49. Altmetric Badge
    Chapter 48 Effectiveness of Structural Restrictions for Hybrid CSPs
  50. Altmetric Badge
    Chapter 49 Polynomial-Time Isomorphism Test of Groups that are Tame Extensions
  51. Altmetric Badge
    Chapter 50 Quantum Algorithm for Triangle Finding in Sparse Graphs
  52. Altmetric Badge
    Chapter 51 On Hardness of the Joint Crossing Number
  53. Altmetric Badge
    Chapter 52 An $$O(n^{\epsilon })$$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
  54. Altmetric Badge
    Chapter 53 Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs
  55. Altmetric Badge
    Chapter 54 Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
  56. Altmetric Badge
    Chapter 55 A New Approximate Min-Max Theorem with Applications in Cryptography
  57. Altmetric Badge
    Chapter 56 Give Me Another One!
  58. Altmetric Badge
    Chapter 57 On the Complexity of Computing Prime Tables
  59. Altmetric Badge
    Chapter 58 Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games
  60. Altmetric Badge
    Chapter 59 Run Generation Revisited: What Goes Up May or May Not Come Down
  61. Altmetric Badge
    Chapter 60 Streaming Verification in Data Analysis
  62. Altmetric Badge
    Chapter 61 All-Around Near-Optimal Solutions for the Online Bin Packing Problem
  63. Altmetric Badge
    Chapter 62 Serving Online Requests with Mobile Servers
  64. Altmetric Badge
    Chapter 63 An In-place Framework for Exact and Approximate Shortest Unique Substring Queries
  65. Altmetric Badge
    Chapter 64 Inferring Strings from Full Abelian Periods
  66. Altmetric Badge
    Chapter 65 Toehold DNA Languages are Regular (Extended Abstract)
Attention for Chapter 31: Cops and Robbers on String Graphs
Altmetric Badge

Readers on

mendeley
9 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
Cops and Robbers on String Graphs
Chapter number 31
Book title
Algorithms and Computation
Published by
Springer, Berlin, Heidelberg, December 2015
DOI 10.1007/978-3-662-48971-0_31
Book ISBNs
978-3-66-248970-3, 978-3-66-248971-0
Authors

Tomáš Gavenčiak, Przemysław Gordinowicz, Vít Jelínek, Pavel Klavík, Jan Kratochvíl

Mendeley readers

Mendeley readers

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

Geographical breakdown

Country Count As %
Unknown 9 100%

Demographic breakdown

Readers by professional status Count As %
Student > Ph. D. Student 3 33%
Student > Master 2 22%
Researcher 2 22%
Student > Bachelor 1 11%
Unknown 1 11%
Readers by discipline Count As %
Computer Science 6 67%
Mathematics 2 22%
Unknown 1 11%