Algorithms and computation : 18th international symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007 : proceedings

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Algorithms and Computation
3. Altmetric Badge
   Chapter 2 Coloring Triangle-Free Graphs on Surfaces
4. Altmetric Badge
   Chapter 3 Integer Representation and Counting in the Bit Probe Model
5. Altmetric Badge
   Chapter 4 Minimum Degree Orderings
6. Altmetric Badge
   Chapter 5 Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs
7. Altmetric Badge
   Chapter 6 Dynamic Distance Hereditary Graphs Using Split Decomposition
8. Altmetric Badge
   Chapter 7 Unifying Two Graph Decompositions with Modular Decomposition
9. Altmetric Badge
   Chapter 8 Escaping Off-Line Searchers and a Discrete Isoperimetric Theorem
10. Altmetric Badge
    Chapter 9 Geometric Spanner of Segments
11. Altmetric Badge
    Chapter 10 Dilation-Optimal Edge Deletion in Polygonal Cycles
12. Altmetric Badge
    Chapter 11 Unbounded-Error Classical and Quantum Communication Complexity
13. Altmetric Badge
    Chapter 12 A Spectral Method for MAX2SAT in the Planted Solution Model
14. Altmetric Badge
    Chapter 13 On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
15. Altmetric Badge
    Chapter 14 The 1-Versus-2 Queries Problem Revisited
16. Altmetric Badge
    Chapter 15 Approximating the Crossing Number of Toroidal Graphs
17. Altmetric Badge
    Chapter 16 Width-Optimal Visibility Representations of Plane Graphs
18. Altmetric Badge
    Chapter 17 Computing Upward Topological Book Embeddings of Upward Planar Digraphs
19. Altmetric Badge
    Chapter 18 Algorithms for the Hypergraph and the Minor Crossing Number Problems
20. Altmetric Badge
    Chapter 19 On Mixing and Edge Expansion Properties in Randomized Broadcasting
21. Altmetric Badge
    Chapter 20 Linear Reconfiguration of Cube-Style Modular Robots
22. Altmetric Badge
    Chapter 21 Fast Message Dissemination in Random Geometric Ad-Hoc Radio Networks
23. Altmetric Badge
    Chapter 22 Sensor Network Gossiping or How to Break the Broadcast Lower Bound
24. Altmetric Badge
    Chapter 23 On the Complexity of the “Most General” Undirected Firing Squad Synchronization Problem
25. Altmetric Badge
    Chapter 24 Capacitated Domination Problem
26. Altmetric Badge
    Chapter 25 The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
27. Altmetric Badge
    Chapter 26 New Bounds for the Nearly Equitable Edge Coloring Problem
28. Altmetric Badge
    Chapter 27 Approximation to the Minimum Cost Edge Installation Problem
29. Altmetric Badge
    Chapter 28 Approximability of Packing Disjoint Cycles
30. Altmetric Badge
    Chapter 29 Succinct Representation of Labeled Graphs
31. Altmetric Badge
    Chapter 30 More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding
32. Altmetric Badge
    Chapter 31 Kinetic Maintenance of Mobile k-Centres on Trees
33. Altmetric Badge
    Chapter 32 Checking Value-Sensitive Data Structures in Sublinear Space
34. Altmetric Badge
    Chapter 33 Manipulation in Games
35. Altmetric Badge
    Chapter 34 Using Nash Implementation to Achieve Better Frugality Ratios
36. Altmetric Badge
    Chapter 35 The Price of Nash Equilibria in Multicast Transmissions Games
37. Altmetric Badge
    Chapter 36 An Efficient Algorithm for Enumerating Pseudo Cliques
38. Altmetric Badge
    Chapter 37 Fast Adaptive Diagnosis with a Minimum Number of Tests
39. Altmetric Badge
    Chapter 38 Dynamic Structures for Top-k Queries on Uncertain Data
40. Altmetric Badge
    Chapter 39 Separating Populations with Wide Data: A Spectral Analysis
