↓ Skip to main content

Algorithms – ESA 2005

Overview of attention for book
Cover of 'Algorithms – ESA 2005'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 Designing Reliable Algorithms in Unreliable Memories
  3. Altmetric Badge
    Chapter 2 From Balanced Graph Partitioning to Balanced Metric Labeling
  4. Altmetric Badge
    Chapter 3 Fearful Symmetries: Quantum Computing, Factoring, and Graph Isomorphism
  5. Altmetric Badge
    Chapter 4 Exploring an Unknown Graph Efficiently
  6. Altmetric Badge
    Chapter 5 Online Routing in Faulty Meshes with Sub-linear Comparative Time and Traffic Ratio
  7. Altmetric Badge
    Chapter 6 Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut
  8. Altmetric Badge
    Chapter 7 Relax-and-Cut for Capacitated Network Design
  9. Altmetric Badge
    Chapter 8 On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games,,
  10. Altmetric Badge
    Chapter 9 The Complexity of Games on Highly Regular Graphs
  11. Altmetric Badge
    Chapter 10 Computing Equilibrium Prices: Does Theory Meet Practice?
  12. Altmetric Badge
    Chapter 11 Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions
  13. Altmetric Badge
    Chapter 12 An Algorithm for the SAT Problem for Formulae of Linear Length
  14. Altmetric Badge
    Chapter 13 Linear-Time Enumeration of Isolated Cliques
  15. Altmetric Badge
    Chapter 14 Finding Shortest Non-separating and Non-contractible Cycles for Topologically Embedded Graphs
  16. Altmetric Badge
    Chapter 15 Delineating Boundaries for Imprecise Regions
  17. Altmetric Badge
    Chapter 16 Exacus : Efficient and Exact Algorithms for Curves and Surfaces
  18. Altmetric Badge
    Chapter 17 Min Sum Clustering with Penalties
  19. Altmetric Badge
    Chapter 18 Improved Approximation Algorithms for Metric Max TSP
  20. Altmetric Badge
    Chapter 19 Unbalanced Graph Cuts
  21. Altmetric Badge
    Chapter 20 Low Degree Connectivity in Ad-Hoc Networks
  22. Altmetric Badge
    Chapter 21 5-Regular Graphs are 3-Colorable with Positive Probability
  23. Altmetric Badge
    Chapter 22 Optimal Integer Alphabetic Trees in Linear Time
  24. Altmetric Badge
    Chapter 23 Predecessor Queries in Constant Time?
  25. Altmetric Badge
    Chapter 24 An Algorithm for Node-Capacitated Ring Routing
  26. Altmetric Badge
    Chapter 25 On Degree Constrained Shortest Paths
  27. Altmetric Badge
    Chapter 26 A New Template for Solving p -Median Problems for Trees in Sub-quadratic Time
  28. Altmetric Badge
    Chapter 27 Roll Cutting in the Curtain Industry
  29. Altmetric Badge
    Chapter 28 Space Efficient Algorithms for the Burrows-Wheeler Backtransformation
  30. Altmetric Badge
    Chapter 29 Cache-Oblivious Comparison-Based Algorithms on Multisets
  31. Altmetric Badge
    Chapter 30 Oblivious vs. Distribution-Based Sorting: An Experimental Evaluation
  32. Altmetric Badge
    Chapter 31 Allocating Memory in a Lock-Free Manner
  33. Altmetric Badge
    Chapter 32 Generating Realistic Terrains with Higher-Order Delaunay Triangulations
  34. Altmetric Badge
    Chapter 33 Algorithms – ESA 2005
  35. Altmetric Badge
    Chapter 34 Convex Hull and Voronoi Diagram of Additively Weighted Points
  36. Altmetric Badge
    Chapter 35 New Tools and Simpler Algorithms for Branchwidth
  37. Altmetric Badge
    Chapter 36 Treewidth Lower Bounds with Brambles
  38. Altmetric Badge
    Chapter 37 Minimal Interval Completions
  39. Altmetric Badge
    Chapter 38 A 2-Approximation Algorithm for Sorting by Prefix Reversals
  40. Altmetric Badge
    Chapter 39 Approximating the 2-Interval Pattern Problem
  41. Altmetric Badge
    Chapter 40 A Loopless Gray Code for Minimal Signed-Binary Representations
  42. Altmetric Badge
    Chapter 41 Efficient Approximation Schemes for Geometric Problems?
  43. Altmetric Badge
    Chapter 42 Geometric Clustering to Minimize the Sum of Cluster Sizes
  44. Altmetric Badge
    Chapter 43 Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs
  45. Altmetric Badge
    Chapter 44 Packet Routing and Information Gathering in Lines, Rings and Trees
  46. Altmetric Badge
    Chapter 45 Jitter Regulation for Multiple Streams
  47. Altmetric Badge
    Chapter 46 Efficient c -Oriented Range Searching with DOP-Trees
  48. Altmetric Badge
    Chapter 47 Matching Point Sets with Respect to the Earth Mover’s Distance
  49. Altmetric Badge
    Chapter 48 Small Stretch Spanners on Dynamic Graphs
  50. Altmetric Badge
    Chapter 49 An Experimental Study of Algorithms for Fully Dynamic Transitive Closure
  51. Altmetric Badge
    Chapter 50 Experimental Study of Geometric t -Spanners
  52. Altmetric Badge
    Chapter 51 Highway Hierarchies Hasten Exact Shortest Path Queries
  53. Altmetric Badge
    Chapter 52 Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delays
  54. Altmetric Badge
    Chapter 53 Fairness-Free Periodic Scheduling with Vacations
  55. Altmetric Badge
    Chapter 54 Online Bin Packing with Cardinality Constraints
  56. Altmetric Badge
    Chapter 55 Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines
  57. Altmetric Badge
    Chapter 56 Engineering Planar Separator Algorithms
  58. Altmetric Badge
    Chapter 57 Stxxl : Standard Template Library for XXL Data Sets
  59. Altmetric Badge
    Chapter 58 Negative Cycle Detection Problem
  60. Altmetric Badge
    Chapter 59 An Optimal Algorithm for Querying Priced Information: Monotone Boolean Functions and Game Trees
  61. Altmetric Badge
    Chapter 60 Algorithms – ESA 2005
  62. Altmetric Badge
    Chapter 61 Online Primal-Dual Algorithms for Covering and Packing Problems
  63. Altmetric Badge
    Chapter 62 Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information
  64. Altmetric Badge
    Chapter 63 Using Fractional Primal-Dual to Schedule Split Intervals with Demands
  65. Altmetric Badge
    Chapter 64 An Approximation Algorithm for the Minimum Latency Set Cover Problem
  66. Altmetric Badge
    Chapter 65 Workload-Optimal Histograms on Streams
  67. Altmetric Badge
    Chapter 66 Finding Frequent Patterns in a String in Sublinear Time
  68. Altmetric Badge
    Chapter 67 Online Occlusion Culling
  69. Altmetric Badge
    Chapter 68 Shortest Paths in Matrix Multiplication Time
  70. Altmetric Badge
    Chapter 69 Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs
  71. Altmetric Badge
    Chapter 70 Greedy Routing in Tree-Decomposed Graphs
  72. Altmetric Badge
    Chapter 71 Making Chord Robust to Byzantine Attacks
  73. Altmetric Badge
    Chapter 72 Bucket Game with Applications to Set Multicover and Dynamic Page Migration
  74. Altmetric Badge
    Chapter 73 Bootstrapping a Hop-Optimal Network in the Weak Sensor Model
  75. Altmetric Badge
    Chapter 74 Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs
  76. Altmetric Badge
    Chapter 75 A Cutting Planes Algorithm Based Upon a Semidefinite Relaxation for the Quadratic Assignment Problem
  77. Altmetric Badge
    Chapter 76 Approximation Complexity of min-max (Regret) Versions of Shortest Path, Spanning Tree, and Knapsack
  78. Altmetric Badge
    Chapter 77 Robust Approximate Zeros
  79. Altmetric Badge
    Chapter 78 Optimizing a 2D Function Satisfying Unimodality Properties
Attention for Chapter 11: Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions
Altmetric Badge

Mentioned by

wikipedia
7 Wikipedia pages

Readers on

mendeley
5 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
Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions
Chapter number 11
Book title
Algorithms – ESA 2005
Published by
Springer Berlin Heidelberg, October 2005
DOI 10.1007/11561071_11
Book ISBNs
978-3-54-029118-3, 978-3-54-031951-1
Authors

Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender, Fedor V. Fomin, Dorn, Frederic, Penninkx, Eelko, Bodlaender, Hans L., Fomin, Fedor V.

Mendeley readers

Mendeley readers

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

Geographical breakdown

Country Count As %
Colombia 1 20%
Unknown 4 80%

Demographic breakdown

Readers by professional status Count As %
Other 1 20%
Student > Bachelor 1 20%
Student > Ph. D. Student 1 20%
Professor > Associate Professor 1 20%
Student > Postgraduate 1 20%
Other 0 0%
Readers by discipline Count As %
Computer Science 3 60%
Physics and Astronomy 1 20%
Chemistry 1 20%