TY - JOUR

T1 - Characterization of efficiently parallel solvable problems on distance-hereditary graphs

AU - Hsieh, Sun Yuan

AU - Ho, Chin Wen

AU - Hsu, Tsan Sheng

AU - Ko, Ming Tat

AU - Chen, Gen Huey

PY - 2002/7

Y1 - 2002/7

N2 - In this paper, we sketch common properties of a class of so-called subgraph optimization problems that can be systematically solved on distance-hereditary graphs. Based on the found properties, we then develop a general problem-solving paradigm that solves these problems efficiently in parallel. As a by-product, we also obtain new linear-time algorithms by a sequential simulation of our parallel algorithms. Let Td(|V|, |E|) and Pd(|V|, |E|) denote the time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G = (V, E) on a PRAM model Md. Based on the proposed paradigm, we show that the maximum independent set problem, the maximum clique problem, the vertex connectivity problem, the domination problem, and the independent domination problem can be sequentially solved in O(|V| + |E|) time, and solved in parallel in O(Td(|V|, |E|) + log |V|) time using O(Pd(|V|, |E|) + |V|/log |V|) processors on Md. By constructing a decomposition tree under a CREW PRAM, we also show that Td(|V|, |E|) = O(log2 |V|) and Pd(|V|, |E|) = O(|V| + |E|).

AB - In this paper, we sketch common properties of a class of so-called subgraph optimization problems that can be systematically solved on distance-hereditary graphs. Based on the found properties, we then develop a general problem-solving paradigm that solves these problems efficiently in parallel. As a by-product, we also obtain new linear-time algorithms by a sequential simulation of our parallel algorithms. Let Td(|V|, |E|) and Pd(|V|, |E|) denote the time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G = (V, E) on a PRAM model Md. Based on the proposed paradigm, we show that the maximum independent set problem, the maximum clique problem, the vertex connectivity problem, the domination problem, and the independent domination problem can be sequentially solved in O(|V| + |E|) time, and solved in parallel in O(Td(|V|, |E|) + log |V|) time using O(Pd(|V|, |E|) + |V|/log |V|) processors on Md. By constructing a decomposition tree under a CREW PRAM, we also show that Td(|V|, |E|) = O(log2 |V|) and Pd(|V|, |E|) = O(|V| + |E|).

KW - Algorithms

KW - Data structures

KW - Distance-hereditary graphs

KW - Parallel random access machine

KW - Subgraph optimization problems

UR - http://www.scopus.com/inward/record.url?scp=0036662508&partnerID=8YFLogxK

U2 - 10.1137/S0895480101389880

DO - 10.1137/S0895480101389880

M3 - 期刊論文

AN - SCOPUS:0036662508

SN - 0895-4801

VL - 15

SP - 488

EP - 518

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 4

ER -