Parameterized leaf power recognition via embedding into graph products
From MaRDI portal
Publication:786044
DOI10.1007/s00453-020-00720-8zbMath1452.68135MaRDI QIDQ786044
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/
dynamic programming; monadic second-order logic; tree decomposition; phylogenetic tree; strong product of graphs; fixed-parameter tractable; Courcelle's theorem; leaf power
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