An efficient parallel algorithm for the efficient domination problem on distance-hereditary graphs
Tóm tắt
In the literature, there are quite a few sequential and parallel algorithms for solving problems on distance-hereditary graphs. With an n-vertex and m-edge distance-hereditary graph G, we show that the efficient domination problem on G can be solved in O(log/sup 2/ n) time using O(n + m) processors on a CREW PRAM. Moreover, if a binary tree representation of G is given, the problem can be optimally solved in O(log n) time using O(n/log n) processors on an EREW PRAM.
Từ khóa
#Parallel algorithms #Phase change random access memory #Binary trees #Tree graphs #Bipartite graph #Joining processes #Concurrent computing #Codes #Resource management #Parallel processingTài liệu tham khảo
bange, 1978, Disjoint Dominating Sets in Trees, Sandia Laboratories Report
10.1016/0012-365X(94)00052-K
10.1016/0095-8956(73)90042-7
bange, 1988, Efficient Dominating Sets in Graphs, Application of Discrete Math, 189
bandelt, 1989, Distance-Hereditary Graphs, J Combinatorial Theory Series B, 41, 182, 10.1016/0095-8956(86)90043-2
10.1016/0196-6774(89)90017-5
chang, 1997, Dynamic Programming on Distance-Hereditary Graphs, Proc Seventh Int'l Symp Algorithms and Computation (ISAAC'97), 344
10.1007/BFb0045090
yen, 1996, The Weighted Perfect Domination Problem and Its Variants, Discrete Applied Math, 66, 147, 10.1016/0166-218X(94)00138-4
esfahanian, 1993, Distance-Hereditary Graphs and Multidestination Message-Routing in Multicomputers, J Combinatorial Math and Combinatorial Computing, 13, 213
golumbic, 1980, Algorithmic Graph Theory and Perfect Graphs
yen, 1992, Algorithmic Aspects of Perfect Domination
10.1137/0217032
10.1016/S0166-218X(98)00060-2
10.1007/3-540-58218-5_34
oellermann, 1994, Computing the Average Distance of a Distance-Hereditary Graph in Linear Time, Congressus Numerantium, 103, 219
10.1016/0196-6774(91)90012-N
10.1016/0196-6774(88)90007-7
10.1016/0166-218X(90)90131-U
he, 1986, Efficient Parallel Algorithms for Solving Some Tree Problems, Proc 24th Allerton Conf Communication Control and Computing, 777
10.1093/qmath/28.4.417
10.1142/S0129626499000074
10.1007/3-540-49164-3_40
10.1006/jagm.1999.1064
10.1007/3-540-49381-6_28
10.1016/B978-0-444-88071-0.50022-9
livingston, 1990, Perfect Dominating Sets, Congressus Numerantium, 79, 187
10.1016/0166-218X(94)00067-3
lu, 1996, Efficient Domination on Bipartite Graphs
10.1016/0020-0190(93)90100-N
10.1002/(SICI)1097-0037(199805)31:3<177::AID-NET4>3.0.CO;2-C
nicolai, 1994, Hamiltonian Problems on Distance-Hereditary Graphs
10.1016/0020-0190(93)90147-2