pipette
ESEspañol

Solving problems in RDV Graphs faster and easier

Therese Biedl, G\"unter Rote

Preprint

In the authors' words

In interval graphs and many generalizations thereof, problems such as Matching, Independent Set, and Dominating Set can be solved with simple greedy algorithms in linear (i.e., ) time. However, it is sometimes possible to improve on this runtime if a suitable representation as intersection graph is given; for example it is possible to find a minimum dominating set in an interval graph in time. We study RDV graphs, a generalization of interval graphs, namely, the intersection graphs of directed paths in a rooted tree. It was known that the above three problems can be solved in time if a suitably small representation is given. In this paper, we reduce the runtime to . Furthermore, while the previous results used non-trivial operations such as range-minimum queries and ray-shooting queries, we need nothing more complicated than lists and (for Matching) a Union-Find data structure.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 20 pages, 2 appendices, 4 figures