On the complexity of computing the measure of ∪[a i ,b i ]
DOI10.1145/359545.359553zbMATH Open0378.68032DBLPjournals/cacm/FredmanW78OpenAlexW2077449861WikidataQ29400574 ScholiaQ29400574MaRDI QIDQ4157950FDOQ4157950
Bruce W. Weide, Michael L. Fredman
Publication date: 1978
Published in: Communications of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/359545.359553
Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99) Real- or complex-valued set functions (28A10)
Cited In (27)
- On the computational complexity of (maximum) shift class scheduling
- Parallel computational geometry of rectangles
- Lower bounds on probabilistic linear decision trees
- Geometric complexity of some location problems
- An improved algorithm for Klee's measure problem on fat boxes
- An in-place algorithm for Klee's measure problem in two dimensions
- Finding Hamiltonian circuits in proper interval graphs
- Periodic assignment and graph colouring
- A (slightly) faster algorithm for Klee's measure problem
- Calculation of Discrepancy Measures and Applications
- On the complexity of finding the convex hull of a set of points
- Minimum node disjoint path covering for circular-arc graphs
- On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination
- Approximate map labeling is in \(\Omega (n\log n)\)
- Comparisons between linear functions can help
- Computing the depth distribution of a set of boxes
- Approximating the volume of unions and intersections of high-dimensional geometric objects
- Visibility maps of segments and triangles in 3D
- Efficient transformations for Klee's measure problem in the streaming model
- An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
- On the computational complexity of (maximum) class scheduling
- License class design: Complexity and algorithms
- An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model
- Klee's measure problem made oblivious
- On optimal cuts of hyperrectangles
- An O(n log n) Manhattan path algorithm
- The inequality-satisfiability problem
This page was built for publication: On the complexity of computing the measure of ∪[a i ,b i ]
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4157950)
