↓ Skip to main content

Algorithms – ESA 2006

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

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 Origami, Linkages, and Polyhedra: Folding with Algorithms
  3. Altmetric Badge
    Chapter 2 Reliable and Efficient Geometric Computing
  4. Altmetric Badge
    Chapter 3 Some Computational Challenges in Today’s Bio-medicine
  5. Altmetric Badge
    Chapter 4 Kinetic Collision Detection for Convex Fat Objects
  6. Altmetric Badge
    Chapter 5 Dynamic Connectivity for Axis-Parallel Rectangles
  7. Altmetric Badge
    Chapter 6 Algorithms – ESA 2006
  8. Altmetric Badge
    Chapter 7 Cooperative TSP
  9. Altmetric Badge
    Chapter 8 Fréchet Distance for Curves, Revisited
  10. Altmetric Badge
    Chapter 9 Resource Allocation in Bounded Degree Trees
  11. Altmetric Badge
    Chapter 10 Dynamic Algorithms for Graph Spanners
  12. Altmetric Badge
    Chapter 11 Latency Constrained Aggregation in Sensor Networks
  13. Altmetric Badge
    Chapter 12 Competitive Analysis of Flash-Memory Algorithms
  14. Altmetric Badge
    Chapter 13 Contention Resolution with Heterogeneous Job Sizes
  15. Altmetric Badge
    Chapter 14 Deciding Relaxed Two-Colorability—A Hardness Jump
  16. Altmetric Badge
    Chapter 15 Negative Examples for Sequential Importance Sampling of Binary Contingency Tables
  17. Altmetric Badge
    Chapter 16 Estimating Entropy over Data Streams
  18. Altmetric Badge
    Chapter 17 Necklaces, Convolutions, and X + Y
  19. Altmetric Badge
    Chapter 18 Purely Functional Worst Case Constant Time Catenable Sorted Lists
  20. Altmetric Badge
    Chapter 19 Taxes for Linear Atomic Congestion Games
  21. Altmetric Badge
    Chapter 20 Spanners with Slack
  22. Altmetric Badge
    Chapter 21 Compressed Indexes for Approximate String Matching
  23. Altmetric Badge
    Chapter 22 Traversing the Machining Graph
  24. Altmetric Badge
    Chapter 23 Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
  25. Altmetric Badge
    Chapter 24 Distributed Almost Exact Approximations for Minor-Closed Families
  26. Altmetric Badge
    Chapter 25 Spectral Clustering by Recursive Partitioning
  27. Altmetric Badge
    Chapter 26 Finite Termination of “Augmenting Path” Algorithms in the Presence of Irrational Problem Data
  28. Altmetric Badge
    Chapter 27 Dynamic Programming and Fast Matrix Multiplication
  29. Altmetric Badge
    Chapter 28 Near-Entropy Hotlink Assignments
  30. Altmetric Badge
    Chapter 29 Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods
  31. Altmetric Badge
    Chapter 30 Finding Total Unimodularity in Optimization Problems Solved by Linear Programs
  32. Altmetric Badge
    Chapter 31 Preemptive Online Scheduling: Optimal Algorithms for All Speeds
  33. Altmetric Badge
    Chapter 32 On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
  34. Altmetric Badge
    Chapter 33 Lower and Upper Bounds on FIFO Buffer Management in QoS Switches
  35. Altmetric Badge
    Chapter 34 Graph Coloring with Rejection
  36. Altmetric Badge
    Chapter 35 A Doubling Dimension Threshold Θ(loglogn) for Augmented Graph Navigability
  37. Altmetric Badge
    Chapter 36 Violator Spaces: Structure and Algorithms
  38. Altmetric Badge
    Chapter 37 Region-Restricted Clustering for Geographic Data Mining
  39. Altmetric Badge
    Chapter 38 An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths
  40. Altmetric Badge
    Chapter 39 Algorithms – ESA 2006
  41. Altmetric Badge
    Chapter 40 Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold
  42. Altmetric Badge
    Chapter 41 Enumerating Spanning and Connected Subsets in Graphs and Matroids
  43. Altmetric Badge
    Chapter 42 Less Hashing, Same Performance: Building a Better Bloom Filter
  44. Altmetric Badge
    Chapter 43 A Unified Approach to Approximating Partial Covering Problems
  45. Altmetric Badge
    Chapter 44 Navigating Low-Dimensional and Hierarchical Population Networks
  46. Altmetric Badge
    Chapter 45 Algorithms – ESA 2006
  47. Altmetric Badge
    Chapter 46 Inner-Product Based Wavelet Synopses for Range-Sum Queries
  48. Altmetric Badge
    Chapter 47 Approximation in Preemptive Stochastic Online Scheduling
  49. Altmetric Badge
    Chapter 48 Greedy in Approximation Algorithms
  50. Altmetric Badge
    Chapter 49 I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths
  51. Altmetric Badge
    Chapter 50 Stochastic Shortest Paths Via Quasi-convex Maximization
  52. Altmetric Badge
    Chapter 51 Path Hitting in Acyclic Graphs
  53. Altmetric Badge
    Chapter 52 Minimum Transversals in Posi-modular Systems
  54. Altmetric Badge
    Chapter 53 An LP-Designed Algorithm for Constraint Satisfaction
  55. Altmetric Badge
    Chapter 54 Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing
  56. Altmetric Badge
    Chapter 55 Balancing Applied to Maximum Network Flow Problems
  57. Altmetric Badge
    Chapter 56 Algorithms – ESA 2006
  58. Altmetric Badge
    Chapter 57 Kinetic Algorithms Via Self-adjusting Computation
  59. Altmetric Badge
    Chapter 58 Parallel Machine Scheduling Through Column Generation: Minimax Objective Functions
  60. Altmetric Badge
    Chapter 59 Reporting Flock Patterns
  61. Altmetric Badge
    Chapter 60 On Exact Algorithms for Treewidth
  62. Altmetric Badge
    Chapter 61 An Improved Construction for Counting Bloom Filters
  63. Altmetric Badge
    Chapter 62 An MINLP Solution Method for a Water Network Problem
  64. Altmetric Badge
    Chapter 63 Skewed Binary Search Trees
  65. Altmetric Badge
    Chapter 64 Algorithmic Aspects of Proportional Symbol Maps
  66. Altmetric Badge
    Chapter 65 Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?
  67. Altmetric Badge
    Chapter 66 Multiline Addressing by Network Flow
  68. Altmetric Badge
    Chapter 67 The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression
  69. Altmetric Badge
    Chapter 68 The Price of Resiliency: A Case Study on Sorting with Memory Faults
  70. Altmetric Badge
    Chapter 69 How Branch Mispredictions Affect Quicksort
  71. Altmetric Badge
    Chapter 70 Robust, Generic and Efficient Construction of Envelopes of Surfaces in Three-Dimensional Spaces
  72. Altmetric Badge
    Chapter 71 Engineering Highway Hierarchies
  73. Altmetric Badge
    Chapter 72 Univariate Polynomial Real Root Isolation: Continued Fractions Revisited
  74. Altmetric Badge
    Chapter 73 Exact and Efficient Construction of Planar Minkowski Sums Using the Convolution Method
Attention for Chapter 30: Finding Total Unimodularity in Optimization Problems Solved by Linear Programs
Altmetric Badge

Readers on

citeulike
1 CiteULike
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
Finding Total Unimodularity in Optimization Problems Solved by Linear Programs
Chapter number 30
Book title
Algorithms – ESA 2006
Published by
Springer Berlin Heidelberg, January 2006
DOI 10.1007/11841036_30
Book ISBNs
978-3-54-038875-3, 978-3-54-038876-0
Authors

Christoph Dürr, Mathilde Hurand

Editors

Yossi Azar, Thomas Erlebach