Solving the weighted efficient edge domination problem on bipartite permutation graphs

✍ Scribed by Chin Lung Lu; Chuan Yi Tang

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 666 KB
• Volume: 87
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(98)00057-2

✦ Synopsis

Given a simple graph G = (V, E), an edge (u, u) E E is said to dominate itself and any edge (u,x) or (u,x), where x E V. A subset D C 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 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) = x{w(e)

1 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.