Master’s Thesis Presentation • Algorithms and Complexity • Efficient Algorithms for RDV Graphs

Please note: This master’s thesis presentation will take place in DC 2314 and online.

Prashant Gokhale, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Therese Biedl

In this thesis, we study the maximum matching and minimum dominating set problem in RDV graphs, i.e., graphs that are vertex-intersection graphs of downward paths in a rooted tree. A straightforward implementation of these algorithms would require O(n+m) time. We improve their efficiency by transforming the question about the neighborhood of v into a type of range query amid a set of horizontal and vertical line segments. Our algorithms run in O(nlogn) time, presuming a O(n)-sized intersection representation of the graph is given. In addition, our techniques can also be used to obtain faster algorithms for maximum independent set and perfect k-clique packing in RDV graphs.

To attend this master’s thesis presentation in in person, please go to DC 2314. You can also attend virtually using Zoom.