Browsing by Author "Gokhale, Prashant Abhijit"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Efficient Algorithms for RDV graphs
    (University of Waterloo, 2025-05-22) Gokhale, Prashant Abhijit
    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(n \log{n})$ 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.