A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
From MaRDI portal
Publication:5408591
DOI10.1137/120866725zbMATH Open1285.05164arXiv1202.2624OpenAlexW2162357422MaRDI QIDQ5408591FDOQ5408591
Authors: Vida Dujmović, Daniel J. Harvey, Gwenaël Joret, David R. Wood, Bruce Reed 
Publication date: 10 April 2014
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
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 article 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}.
Full work available at URL: https://arxiv.org/abs/1202.2624
Recommendations
- A linear-time algorithm to find a separator in a graph excluding a minor
- A practical algorithm for making filled graphs minimal
- Graph minors and parameterized algorithm design
- scientific article; zbMATH DE number 742959
- Computing Minimal Spanning Subgraphs in Linear Time
- scientific article; zbMATH DE number 795221
- A simpler algorithm and shorter proof for the graph minor decomposition
- Two linear time algorithms for MST on minor closed graph classes.
- scientific article; zbMATH DE number 5874803
Cited In (3)
This page was built for publication: A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5408591)
