SOLVING THE WEIGHTED EFFICIENT EDGE DOMINATION PROBLEM ON BIPARTITE PERMUTATION GRAPHS

Given a simple graph G=(V,E), an edge (u, U) is an element of E is sai d to dominate itself and any edge (u,x) or (u,x), where x is an elemen t of V. A subset D subset of or equal to E is called an efficient edge dominating set of G if all edges in E are dominated by exactly one ed ge of D. The efficient edge domination problem is to find an efficient edge dominating set of minimum size in G. Suppose that each edge e is an element of E is associated with a real number w(e), called the wei ght of e. The weighted efficient edge domination problem is to calcula te an efficient edge dominating set D of G such that the weight w(D) o f D is minimum, where w(D) = Sigma{w(e) \ e is an element of D}. In th is paper, we show that the problem of determining whether G has an eff icient edge dominating set is NP-complete when G is restricted to a bi partite graph. Consequently, the decision problem of efficient (vertex ) domination remains NP-complete for the line graphs of bipartite grap hs. Moreover, we present a linear time algorithm to solve the weighted efficient edge domination problem on bipartite permutation graphs, wh ich form a subclass of bipartite graphs, using the technique of dynami c programming. (C) 1998 Elsevier Science B.V. All rights reserved.