A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
Authors:
- Vida DujmovićVDVida Dujmović
- Daniel J. HarveyDHDaniel J. Harvey
- Gwenaël JoretGJGwenaël Joret
- Bruce ReedBRBruce Reed
- David R. WoodDWDavid R. Wood
- 1 January 2013
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 27 (4) , 1770-1774
Abstract
Let $g(t)$ be the minimum number such that every graph $G$ with average degree $d(G) \geq 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) \in \Theta(t\sqrt{\log t})$. This paper shows that for all fixed $\epsilon > 0$ and fixed sufficiently large $t \geq t(\epsilon)$, if $d(G) \geq (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) \geq 2^{t-2}$.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- The disjoint paths problem in quadratic timeJournal of Combinatorial Theory, Series B, 2012
- Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications2011
- A linear-time algorithm to find a separator in a graph excluding a minorACM Transactions on Algorithms, 2009
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximationDiscrete Applied Mathematics, 2009
- The Extremal Function for Complete MinorsJournal of Combinatorial Theory, Series B, 2001
- Graph Minors .XIII. The Disjoint Paths ProblemJournal of Combinatorial Theory, Series B, 1995
- Lower bound of the hadwiger number of graphs by their average degreeCombinatorica, 1984
- An extremal function for contractions of graphsMathematical Proceedings of the Cambridge Philosophical Society, 1984
- Homomorphies tze f r GraphenMathematische Annalen, 1968
- Homomorphieeigenschaften und mittlere Kantendichte von GraphenMathematische Annalen, 1967