Name
Title | ||
|---|---|---|
Characterization of Efficiently Parallel Solvable Problems on Distance-Hereditary Graphs |
Abstract | ||
|---|---|---|
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|). |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1137/S0895480101389880 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
parallel algorithm,so-called subgraph optimization problem,maximum independent set problem,distance-hereditary graph,distance-hereditary graphs,subgraph optimization problems,data structures,maximum clique problem,crew pram,domination problem,independent domination problem,algorithms,parallel random access machine,efficiently parallel solvable problems,decomposition tree,vertex connectivity problem,maximum independent set,data structure,optimization problem | Graph theory,Discrete mathematics,Combinatorics,Parallel random-access machine,Parallel algorithm,Independent set,Time complexity,Optimization problem,Mathematics,Clique problem,Computational complexity theory | Journal |
Volume | Issue | ISSN |
15 | 4 | 0895-4801 |
Citations | PageRank | References |
6 | 0.49 | 17 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sun-Yuan Hsieh | 1 | 1715 | 112.85 |
| Chin-Wen Ho | 2 | 573 | 39.27 |
| Tsan-sheng Hsu | 3 | 737 | 101.00 |
| Ming-Tat Ko | 4 | 1320 | 103.71 |
| Gen-Huey Chen | 5 | 979 | 89.32 |