{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T17:26:00Z","timestamp":1791221160433,"version":"4.1.0"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>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 &gt; 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}$.<\/jats:p>","DOI":"10.1137\/120866725","type":"journal-article","created":{"date-parts":[[2013,10,22]],"date-time":"2013-10-22T15:41:29Z","timestamp":1382456489000},"page":"1770-1774","source":"Crossref","is-referenced-by-count":4,"title":["A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph"],"prefix":"10.1137","volume":"27","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel J.","family":"Harvey","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bruce","family":"Reed","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,10,22]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.07.004"},{"key":"atypb2","first-page":"37","volume":"38","author":"Kostochka A. V.","year":"1982","journal-title":"Metody Diskret. Analiz."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579141"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01364272"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01350657"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/1597036.1597043"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.002"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100061521"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2013"},{"key":"atypb11","unstructured":"C. Wulff-Nilsen,<i>Faster shortest path algorithm for $H$-minor free graphs with negative edge weights<\/i> CoRR, abs\/1008.1048 (2010)."},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"C. Wulff-Nilsen,<i>Separator theorems for minor-free and shallow minor-free graphs with applications<\/i> in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, Los Alamitos, CA, 2011, pp. 37-46.","DOI":"10.1109\/FOCS.2011.15"},{"key":"atypb13","first-page":"108","author":"Yuster R.","year":"2007","journal-title":"New York"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120866725","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:22:48Z","timestamp":1787318568000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120866725"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/120866725"],"URL":"https:\/\/doi.org\/10.1137\/120866725","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}