Fast parallel algorithms for coloring random graphs

dc.contributor.author	Kedem, Zvi M.	en
dc.contributor.author	Palem, Krishna V.	en
dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Σπυράκης, Παύλος	el
dc.contributor.author	Ζαρολιάγκης, Χρήστος	el
dc.date.accessioned	2015-05-29T19:33:02Z
dc.date.issued	2015-05-29
dc.identifier.uri	http://hdl.handle.net/11400/11908
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%2F3-540-55121-2_13	en
dc.subject	παράλληλοι αλγόριθμοι
dc.subject	τυχαίος χρωματισμός γραφημάτων
dc.subject	αλγόριθμοι γραφήματος
dc.subject	επεξεργαστές
dc.subject	Parallel algorithms
dc.subject	coloring random graphs
dc.subject	Graph algorithms
dc.subject	processors
dc.title	Fast parallel algorithms for coloring random 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.keywordURI	http://id.loc.gov/authorities/subjects/sh2002004605
heal.identifier.secondary	DOI: 10.1007/3-540-55121-2_13
heal.dateAvailable	10000-01-01
heal.language	en
heal.access	forever
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1991-06-17
heal.bibliographicCitation	Kedem, Z., Palem, K., Pantziou, G., Spirakis, P. and Zaroliagis, C. (1991) Fast parallel algorithms for coloring random graphs. Proceedings of the 17th International Workshop, WG '91. 570, pp.135-147. Fischbachau, Germany: Springer Berlin Heidelberg	en
heal.abstract	We improve here the expected performance of parallel algorithms for graph coloring. This is achieved through new adaptive techniques that may be useful for the average-case analysis of many graph algorithms. We apply our techniques to: the class G n,p of random graphs. We present a parallel algorithm which colors the graph with a number of colors at most twice its chromatic number and runs in time O(log4 n/ log log n) almost surely, for p = Ω((log(3) n)2/ log(2) n). The number of processors used is O(m) where m is the number of edges of the graph. the class of all k-colorable graphs, uniformly chosen. We present a parallel algorithm which actually constructs the coloring in expected parallel time O(log2 n), for constant k, by using O(m) processors on the average. This problem is not known to have a polynomial time algorithm in the worst case.	en
heal.publisher	Springer Berlin Heidelberg	en
heal.fullTextAvailability	false
heal.conferenceName	Proceedings of the 17th International Workshop, WG '91	el
heal.conferenceItemType	full paper