Narrow Results

For a fixed positive integer $k$, a $k$-hop dominating set$D$ of a graph $G=(V,E)$ is a subset of $V$ such that every vertex $x\in V$ is within $k$-steps from at least one vertex $y\in D$, i.e., $d(x,y)\le k$. A $k$-hop dominating set $D$ is said to be minimal if there does not exist any $D^{\prime }\subset D$ such that $D^{\prime }$ is a $k$-hop dominating set of G. A dominating set $D$ is said to be minimum $k$-hop dominating set, if it is minimal as well as it is $k$-hop dominating set. In this paper, we present an optimal algorithm to find a minimum $k$-hop dominating set of interval graphs with $n$ vertices which runs in $O(n)$ time.

We present an algorithm for the All Pairs Shortest Distance problem on an interval graph on n vertices: after O(n) preprocessing time, the algorithm can deliver a response to a distance query in O(1) time. The method used here is simpler than the method of Chen et al. [4], which has the same preprocessing and query time. It is assumed that an interval model for the graph is given, and ends of intervals are already sorted by coordinate. The preprocessing algorithm can be executed in the EREW PRAM model in O(log n) time, using n/log n processors. These algorithms (sequential and parallel) may be extended to circular arc graphs, with the same time and processor bounds.