arXiv preprint ·
Solving problems in RDV Graphs faster and easier
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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., $O(m+n)$) 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 $O(n)$ 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 $O(n\log n)$ time if a suitably small representation is given. In this paper, we reduce the runtime to $O(n)$. 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Approximating Directed Telephone Multicast
Near-Optimal Consistency-Robustness Bounds for Non-Clairvoyant Scheduling
A 55-Addition Rank-23 Scheme for $3\times3$ Matrix Multiplication via Exact Two-Sided Minimization
Optimal Labeling Schemes for $Γ$-Free Matrices
Improved rapid phase ordering for Ising dynamics on random regular graphs
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.