An Optimal Algorithm to Solve 2-Neighbourhood Covering Problem on Interval Graphs

Let G =( V , E ) be a simple graph and k be a fixed positive integer. A vertex w is said to be a k -neighbourhood-cover of an edge ( u , v ) if d ( u , w ) h k and d ( v , w ) h k . A set C ³ V is called a k -neighbourhood-covering set if every edge in E is k -neighbourhood-covered by some vertices of C . This problem is NP-complete for general graphs even it remains NP-complete for chordal graphs. Using dynamic programming technique, an O ( n ) time algorithm is designed to solve minimum 2-neighbourhood-covering problem on interval graphs. A data structure called interval tree is used to solve this problem.

Keywords:

• Design Of Algorithms
• Analysis Of Algorithms
• 2-neighbourhood-covering
• Interval Tree
• Interval Graph