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(log2 n) time and n/log2 n 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).
(EN)
Proceedings of the 16th International Workshop WG '90
(EN)
