Optimal parallel algorithms for sparse graphs

dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Σπυράκης, Παύλος	el
dc.contributor.author	Ζαρολιάγκης, Χρήστος	el
dc.date.accessioned	2015-05-29T19:48:20Z
dc.date.issued	2015-05-29
dc.identifier.uri	http://hdl.handle.net/11400/11913
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/us/	*
dc.source	http://link.springer.com/chapter/10.1007/3-540-53832-1_27	en
dc.subject	παράλληλοι αλγόριθμοι
dc.subject	αραιά γραφήματα
dc.subject	επεξεργαστές
dc.subject	επίπεδα γραφήματα
dc.subject	μέγιστος χρωματισμός
dc.subject	μέγιστο ανεξάρτητο σύνολο
dc.subject	Parallel algorithms
dc.subject	sparse graphs
dc.subject	processors
dc.subject	planar graphs
dc.subject	maximal coloring
dc.subject	maximal independent set
dc.title	Optimal parallel algorithms for sparse graphs	en
heal.type	conferenceItem
heal.classification	Επιστήμες
heal.classification	Πληροφορική
heal.classification	Science
heal.classification	Computer science
heal.classificationURI	N/A-Επιστήμες
heal.classificationURI	N/A-Πληροφορική
heal.classificationURI	http://skos.um.es/unescothes/C03532
heal.classificationURI	http://skos.um.es/unescothes/C00750
heal.keywordURI	http://id.loc.gov/authorities/subjects/sh98003394
heal.identifier.secondary	DOI: 10.1007/3-540-53832-1_27
heal.dateAvailable	10000-01-01
heal.language	en
heal.access	forever
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1991-06-20
heal.bibliographicCitation	Pantziou, G., Spirakis, P. and Zaroliagis, C. (1991) Optimal parallel algorithms for sparse graphs. Proceedings of the 16th International Workshop WG '90. 484, pp.1-17. Berlin, Germany: Springer Berlin Heidelberg	en
heal.abstract	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
heal.publisher	Springer Berlin Heidelberg	en
heal.fullTextAvailability	false
heal.conferenceName	Proceedings of the 16th International Workshop WG '90	en
heal.conferenceItemType	full paper