A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
From MaRDI portal
(Redirected from Publication:5408591)
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}.
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
(4)
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)
