Contracting graphs to paths and trees
From MaRDI portal
Publication:2441588
DOI10.1007/s00453-012-9670-2zbMath1310.68229arXiv1104.3677MaRDI QIDQ2441588
Christophe Paul, Pinar Heggernes, Daniel Lokshtanov, Pim van 't Hof, Benjamin Lévêque
Publication date: 25 March 2014
Published in: Algorithmica, Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1104.3677
kernelization; graph modification problems; edge contractions; FPT algorithms; tree contraction; path contraction
68Q25: Analysis of algorithms and problem complexity
05C05: Trees
05C38: Paths and cycles
05C85: Graph algorithms (graph-theoretic aspects)
68W20: Randomized algorithms