Academic Journal
DISTRIBUTED-MEMORY PARALLEL ALGORITHMS FOR DISTANCE-2 COLORING AND THEIR APPLICATION TO DERIVATIVE COMPUTATION
| العنوان: | DISTRIBUTED-MEMORY PARALLEL ALGORITHMS FOR DISTANCE-2 COLORING AND THEIR APPLICATION TO DERIVATIVE COMPUTATION |
|---|---|
| المؤلفون: | Doruk Bozdag, Assefaw H. Gebremedhin, Fredrik Manne, Erik G. Boman, Füsun Özgüner |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | http://www.sandia.gov/~egboman/papers/d2coloring-SISC.pdf. |
| سنة النشر: | 2010 |
| المجموعة: | CiteSeerX |
| الوصف: | The distance-2 graph coloring problem aims at partitioning the vertex set of a graph into the fewest sets consisting of vertices pairwise at distance greater than two from each other. Its applications include derivative computation in numerical optimization and channel assignment in radio networks. We present efficient, distributed-memory, parallel heuristic algorithms for this NP-hard problem as well as for two related problems used in the computation of Jacobians and Hessians. Parallel speedup is achieved through graph partitioning, speculative (iterative) coloring, and a BSP-like organization of parallel computation. Results from experiments conducted on a PC cluster employing up to 96 processors and using large-size real-world as well as synthetically generated test graphs show that the algorithms are scalable. In terms of quality of solution, the algorithms perform remarkably well—the number of colors used by the parallel algorithms was observed to be very close to the number used by the sequential counterparts, which in turn are quite often near optimal. Moreover, the experimental results show that the parallel distance-2 coloring algorithm compares favorably with the alternative approach of solving the distance-2 coloring problem on a graph G by first constructing the square graph G² and then applying a parallel distance-1 coloring algorithm on G2. Implementations of the algorithms are made available via the Zoltan load-balancing library. |
| نوع الوثيقة: | text |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.216.4122; http://www.sandia.gov/~egboman/papers/d2coloring-SISC.pdf |
| الاتاحة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.216.4122 http://www.sandia.gov/~egboman/papers/d2coloring-SISC.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.CFD7F9FC |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |