Daniel Kral (University of Warwick)
27/09/13 12:30 Talks
Algorithms for First Order model checking
Speaker:
Daniel Kral (University of Warwick, UK)
Abstract:
Algorithms for deciding first order (FO) properties has attracted a significant amount of attention. In the case of graphs, FO properties include the existence of a subgraph or a dominating set of a fixed size. In the talk, we first survey commonly applied techniques to design FPT algorithms for FO properties and we then focus on one class of graphs, intersection graphs of intervals with finitely many lengths. The standard techniques do not seem to straightforwardly apply here, but we are still able to design an FPT algorithm for deciding FO properties for this class of graphs.
The talk contains results obtained during joint work with Ganian, Hlineny, Obdrzalek, Schwartz and Teska.
Date:
Friday, September 27, 2013
Time:
12:30 pm - 1:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby
Daniel Kral (University of Warwick, UK)
Abstract:
Algorithms for deciding first order (FO) properties has attracted a significant amount of attention. In the case of graphs, FO properties include the existence of a subgraph or a dominating set of a fixed size. In the talk, we first survey commonly applied techniques to design FPT algorithms for FO properties and we then focus on one class of graphs, intersection graphs of intervals with finitely many lengths. The standard techniques do not seem to straightforwardly apply here, but we are still able to design an FPT algorithm for deciding FO properties for this class of graphs.
The talk contains results obtained during joint work with Ganian, Hlineny, Obdrzalek, Schwartz and Teska.
Date:
Friday, September 27, 2013
Time:
12:30 pm - 1:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby