Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs

DOI10.1007/s00453-016-0166-3zbMath1361.05133MaRDI QIDQ527430

Meirav Zehavi

Publication date: 11 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0166-3

zbMATH Keywords

\(k\)-tree; parameterized algorithm; proper coloring; \(k\)-internal out-branching; multilinear detection

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms