Complexity Links Between Matrix Multiplication, Klee's Measure and Call Access Control for Satellite Constellations
Overview & Synopsis
We study the complexity of computing the maximum load of weighted rectangles (the load on a point is defined as the sum of the weights of intersecting rectangles on this point). We relate the complexity of the dynamic version of this problem (in which we want to perform insert/delete operations on the rectangles) to the complexity of the matrix multiplication problem in the \maxplus\ algebra. In particular, we show that a significant improvemen- t on the existing solutions for the first one (within $O(n^\theta/2$) per insertion/extraction with $\theta
Indexed from repository: HAL Open Science
(
hal.science)
Keyboard Shortcuts:
← / → for pages • + / - for zoom • 0 to fit width
Powered by Mozilla PDF.js v3.11
Document Information
| Document Title | Complexity Links Between Matrix Multiplication, Klee's Measure and Call Access Control for Satellite Constellations |
|---|---|
| Author / Organization | Jérôme Galtier, Paolo Penna |
| Subject & Discipline | Multidisciplinary Academic Open Research |
| Categories | Science & Mathematics |
| Publication Year | 2001 |
| License / Rights | Open Access / Creative Commons |
| Resource Verification | Listed PDF (Verification Pending) |
| Original Host Website |
HAL Open Science
(hal.science)
|
| File Format | application/pdf (Portable Document Format) |
| Language | EN |
| Catalog ID | DOC-80882 |
| Original Source Link | Visit Source Page on hal.science » |