Hammock-on-ears decomposition

dc.contributor.author	Καββαδίας, Δημήτριος	el
dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Σπυράκης, Παύλος	el
dc.contributor.author	Ζαρολιάγκης, Χρήστος	el
dc.date.accessioned	2015-05-25T19:28:14Z
dc.date.available	2015-05-25T19:28:14Z
dc.date.issued	2015-05-25
dc.identifier.uri	http://hdl.handle.net/11400/11150
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/us/	*
dc.source	http://www.sciencedirect.com/science/article/pii/S0304397596000655	en
dc.subject	Αιώρα
dc.subject	παράλληλα τεχνική αποσύνθεσης αυτιού
dc.subject	γράφημα
dc.subject	δίγραμμα
dc.subject	Hammock
dc.subject	parallel ear decomposition technique
dc.subject	graph
dc.subject	digraph
dc.title	Hammock-on-ears decomposition	en
heal.type	journalArticle
heal.secondaryTitle	a technique for the efficient parallel solution of shortest paths and other problems	en
heal.classification	Τεχνολογία
heal.classification	Πληροφορική
heal.classification	Technology
heal.classification	Computer science
heal.classificationURI	N/A-Τεχνολογία
heal.classificationURI	N/A-Πληροφορική
heal.classificationURI	http://id.loc.gov/authorities/subjects/sh85133147
heal.classificationURI	http://skos.um.es/unescothes/C00750
heal.identifier.secondary	DOI: 10.1016/S0304-3975(96)00065-5
heal.language	en
heal.access	free
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1996-11-10
heal.bibliographicCitation	Kavvadias, D., Pantziou, G., Spirakis, P. and Zaroliagis, C. (1996) Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems. Theoretical Computer Science. [Online] 168 (1). pp.121-154. Available from: http://www.sciencedirect.com [Accessed 25/05/2015]	en
heal.abstract	We show how to decompose efficiently in parallel any graph into a number, gg, of outerplanar subgraphs (called hammocks) satisfying certain separator properties. Our work combines and extends the sequential hammock decomposition technique introduced by Frederickson and the parallel ear decomposition technique, thus we call it the hammock-on-ears decomposition. We mention that hammock-on-ears decomposition also draws from techniques in computational geometry and that an embedding of the graph does not need to be provided with the input. We achieve this decomposition in O(lognloglogn) time using O(n + m) CREW PRAM processors, for an n-vertex, m-edge graph or digraph. The hammock-on-ears decomposition implies a general framework for solving graph problems efficiently. Its value is demonstrated by a variety of applications on a significant class of graphs, namely that of sparse (di)graphs. This class consists of all (di)graphs which have a gg between 1 and Θ(n), and includes planar graphs and graphs with genus o(n). We improve previous bounds for certain instances of shortest paths and related problems, in this class of graphs. These problems include all pairs shortest paths, all pairs reachability, and detection of a negative cycle.	en
heal.publisher	Elsevier	en
heal.journalName	Theoretical Computer Science	en
heal.journalType	peer-reviewed
heal.fullTextAvailability	true