Geodesic
A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs
Czechoslovak Mathematical Journal, Tome 46 (1996) no. 3, pp. 413-419
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

DOI : 10.21136/CMJ.1996.127306
Classification : 05C70, 05C75, 05C85 
@article{10_21136_CMJ_1996_127306,
     author = {Caro, Yair and Rojas, Juan and Ruiz, Sergio},
     title = {A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {413--419},
     year = {1996},
     volume = {46},
     number = {3},
     doi = {10.21136/CMJ.1996.127306},
     mrnumber = {1408296},
     zbl = {0879.05063},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.1996.127306/}
}
TY  - JOUR
AU  - Caro, Yair
AU  - Rojas, Juan
AU  - Ruiz, Sergio
TI  - A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs
JO  - Czechoslovak Mathematical Journal
PY  - 1996
SP  - 413
EP  - 419
VL  - 46
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.1996.127306/
DO  - 10.21136/CMJ.1996.127306
LA  - en
ID  - 10_21136_CMJ_1996_127306
ER  - 
%0 Journal Article
%A Caro, Yair
%A Rojas, Juan
%A Ruiz, Sergio
%T A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs
%J Czechoslovak Mathematical Journal
%D 1996
%P 413-419
%V 46
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.1996.127306/
%R 10.21136/CMJ.1996.127306
%G en
%F 10_21136_CMJ_1996_127306
Caro, Yair; Rojas, Juan; Ruiz, Sergio. A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs. Czechoslovak Mathematical Journal, Tome 46 (1996) no. 3, pp. 413-419. doi: 10.21136/CMJ.1996.127306

[BBJR] C. Barrientos, A Bernasconi, E. Jeltsch, S. Ruiz: Randomly star-decomposable graphs. Congressus Numeratium 64 (1988), 193–195. | MR

[BGH] L. W. Beineke, W. Goddard, P. Hamburger: Random Packings of Graphs. Manuscript, .

[EVK] S. Even, O. Kariv: An $O(n^{2.5})$ algorithm for maximum matching in general graphs. Proc. 16th Annual Symp. on Foundation of Computer Sciences. IEEE, New York (1975), 100–112. | MR

[JGT] Journal of Graph Theory 1, 9 (1985), . | Zbl

[RU] S. Ruiz: Randomly decomposable graphs. Discrete Mathematics 57 (1985), 123–128. | DOI | MR | Zbl

[SK] D. P. Sumner: Randomly Matchable Graphs. Journal of Graph Theory 3 (1979), 183–186. | DOI | MR | Zbl

[TAD] M. Tarsi, D. Dor: Graph Decomposition is NPC, a Complete Proof of Holyer’s Conjecture. (to appear).

Cité par Sources :