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

Charrier, P. ; Roman, J.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988) no. 2, pp. 245-265.

MR Zbl

@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},
     pages = {245--265},
     publisher = {EDP-Sciences},
     volume = {22},
     number = {2},
     year = {1988},
     mrnumber = {951340},
     zbl = {0645.68073},
     language = {fr},
     url = {http://www.numdam.org/item/ITA_1988__22_2_245_0/}
}

TY  - JOUR
AU  - Charrier, P.
AU  - Roman, J.
TI  - É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
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1988
SP  - 245
EP  - 265
VL  - 22
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1988__22_2_245_0/
LA  - fr
ID  - ITA_1988__22_2_245_0
ER  -

%0 Journal Article
%A Charrier, P.
%A Roman, J.
%T É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
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1988
%P 245-265
%V 22
%N 2
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1988__22_2_245_0/
%G fr
%F 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) no. 2, pp. 245-265. http://www.numdam.org/item/ITA_1988__22_2_245_0/

Bibliographie
Cité par

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 | Zbl

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

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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.