Cancelled: ICE-TCS seminar: Tree Matching, 20 years later
Date and time: Friday, 27 March 2015, at 2pm
Place: Room M102
Title: Tree Matching, 20 years later
Speaker: Magnús M. Halldórsson (Reykjavik University)
Abstract: XML is a popular data representation, which formally corresponds to an unordered labeled tree. "Give me the closest match" queries correspond to tree matching. We examine our algorithmic explorations into tree matching problems, which started in early 1995 but appeared in proper form only recently. This includes exact algorithms for special cases, hardness results, fixed-parameter algorithms, and approximation algorithms. It turns out to have a surprising connection to the problem of finding a large independent set in so-called 2-interval graphs.
The talk will be given at a level appropriate for undergraduate students with some familiarity with algorithms or complexity.