THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS
Madhumangal Pal, Gobinda Prashad Bhattacharjee · International Journal of Parallel Emergent and Distributed Systems · 1995
Recently, it has been shown that resource allocation problems in parallel processing systems can be viewed as edge domination problems in graphs. Other applications of edge domination include encoding theory and network routing problems. In a graph G = (V,E) and edge (u,v) ∈ E is said to dominate itself and any edge (u,x) or (v,x) where x ∈ V. An Edge-Packing (EP) in a graph G is a set of edges (B), B CE such that no edge in E is dominated by more than one edge of B. A subset of edges E’ C E is called an Efficient Edge Domination (EED) set for the graph G if all edges in E are dominated by exactly one edge of E’. The EED problem for general graph is NP-complete. For the series parallel graph a linear time sequential algorithm is available. In this paper, a linear time sequential algorithm is presented to find EP for a weighted interval graph. Parallel algorithms are also presented to find EP for weighted and unweighted interval graphs. For the weighted case, the proposed parallel algorithm takes O(log2n) time and O(n3/logn) processors and for the unweighted case, the parallel algorithm lakes O(logn) time and O(n + m) processors on an EREW PRAM, where m,n represent number of edges and number of vertices of the graph. If EED set exists for the given unweighted interval graph then it can be computed using the same resource bound for finding EP of an unweighted interval graph.