Parameterized leaf power recognition via embedding into graph products

DOI10.1007/s00453-020-00720-8zbMath1452.68135MaRDI QIDQ786044

David Eppstein, Elham Havvaei

Publication date: 12 August 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10217/

zbMATH Keywords

dynamic programming; monadic second-order logic; tree decomposition; phylogenetic tree; strong product of graphs; fixed-parameter tractable; Courcelle's theorem; leaf power

Mathematics Subject Classification ID

05C05: Trees

92D15: Problems related to evolution

68R10: Graph theory (including graph drawing) in computer science

03B70: Logic in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C76: Graph operations (line graphs, products, etc.)

68Q27: Parameterized complexity, tractability and kernelization