41. Altmetric Badge
    Chapter 40 A Constant-Competitive Algorithm for Online OVSF Code Assignment
42. Altmetric Badge
    Chapter 41 Average-Case Analysis of Online Topological Ordering
43. Altmetric Badge
    Chapter 42 Energy Efficient Deadline Scheduling in Two Processor Systems
44. Altmetric Badge
    Chapter 43 On the Relative Dominance of Paging Algorithms
45. Altmetric Badge
    Chapter 44 I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions
46. Altmetric Badge
    Chapter 45 Geometric Streaming Algorithms with a Sorting Primitive
47. Altmetric Badge
    Chapter 46 External Memory Range Reporting on a Grid
48. Altmetric Badge
    Chapter 47 Approximate Range Searching in External Memory
49. Altmetric Badge
    Chapter 48 Faster Treasure Hunt and Better Strongly Universal Exploration Sequences
50. Altmetric Badge
    Chapter 49 Hardness and Approximation of Traffic Grooming
51. Altmetric Badge
    Chapter 50 Depth of Field and Cautious-Greedy Routing in Social Networks
52. Altmetric Badge
    Chapter 51 Locating Facilities on a Network to Minimize Their Average Service Radius
53. Altmetric Badge
    Chapter 52 Faster Combinatorial Algorithms for Determinant and Pfaffian
54. Altmetric Badge
    Chapter 53 A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria Optimization
55. Altmetric Badge
    Chapter 54 The Parameterized Complexity of the Unique Coverage Problem
56. Altmetric Badge
    Chapter 55 Bounded Tree-Width and CSP-Related Problems
57. Altmetric Badge
    Chapter 56 Covering Points by Unit Disks of Fixed Location
58. Altmetric Badge
    Chapter 57 Geodesic Disks and Clustering in a Simple Polygon
59. Altmetric Badge
    Chapter 58 An O(n 2logn) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane
60. Altmetric Badge
    Chapter 59 Optimal Triangulation with Steiner Points
61. Altmetric Badge
    Chapter 60 New Algorithm for Field Splitting in Radiation Therapy
62. Altmetric Badge
    Chapter 61 In-Place Algorithm for Image Rotation
63. Altmetric Badge
    Chapter 62 Higher Order Voronoi Diagrams of Segments for VLSI Critical Area Extraction
64. Altmetric Badge
    Chapter 63 Distributed Relationship Schemes for Trees
65. Altmetric Badge
    Chapter 64 Fast Evaluation of Union-Intersection Expressions
66. Altmetric Badge
    Chapter 65 A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem
67. Altmetric Badge
    Chapter 66 Compressing Spatio-temporal Trajectories
68. Altmetric Badge
    Chapter 67 Finding Popular Places
69. Altmetric Badge
    Chapter 68 Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations
70. Altmetric Badge
    Chapter 69 The Monomial Ideal Membership Problem and Polynomial Identity Testing
71. Altmetric Badge
    Chapter 70 On the Fault Testing for Reversible Circuits
72. Altmetric Badge
    Chapter 71 The Space Complexity of k-Tree Isomorphism
73. Altmetric Badge
    Chapter 72 Algorithms for Computing the Length-Constrained Max-Score Segments with Applications to DNA Copy Number Data Analysis
74. Altmetric Badge
    Chapter 73 Space Efficient Indexes for String Matching with Don’t Cares
75. Altmetric Badge
    Chapter 74 2-Stage Fault Tolerant Interval Group Testing
76. Altmetric Badge
    Chapter 75 Approximate String Matching with Swap and Mismatch
77. Altmetric Badge
    Chapter 76 Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
78. Altmetric Badge
    Chapter 77 Weighted Treewidth Algorithmic Techniques and Results
79. Altmetric Badge
    Chapter 78 Spanning Trees with Many Leaves in Regular Bipartite Graphs
80. Altmetric Badge
    Chapter 79 Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs