Efficient parallel algorithms for some tree layout problems

dc.contributor.author	Díaz, Josep	en
dc.contributor.author	Gibbons, Alan	en
dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Serna, Maria J.	en
dc.contributor.author	Σπυράκης, Παύλος	el
dc.date.accessioned	2015-05-28T20:44:48Z
dc.date.available	2015-05-28T20:44:48Z
dc.date.issued	2015-05-28
dc.identifier.uri	http://hdl.handle.net/11400/11479
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/BFb0030846	el
dc.subject	παράλληλοι αλγόριθμοι
dc.subject	προβλήματα καλωδίωσης
dc.subject	ελάχιστη περικοπή
dc.subject	ελάχιστο γραμμικό μήκος
dc.subject	Parallel algorithms
dc.subject	wiring problems
dc.subject	minimum cut
dc.subject	minimum length
dc.title	Efficient parallel algorithms for some tree layout problems	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.contributorName	Toran, Jacobo	en
heal.identifier.secondary	DOI: 10.1007/BFb0030846
heal.language	en
heal.access	campus
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1995-08-24
heal.bibliographicCitation	Diaz, J., Gibbons, A., Pantziou, G., Serna, M. and Spirakis, P. (1995) Efficient parallel algorithms for some tree layout problems. Proceedings of the First Annual International Conference, COCOON '95. 959, pp.313-323. Xi'an, China: Springer Berlin Heidelberg	en
heal.abstract	The minimum cut and minimum length linear arrangement problems usually occur in solving wiring problems and have a lot in common with job sequencing questions. Both problems are NP-complete for general graphs and in P for trees. We present here two parallel algorithms for the CREW PRAM. The first solves the minimum length linear arrangement problem for trees and the second solves the minimum cut arrangement for trees. We prove that the first problem belongs to NC for trees, and the second problem also is in NC for bounded degree trees.	en
heal.publisher	Springer Berlin Heidelberg	en
heal.fullTextAvailability	true
heal.conferenceName	Proceedings of the First Annual International Conference, COCOON '95	en
heal.conferenceItemType	full paper