Geodesic
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.

Voir la notice de l'article provenant de la source Numdam

@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/item/ITA_1987__21_2_181_0/

1. A. V. Aho, M. R. Garey et J. D. Ullman, The Transitive Reduction of a Directed Graph, S.I.A.M. J. Comput., vol. 1, n° 2, juin, 1972, p. 131-137. | Zbl | MR

2. M. Barbut et B. Monjardet, Ordre et Classification, Algèbre et Combinatoire, 2 tomes, Hachette, Paris, 1970. | Zbl

3. J. P. Bordat, Parcours dans les graphes : un outil pour l'algorithmique des ensembles ordonnés, Discr. Appl. Math., vol. 12, 1985, 215-231. | Zbl | MR

4. J. P. Bordat, Propriétés algorithmiques des treillis distributifs, Rapp. Rech., C.R.I.M., Montpellier (en préparation).

5. J. P. Bordat et O. Cogis, Parcours dans les graphes sans circuit, Rapp. rech., n° 11, C.R.I.M., Montpellier, mai 1985.

6. G. Chaty et M. Chein, Invariants liés aux chemins dans les graphes sans circuit, Coll. Int. Th. Comb. Rome, 3-15 sept. 1973, p. 287-308. | Zbl | MR

7. M. J. Fischer et A. R. Meyer, Boolean Matrix Multiplication and Transitive Closure, Conference Record, I.E.E.E. 12th Annual Symposium on Switching and Automata Theory, 1971, p. 129-131.

8. M. L. Fredman, 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. | Zbl | MR

9A. Goralcikova et V. Koubek, A Reduct-and-Closure Algorithm for Graphs, Proceedings of M.F.C.S. 79, Springer-Verlag, Berlin, Heidelberg, New York, 1979, p. 301-307. | Zbl | MR

10. M. Habib, M. Hamroun et R. Jegou, Linear equivalences for transitivity in Graphs, Rapp. Rech. n° 83-10, E.N.S.M. Saint-Etienne, Discrete Applied Mathematics (Soumis).

11. M. Habib et R. Jegou, N-free Posets as Generalizations of Series-Parallel Posets, Discr. Appl. Math., vol. 12, 1985 p. 279-291. | Zbl | MR

12. D. E. Knuth, Big Omicron and Big Omega and Big Theta, Sigact News, avril-juin 1976, p. 18-24.

13.K. Melhorn, Data Structures andAlgorithms 2 : Graph Algorithms and NP completeness, Springer-Verlag, 1984. | Zbl

14. B. Monjardet, Caractérisations métriques des ensembles ordonnés semi-modulaires, Math. Sci. Hum., vol. 56, 1976, p. 77-87. | Zbl | MR | mathdoc-id

15. I. Munro, 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. F. Romani, Shortest Path Problem is not harder than Matrix Multiplication, Inform. Proc. Lett., vol. 11, n° 3, 1981, p. 134-136. | Zbl | MR

17. J. Valdes, R. E. Tarjan et E. L. Lawler, The Recognition of Series-Parallel Digraphs, S.I.A.M. J. Comput, vol. 11, n° 2, 1982, p. 298-313. | Zbl | MR