Abstract
Starting from a permutation of {0, ..., n−1} we compute in parallel with a workload of O(n log n) a compact data structure of size O(n log n). This data structure allows to obtain the associated permutation graph and the transitive closure and reduction of the associated order of dimension 2 efficiently. The parallel algorithms obtained have a workload of O(m+n log n) where m is the number of edges of the permutation graph. They run in time O(log2 n) on a CREW PRAM.
The authors are supported by PROCOPE.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
K.A. Baker, P.C. Fishburn, and F.S. Roberts. Partial orders of dimension 2. Networks, 2:11–28, 1971.
C.J. Colbourn. On testing isomorphism of permutation graphs. Networks, 11:13–21, 1981.
Richard Cole. Parallel merge sort. SIAM J. Comput., 17(4), august 1988.
Paul F. Dietz. Optimal algorithms for list indexing and subset rank. In Algorithms and data structures, Proc. workshop WADS '89, Ottawa/Canada, number 382 in Lect. Notes Comput. Sci., pages 39–86, 1989.
M. Fredman and M. Saks. The cell probe complexity of dynamic data structures. In 21st ACM STOC, pages 345–354, 1989.
M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1985.
A. Pnueli, A. Lempel, and W. Even. Transitive orientation of graphs and identification. Canad. J. Math., 23:160–175, 1971.
J. Spinrad and J. Valdes. Recognition and isomorphism of two dimensional partial oreders. In 10th Coll. on Automata, Language and Programming, number 154 in Lect. Notes Comput. Sci., pages 676–686, Berlin, 1983. Springer.
Jeremy Spinrad. Dimension and algorithms. In V. Bouchité and M. Morvan, editors, Orders, Algorithms, and Applications, number 831 in Lect. Notes Comput. Sci., pages 33–52. Springer-Verlag, 1994.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gustedt, J., Morvan, M., Viennot, L. (1995). A compact data structure and parallel algorithms for permutation graphs. In: Nagl, M. (eds) Graph-Theoretic Concepts in Computer Science. WG 1995. Lecture Notes in Computer Science, vol 1017. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60618-1_89
Download citation
DOI: https://doi.org/10.1007/3-540-60618-1_89
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60618-5
Online ISBN: 978-3-540-48487-5
eBook Packages: Springer Book Archive