loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
1996 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '96)
Optimal overlap representations
Beijing, CHINA
June 12-June 14
ISBN: 0-8186-7460-1
ASCII Text
x 
 
Lin Chen, "Optimal overlap representations," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 8, 1996 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '96), 1996.
 
 
BibTex
x
 
@article{ 10.1109/ISPAN.1996.508954,
author = {Lin Chen},
title = {Optimal overlap representations},
journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on},
volume = {0},
year = {1996},
issn = {1087-4089},
pages = {8},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.1996.508954},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel Architectures, Algorithms, and Networks, International Symposium on
TI - Optimal overlap representations
SN - 1087-4089
SP
EP
A1 - Lin Chen,
PY - 1996
KW - computational complexity; computational geometry; parallel algorithms; optimal overlap representations; minimal interval; circular arc overlap representations; optimal algorithms; minimal interval overlap representation; EREW PRAM processors; common CRCW PRAM; BSR processors
VL - 0
JA - Parallel Architectures, Algorithms, and Networks, International Symposium on
ER -
 
Lin Chen, FRL, Los Angeles, CA, USA
In this paper, we investigate the problem of computing minimal interval and circular arc overlap representations, and give several optimal algorithms. We show that, among other things, given an s/spl times/t interval or circular arc overlap representation matrix: a minimal interval overlap representation can be obtained with O(log(st)) time with O(st/log(st)) EREW PRAM processors, or in O(log t/log log t) time with O(st log log t/log t) common CRCW PRAM processors, or in O(1) time with O(st) BSR processors; a minimal circular arc overlap representation can be obtained in O(st) time.
Index Terms:
computational complexity; computational geometry; parallel algorithms; optimal overlap representations; minimal interval; circular arc overlap representations; optimal algorithms; minimal interval overlap representation; EREW PRAM processors; common CRCW PRAM; BSR processors
Citation:
Lin Chen, "Optimal overlap representations," ispan, pp.8, 1996 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '96), 1996
Usage of this product signifies your acceptance of the Terms of Use.