A note on convex characters, Fibonacci numbers and exponential-time algorithms

DOI10.1016/j.aam.2016.10.003zbMath1431.05084arXiv1508.02598OpenAlexW2963518893WikidataQ115598944 ScholiaQ115598944MaRDI QIDQ730310

Steven Kelk, Georgios Stamoulis

Publication date: 27 December 2016

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1508.02598

zbMATH Keywords

algorithmsconvexitycountingFibonacci numberstreesphylogenetics

Mathematics Subject Classification ID

Applications of graph theory (05C90) Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Related Items (7)

Sharp upper and lower bounds on a restricted class of convex characters ⋮ Convex Characters, Algorithms, and Matchings ⋮ A near-linear kernel for bounded-state parsimony distance ⋮ Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm ⋮ Combinatorial Scoring of Phylogenetic Networks ⋮ Reflections on kernelizing and computing unrooted agreement forests ⋮ A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees

Cites Work

• Unnamed Item
• On the maximum parsimony distance between phylogenetic trees
• Reduction rules for the maximum parsimony distance on phylogenetic trees
• Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
• The complexity of reconstructing trees from qualitative characters and subtrees
• Identifying phylogenetic trees
• Basic Phylogenetic Combinatorics
• Subtree transfer operations and their induced metrics on evolutionary trees

This page was built for publication: A note on convex characters, Fibonacci numbers and exponential-time algorithms