The k-neighbourhood-covering problem on interval graphs

Abstract

Let G=(V, E) be a simple connected graph and k be a fixed positive integer. A vertex w is said to be a k-neighbourhood-cover (kNC) of an edge (u, v) if d(u, w)≤k and d(v, w)≤k. A set C ⊆ V is called a kNC set if every edge in E is kNC by some vertices of C. The decision problem associated with this problem is NP-complete for general graphs and it remains NP-complete for chordal graphs. In this article, we design an O(n) time algorithm to solve minimum kNC problem on interval graphs by using a data structure called interval tree.

Keywords:

• design of algorithms
• analysis of algorithms
• k-neighbourhood-covering
• interval tree
• interval graph

2000 AMS Subject Classifications :

• 68Q22
• 68Q25
• 68R10

Acknowledgements

We thank the anonymous referees and the Subject Editor for their valuable suggestions which improved the presentation and readability of the article. This work is partially supported by UGC grant F. PSW-072/03-04.