Back to search

University of Waterloo

Efficient Algorithms for RDV graphs

Abstract

dc:description.abstract

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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gokhale, Prashant Abhijit

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/21770

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Gokhale, Prashant Abhijit. Efficient Algorithms for RDV graphs. University of Waterloo, 2025. https://hdl.handle.net/10012/21770