Complexité de problèmes liés aux graphes sans circuit

J. P. Bordat

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1987)

  • Volume: 21, Issue: 2, page 181-197
  • ISSN: 0988-3754

How to cite

top

Bordat, J. P.. "Complexité de problèmes liés aux graphes sans circuit." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 21.2 (1987): 181-197. <http://eudml.org/doc/92283>.

@article{Bordat1987,
author = {Bordat, J. P.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {transitive reduction; transitive closure; acyclic digraphs; linear time algorithmic solutions},
language = {fre},
number = {2},
pages = {181-197},
publisher = {EDP-Sciences},
title = {Complexité de problèmes liés aux graphes sans circuit},
url = {http://eudml.org/doc/92283},
volume = {21},
year = {1987},
}

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
PB - EDP-Sciences
VL - 21
IS - 2
SP - 181
EP - 197
LA - fre
KW - transitive reduction; transitive closure; acyclic digraphs; linear time algorithmic solutions
UR - http://eudml.org/doc/92283
ER -

References

top
  1. 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. Zbl0247.05128MR306032
  2. 2. M. BARBUT et B. MONJARDET, Ordre et Classification, Algèbre et Combinatoire, 2 tomes, Hachette, Paris, 1970. Zbl0267.06001
  3. 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. Zbl0589.06004MR813971
  4. 4. J. P. BORDAT, Propriétés algorithmiques des treillis distributifs, Rapp. Rech., C.R.I.M., Montpellier (en préparation). 
  5. 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. 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. Zbl0349.05112MR472588
  7. 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. 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. Zbl0326.68027MR404050
  9. 9 A. 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. Zbl0408.68038MR570989
  10. 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. 11. M. HABIB et R. JEGOU, N-free Posets as Generalizations of Series-Parallel Posets, Discr. Appl. Math., vol. 12, 1985 p. 279-291. Zbl0635.06002MR813975
  12. 12. D. E. KNUTH, Big Omicron and Big Omega and Big Theta, Sigact News, avril-juin 1976, p. 18-24. 
  13. 13. K. MELHORN, Data Structures andAlgorithms 2 : Graph Algorithms and NP completeness, Springer-Verlag, 1984. Zbl0556.68002
  14. 14. B. MONJARDET, Caractérisations métriques des ensembles ordonnés semi-modulaires, Math. Sci. Hum., vol. 56, 1976, p. 77-87. Zbl0367.06010MR444543
  15. 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. Zbl0221.68030
  16. 16. F. ROMANI, Shortest Path Problem is not harder than Matrix Multiplication, Inform. Proc. Lett., vol. 11, n° 3, 1981, p. 134-136. Zbl0454.68069MR593406
  17. 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. Zbl0478.68065MR652904

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.