Name
Abstract | ||
|---|---|---|
In this paper, we consider parallelizability of some P-complete problems. First we propose a parameter which indicates parallelizability for a convex layers problem. We prove P-completeness of the problem and propose a cost optimal parallel algorithm, according to the parameter. Second we consider a lexicographically first maximal 3 sums problem. We prove P-completeness of the problem by reducing a lexicographically first maximal independent set problem, and propose two cost optimal parallel algorithms for related problems. The above results show that some P-complete problems have efficient cost optimal parallel algorithms. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/3-540-45591-4_14 | IPDPS Workshops |
Keywords | Field | DocType |
efficient cost optimal parallel,convex layers problem,sums problem,cost optimal parallel algorithm,p-complete problems,related problem,p-complete problem,maximal independent set problem,parallel algorithm,maximal independent set | Mathematical optimization,Computer science,Parallel algorithm,Neighbourhood (graph theory),Algorithm,P-complete,Convex hull,Regular polygon,Lexicographical order,Sequential algorithm,Maximal independent set | Conference |
Volume | ISSN | ISBN |
1800 | 0302-9743 | 3-540-67442-X |
Citations | PageRank | References |
2 | 0.38 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Akihiro Fujiwara | 1 | 122 | 27.25 |
| Michiko Inoue | 2 | 24 | 3.56 |
| Toshimitsu Masuzawa | 3 | 635 | 91.06 |