A property tester for tree-likeness of quartet topologies

DOI10.1007/s00224-010-9276-5zbMath1227.68115MaRDI QIDQ649111

Peter Rossmanith, Maw-Shang Chang, Chuang-Chieh Lin

Publication date: 30 November 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-010-9276-5

zbMATH Keywords

randomized algorithm; property testing; quartet method; evolutionary tree

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68W20: Randomized algorithms

Related Items

Testing consistency of quartet topologies: a parameterized approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• Analysis of binary trees when occasional multifurcations can be considered as aggregates of bifurcations
• The complexity of reconstructing trees from qualitative characters and subtrees
• Self-testing/correcting with applications to numerical problems
• Inferring evolutionary trees with strong combinatorial evidence
• A fixed-parameter algorithm for minimum quartet inconsistency
• New fixed-parameter algorithms for the minimum quartet inconsistency problem
• Constructing Optimal Trees from Quartets
• A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application
• Property testing and its connection to learning and approximation
• Statistical Inference of Phylogenies
• Every monotone graph property is testable
• Tree structures for proximity data
• A few logs suffice to build (almost) all trees (I)
• Robust Characterizations of Polynomials with Applications to Program Testing