Étude de la séparation et de l'élimination sur une famille de graphes quotients déduite d'une méthode de dissections emboîtées
Charrier, P. ; Roman, J.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988), p. 245-265 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1988-01-01
@article{ITA_1988__22_2_245_0,
     author = {Charrier, P. and Roman, J.},
     title = {\'Etude de la s\'eparation et de l'\'elimination sur une famille de graphes quotients d\'eduite d'une m\'ethode de dissections embo\^\i t\'ees},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {22},
     year = {1988},
     pages = {245-265},
     mrnumber = {951340},
     zbl = {0645.68073},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/ITA_1988__22_2_245_0}
}

Charrier, P.; Roman, J. Étude de la séparation et de l'élimination sur une famille de graphes quotients déduite d'une méthode de dissections emboîtées. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988) pp. 245-265. http://gdmltest.u-ga.fr/item/ITA_1988__22_2_245_0/

1. S. N. Bhatt et F. T. Leighton, A Framework for Solving VLSI Graph Layout Problems, J. Comput. Syst. Sci., vol. 28, 1984, p. 300-343. | MR 760549 | Zbl 0543.68052

2. P. Charrier et J. Roman, Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées, Rapport interne Informatique, Université de Bordeaux-I, 1986, soumis pour publication dans Numerische Mathematik. | Zbl 0663.65020

3. P. Charrier et J. Roman, Study of the Parallelism Inducedby a Nested Dissection Method and of its Implementation on a Message-Passing Multiprocessor Computeur, Rapport interne Informatique, Université de Bordeaux-I, 1987, soumis pour publication dans S.I.A.M. Journal of Computing.

4. P. G. Ciarlet, Numerical Analysis of the Finite Element Method, Séminaire de mathématiques supérieures, Presses de l'Université de Montréal, 1976. | MR 495010 | Zbl 0363.65083

5. M. C. Counilh, J. M. Lepine, J. Roman, F. Rubi et B. Vauquelin, Description du calculateur CHEOPS, Rapport interne Informatique, Université de Bordeaux-I, 1986.

6. H. N. Djidjev, On the Problem of Partioning Planar Graphs, S.I.A.M. J. Algebraic Discrete Methods, Vol. 3, 1982, p. 229-240. | MR 655563 | Zbl 0503.05057

7. J. A. George, Nested Dissection of a Regular Finite Element Mesh., S.I.A.M. J. Numer. Anal., Vol. 10, 1973, p. 345-367. | MR 388756 | Zbl 0259.65087

8. J. A. George et J. W. H. Liu, Computer Solution of Large Spar se Positive Defïnite Systems, Englewood Cliffs, New Jersey, Prentice Hall, 1981. | MR 646786 | Zbl 0516.65010

9. J. R. Gilbert, Some Nested Dissection Order is Nearly Optimal, Technical report 86-767, Department of Computer Science, Cornell University, 1986.

10. J. R. Gilbert, J. P. Hutchinson et R. E. Tarjan, A Separator Theorem for Graphs of Bounded Genus, J. Algorithms, vol. 5, 1984, p. 391-407. | MR 756165 | Zbl 0556.05022

11. J. R. Gilbert, D. J. Rose et A. Edenbrandt, A Separator Theorem for Chordal Graphs, S.I.A.M. J. Algebraic Discrete Methods, vol. 5, 1984, p. 306-313. | MR 752037 | Zbl 0551.05049

12. J. R. Gilbert et R. E. Tarjan, The Analysis of a Nested Dissection Algorithm, Numerische Mathematik, vol. 50, 1987, p. 377-404. | MR 875164 | Zbl 0645.65012

13. H. T. Kung, The Structure of Parallel Algorithm, Advances in Computers, vol.19, Academic Press, New York, 1980.

14. F. T. Leighton, A Layout Strategy for VLSI which is Provably Good, Proc. 14th Ann. A.C.M. Symp. Theory Comput., 1982, p. 85-98.

15. R. J. Lipton et R. E. Tarjan, A Separator Theorem for Planar Graphs, S.I.A.M. J. on Appl. Math., vol. 36, 1979, p. 177-189. | MR 524495 | Zbl 0432.05022

16. R. J. Lipton et R. E. Tarjan, Applications of a Planar Separator Theorem, S.I.A.M. J. Comput., vol. 9, 1980. p. 615-627 | MR 584516 | Zbl 0456.68077

17. R. J. Lipton, D. J. Rose et R. E. Tarjan, Generalized Nested Dissection, S.I.A.M. J. Numer. Anal., vol. 16, 1979, p. 346-358. | MR 526496 | Zbl 0435.65021

18. M. Raynal, Algorithmique du parallélisme: le problème de l'exclusion mutuelle, Dunod Informatique, 1984.

19. M. Raynal, Algorithmes distribués et protocoles, Eyrolles, Paris, 1985.

20. J. Roman, Dissection emboîtée et n°-théorème de séparation (l/2 ( σ ( l), Rapport interne Analyse appliquée et Informatique, Université de Bordeaux-I, 1984.

21. J. Roman, Calculs de complexité relatifs à une méthode de dissection emboîtée, Numerische Mathematik, vol.47, 1985, p. 175-190. | MR 799683 | Zbl 0537.65025

22. D. J. Rose, A Graph-Theoretic Study of the Numerical Solution of Sparse Positive Defïnite Systems of Linear Equations, Graph Theory and Computing, p. 183-217, R.C. Read, Academic Press, New York, 1973. | MR 341833 | Zbl 0266.65028

23. D. J. Rose, R. E. Tarjan et G. S. Lueker, Algorithmic Aspects of Vertex Elimination on Graphs, S.I.A.M. J. Comput, vol. 5, 1976, p. 266-283. | MR 408312 | Zbl 0353.65019

24. C. L. Settz, The Cosmic Cube, Commun. A.C.M., vol.28, n° 1, 1985, p. 22-33.

25. G. Varenne, Dessins récursifs de graphes, Thèse de 3e cycle, Université de Paris-VII, Laboratoire Informatique Théorique et Programmation, 1985.