In this paper, we study the dominating set problem in RDV graphs, a graph class that lies between interval graphs and chordal graphs and defined as the vertex-intersection graphs of downward paths in a rooted tree. It was shown in a previous paper that adjacency queries in an RDV graph can be reduced to the question whether a horizontal segment intersects a vertical segment. This was then used to find a maximum matching in an n-vertex RDV graph, using priority search trees, in \(O(n\log n)\) time, i.e., without even looking at all edges. In this paper, we show that if additionally we also use a ray shooting data structure, we can also find a minimum dominating set in an RDV graph \(O(n\log n)\) time (presuming a linear-sized representation of the graph is given).. The same idea can also be used for a new proof to find a minimum dominating set in an interval graph in O(n) time.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Using Ray-Shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs

  • Therese Biedl,
  • Prashant Gokhale

摘要

In this paper, we study the dominating set problem in RDV graphs, a graph class that lies between interval graphs and chordal graphs and defined as the vertex-intersection graphs of downward paths in a rooted tree. It was shown in a previous paper that adjacency queries in an RDV graph can be reduced to the question whether a horizontal segment intersects a vertical segment. This was then used to find a maximum matching in an n-vertex RDV graph, using priority search trees, in \(O(n\log n)\) time, i.e., without even looking at all edges. In this paper, we show that if additionally we also use a ray shooting data structure, we can also find a minimum dominating set in an RDV graph \(O(n\log n)\) time (presuming a linear-sized representation of the graph is given).. The same idea can also be used for a new proof to find a minimum dominating set in an interval graph in O(n) time.