Name
Abstract | ||
|---|---|---|
Let g(t) be the minimum number such that every graph G with average degree d(G) >= g(t) contains a K-t-minor. Such a function is known to exist, as originally shown by Mader. Kostochka and Thomason independently proved that g(t) is an element of Theta(t root log t). This paper shows that for all fixed epsilon > 0 and fixed sufficiently large t >= t(epsilon), if d(G) >= (2 + epsilon) g(t), then we can find this K-t-minor in linear time. This improves a previous result by Reed and Wood who gave a linear-time algorithm when d(G) >= 2(t-2). |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1137/120866725 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
algorithm,graph minor | Journal | 27 |
Issue | ISSN | Citations |
4 | 0895-4801 | 2 |
PageRank | References | Authors |
0.39 | 9 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vida Dujmovic | 1 | 416 | 43.34 |
| Daniel J. Harvey | 2 | 98 | 8.70 |
| Gwenaël Joret | 3 | 196 | 28.64 |
| Bruce A. Reed | 4 | 1311 | 122.69 |
| David R. Wood | 5 | 1073 | 96.22 |