@article{ITA_1987__21_2_181_0, author = {Bordat, J. P.}, title = {Complexit\'e de probl\`emes li\'es aux graphes sans circuit}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {181--197}, publisher = {EDP-Sciences}, volume = {21}, number = {2}, year = {1987}, mrnumber = {894710}, zbl = {0634.68031}, language = {fr}, url = {http://archive.numdam.org/item/ITA_1987__21_2_181_0/} }
TY - JOUR AU - Bordat, J. P. TI - Complexité de problèmes liés aux graphes sans circuit JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 1987 SP - 181 EP - 197 VL - 21 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/item/ITA_1987__21_2_181_0/ LA - fr ID - ITA_1987__21_2_181_0 ER -
%0 Journal Article %A Bordat, J. P. %T Complexité de problèmes liés aux graphes sans circuit %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1987 %P 181-197 %V 21 %N 2 %I EDP-Sciences %U http://archive.numdam.org/item/ITA_1987__21_2_181_0/ %G fr %F ITA_1987__21_2_181_0
Bordat, J. P. Complexité de problèmes liés aux graphes sans circuit. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 21 (1987) no. 2, pp. 181-197. http://archive.numdam.org/item/ITA_1987__21_2_181_0/
1. The Transitive Reduction of a Directed Graph, S.I.A.M. J. Comput., vol. 1, n° 2, juin, 1972, p. 131-137. | MR | Zbl
, et ,2. Ordre et Classification, Algèbre et Combinatoire, 2 tomes, Hachette, Paris, 1970. | Zbl
et ,3. Parcours dans les graphes : un outil pour l'algorithmique des ensembles ordonnés, Discr. Appl. Math., vol. 12, 1985, 215-231. | MR | Zbl
,4. Propriétés algorithmiques des treillis distributifs, Rapp. Rech., C.R.I.M., Montpellier (en préparation).
,5. Parcours dans les graphes sans circuit, Rapp. rech., n° 11, C.R.I.M., Montpellier, mai 1985.
et ,6. Invariants liés aux chemins dans les graphes sans circuit, Coll. Int. Th. Comb. Rome, 3-15 sept. 1973, p. 287-308. | MR | Zbl
et ,7. Boolean Matrix Multiplication and Transitive Closure, Conference Record, I.E.E.E. 12th Annual Symposium on Switching and Automata Theory, 1971, p. 129-131.
et ,8. New Bounds on the Complexity of the Shortest Path Problem, S.I.A.M. J. Comput., vol. 5, n° 1, mars 1976, p. 83-88. | MR | Zbl
,9A Reduct-and-Closure Algorithm for Graphs, Proceedings of M.F.C.S. 79, Springer-Verlag, Berlin, Heidelberg, New York, 1979, p. 301-307. | MR | Zbl
et ,10. Linear equivalences for transitivity in Graphs, Rapp. Rech. n° 83-10, E.N.S.M. Saint-Etienne, Discrete Applied Mathematics (Soumis).
, et ,11. N-free Posets as Generalizations of Series-Parallel Posets, Discr. Appl. Math., vol. 12, 1985 p. 279-291. | MR | Zbl
et ,12. Big Omicron and Big Omega and Big Theta, Sigact News, avril-juin 1976, p. 18-24.
,13.Data Structures andAlgorithms 2 : Graph Algorithms and NP completeness, Springer-Verlag, 1984. | Zbl
,14. Caractérisations métriques des ensembles ordonnés semi-modulaires, Math. Sci. Hum., vol. 56, 1976, p. 77-87. | Numdam | MR | Zbl
,15. Efficient Determination of the Transitive Closure of a Directed Graph, Dept. of Computer Science, University of Toronto, U.S.A., Inform. Proc. Lett., vol. 1, 1971, p. 56-58. | Zbl
,16. Shortest Path Problem is not harder than Matrix Multiplication, Inform. Proc. Lett., vol. 11, n° 3, 1981, p. 134-136. | MR | Zbl
,17. The Recognition of Series-Parallel Digraphs, S.I.A.M. J. Comput, vol. 11, n° 2, 1982, p. 298-313. | MR | Zbl
, et ,