Abstract
Given a simple graph G = (V,E), an edge (u,v) ∈ E is said to dominate itself and any edge (u,x) or (v,x), where x ∈ V. A subset D ⊆ E is called an efficient edge dominating set of G if all edges in E are dominated by exactly one edge 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 ∈ E is associated with a real number w(e), called the weight of e. The weighted efficient edge domination problem is to calculate an efficient edge dominating set D of G such that the weight w(D) of D is minimum, where w(D) = ∑{w(e) | e ∈ D}. In this paper, we show that the problem of determining whether G has an efficient edge dominating set is NP-complete when G is restricted to a bipartite graph. Consequently, the decision problem of efficient (vertex) domination remains NP-complete for the line graphs of bipartite graphs. Moreover, we present a linear time algorithm to solve the weighted efficient edge domination problem on bipartite permutation graphs, which form a subclass of bipartite graphs, using the technique of dynamic programming. © 1998 Elsevier Science B.V. All rights reserved.