Abstract
We investigate some properties of minimal interval and circular arc representations and give several optimal parallel recognition and construction algorithms. We show that, among other things, given an s × t interval or circular arc representation matrix,
-
deciding if the representation is minimal can be done in O(log s) time with O(st/log s) EREW PRAM processors, or in O(1) time with O(st) Common CRCW PRAM processors;
-
constructing a minimum interval representation can be done in 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.
Chapter PDF
Keywords
- Intersection Point
- Intersection Graph
- Left Endpoint
- Interval Representation
- Parallel Random Access Machine
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
F. Abolhassan, R. Drefenstedt, J. Keller, W. J. Paul, and D. Scheerer. On the physical design of PRAMs. Computer Journal, 36(8):756–762, December 1993.
S. G. Akl and G. R. Guenther. Broadcasting with selective reduction. In G. X. Ritter, editor, Proceedings, 11th IFIP World Computer Congress, pages 515–520, 1989. North-Holland.
P. W. Beame and J. Hastad. Optimal bounds for decision problems on the CRCW PRAM. Journal of the ACM, 36(3):643–670, July 1989.
S. Benzer. On the topology of the genetic fine structure. Proceedings, Nat. Acad. Sci., 45:1607–1620, 1959.
R. P. Brent. The parallel evaluation of general arithmetic expressions. Journal of the ACM, 21:201–208, 1974.
L. Chen. Efficient parallel algorithms for several intersection graphs. In Proceedings, 22nd Int'l Symp. on Circuits and Systems, pages 973–976. IEEE, 1989.
L. Chen. Efficient deterministic parallel algorithms for integer sorting. In S. G. Akl, F. Fiala, and W. W. Koczkodaj, editors, Proc. International Conference on Computing and Information, Lecture Notes in Computer Science, Vol. 468, pages 433–442. Springer-Verlag, 1990.
L. Chen. Optimal parallel time bounds for the maximum clique problem on intervals. Information Processing Letters, 42(4):197–201, June 1992.
L. Chen. Efficient parallel recognition of some circular arc graphs, I. Algorithmica, 9(3):217–238, March 1993.
L. Chen. Revisiting circular arc graphs. In D.-Z. Du and X.-S. Zhang, editors, Proceedings, 5th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 834, pages 559–566. Springer-Verlag, 1994.
R. Cole and U. Vishkin. Faster optimal parallel prefix sums and list ranking. Information and Computation, 81(3):334–352, June 1989.
S. A. Cook, C. Dwork, and R. Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM Journal on Computing, 15(1):87–97, 1986.
F. E. Fich, P. L. Ragde, and A. Wigderson. Relations between concurrent-write models of parallel computation. In Proc. 3rd ACM Symp. on Principles of Distributed Computing, pages 179–189. Association for Computing Machinery, 1984.
M. Goldberg and T. Spencer. Constructing a maximal independent set in parallel. SIAM J. on Discr. Math., 2(3):322–328, August 1989.
U. I. Gupta, D. T. Lee, and J. Y.-T. Leung. Efficient algorithms for interval graphs and circular-arc graphs. Networks, 12:459–467, 1982.
J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, 1990.
R. E. Ladner and M. J. Fischer. Parallel prefix computation. Journal of the ACM, 27(4):831–838, October 1980.
L. F. Lindon and S. G. Akl. An optimal implementation of broadcasting with selective reduction. IEEE Transactions on Parallel and Distributed Systems, 4(3):256–269, March 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, L. (1995). Optimal circular arc representations. In: Haridi, S., Ali, K., Magnusson, P. (eds) EURO-PAR '95 Parallel Processing. Euro-Par 1995. Lecture Notes in Computer Science, vol 966. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0020470
Download citation
DOI: https://doi.org/10.1007/BFb0020470
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60247-7
Online ISBN: 978-3-540-44769-6
eBook Packages: Springer Book Archive