A parametric analysis of the largest induced tree problem in random graphs
Protasi, M. ; Talamo, M.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 20 (1986), p. 211-219 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1986-01-01
@article{ITA_1986__20_3_211_0,
     author = {Protasi, M. and Talamo, M.},
     title = {A parametric analysis of the largest induced tree problem in random graphs},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {20},
     year = {1986},
     pages = {211-219},
     mrnumber = {894712},
     zbl = {0604.05014},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1986__20_3_211_0}
}

Protasi, M.; Talamo, M. A parametric analysis of the largest induced tree problem in random graphs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 20 (1986) pp. 211-219. http://gdmltest.u-ga.fr/item/ITA_1986__20_3_211_0/

1. P. Erdös and Z. Palka, Trees in Random Graphs, Discr. Math., Vol 46, 1983. | MR 710885 | Zbl 0535.05049

2. J. Friedman, Constructing 0 (n log n) size monotone formulae for the k-th elementary symmetric polynomial of n boolean variables, Proc. 25th Symp. on Foundations of Computer Science, 1984.

3. M. Karonski and Z. Palka, On the Size of a Maximal Induced Tree in a Random Graph, Math. Slovaca, Vol. 30, 1980. | MR 587240 | Zbl 0438.05028

4. A. Marchetti-Spaccamela and M. Protasi, The Largest Tree in a Random Graph, Theor. Comp. Sci., Vol. 23, 1983. | MR 702012 | Zbl 0512.68045

5. M. Protasi and M. Talamo, A New Probabilistic Model for the Study of Algorithmic Properties of Random Graph Problems, Proc. Conf. on Foundations of Computation Theory, Borgholm, Lect. Notes in Comp. Sci., Vol. 158, 1983. | MR 734734 | Zbl 0549.68068

6. M. Protasi and M. Talamo, A General Analysis of the Max-Independent Set and Related Problems on Random Graphs, Tech. Rep. 3/84, Dip. Matematica, Università dell'Aquila, 1984.

7. M. Protasi and M. Talamo, On the Maximum Size of Random Trees, Proc. X Coll. on Trees in Algebra and Programming, Berlin, Lect. Notes in Comp. Sci., Vol. 185, 1985. | Zbl 0576.05014