| Title:
|
A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs (English) |
| Author:
|
Caro, Yair |
| Author:
|
Rojas, Juan |
| Author:
|
Ruiz, Sergio |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
46 |
| Issue:
|
3 |
| Year:
|
1996 |
| Pages:
|
413-419 |
| . |
| Category:
|
math |
| . |
| MSC:
|
05C70 |
| MSC:
|
05C75 |
| MSC:
|
05C85 |
| idZBL:
|
Zbl 0879.05063 |
| idMR:
|
MR1408296 |
| DOI:
|
10.21136/CMJ.1996.127306 |
| . |
| Date available:
|
2009-09-24T09:58:24Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127306 |
| . |
| Reference:
|
[BBJR] C. Barrientos, A Bernasconi, E. Jeltsch, S. Ruiz: Randomly star-decomposable graphs.Congressus Numeratium 64 (1988), 193–195. MR 0988681 |
| Reference:
|
[BGH] L. W. Beineke, W. Goddard, P. Hamburger: Random Packings of Graphs.Manuscript, . |
| Reference:
|
[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 0428780 |
| Reference:
|
[JGT] : .Journal of Graph Theory 1, 9 (1985), . Zbl 1170.01303 |
| Reference:
|
[RU] S. Ruiz: Randomly decomposable graphs.Discrete Mathematics 57 (1985), 123–128. Zbl 0588.05035, MR 0816053, 10.1016/0012-365X(85)90161-X |
| Reference:
|
[SK] D. P. Sumner: Randomly Matchable Graphs.Journal of Graph Theory 3 (1979), 183–186. Zbl 0404.05053, MR 0530304, 10.1002/jgt.3190030209 |
| Reference:
|
[TAD] M. Tarsi, D. Dor: Graph Decomposition is NPC, a Complete Proof of Holyer’s Conjecture.(to appear). |
| . |
