A Property Tester for Tree-Likeness of Quartet Topologies

Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function  f over a domain D , a property ℘ and a parameter 0< ε 0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2011-10, Vol.49 (3), p.576-587
Main Authors: Chang, Maw-Shang, Lin, Chuang-Chieh, Rossmanith, Peter
Format: Article
Language:English
Subjects:
Algorithms
Computation
Computer Science
Leaves
Mathematical analysis
Mathematical models
Queries
Studies
Tasks
Theory of Computation
Topological manifolds
Topology
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function  f over a domain D , a property ℘ and a parameter 0< ε 0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O ( n 3 / ε ) queries, and is of one-sided error and non-adaptive.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-010-9276-5