An Optimal Algorithm to Solve 2-Neighbourhood Covering Problem on Interval Graphs
Sukumar Mondal, Madhumangal Pal, Tapan Kumar Pal · International Journal of Computer Mathematics · 2002
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.