BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260916T214646Z
UID:Seminar-dept-287@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20120517T150000
DTEND:20120517T160000
SUMMARY:School Seminar Series
DESCRIPTION:Yonatan Goldhirsh: Testing forbidden topological subtrees\n\nWe say that a colored ordered rooted tree H is a topological subtree of a colored ordered rooted tree T if we can map the vertices of H to vertices of T in a mapping which is one-to-one, preserves colors, preserves the ``descendant of'' relation, preserves right-to-left order, and maps least common ancestors to least common ancestors. Fix an ordered rooted tree T and let F be a family of ``forbidden'' colored ordered trees. We present an algorithm for testing whether a coloring of T is free from F or is epsilon-far from being free from F, with query complexity depending only on F and epsilon. This is an instance of the massively parameterized testing model, as T itself is immutable. Families of forbidden topological subtrees generalize previously considered tree coloring properties, such as tree monotonicity [FLNRRS 02] and convexity-like properties [FY 07].\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=287
LOCATION:G12
END:VEVENT
END:VCALENDAR