Details

Autor(en) / Beteiligte

• Pantziou, Grammati E.
• Spirakis, Paul G.
• Zaroliagis, Christos D.

Titel

Optimal parallel algorithms for sparse graphs

Ist Teil von

• Graph-Theoretic Concepts in Computer Science, 2005, p.1-17

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2005

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• We present here techniques which exhibit optimal processor-time tradeoff for many important problems on sparse graphs. These problems include: maximal coloring and maximal independent set in trees and bounded degree graphs; 7-colorability, maximal independent set and maximal matching in planar graphs; maximum independent set, maximum matching and Hamiltonian path on rectangular grid graphs. Our techniques are based on the general list ranking problem: given k lists having a total of n elements, find for each element the membership relation and the rank of the element in its list. We solve this problem in O(log n) time with n/log n processors on an EREW PRAM. For trees and bounded degree graphs our methods need O(log n) time and n/log n processors on an EREW PRAM. For planar graphs they need O(log2n) time and n/log2n processors on an EREW PRAM using linear space. For the case of rectangular grid graphs they need O(log n) time with n/log n processors on a CRCW PRAM, or on an EREW PRAM (if the embedding is given).