Parallel algorithms for the minimum cut and the minimum length 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-25T19:10:11Z
dc.date.available	2015-05-25T19:10:11Z
dc.date.issued	2015-05-25
dc.identifier.uri	http://hdl.handle.net/11400/11147
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/S0304397596002745	en
dc.subject	Παράλληλοι αλγόριθμοι
dc.subject	προβλήματα διάταξης δέντρου
dc.subject	γενικές γραφήματα
dc.subject	ελάχιστο μήκος γραμμικής διάταξης
dc.subject	ελάχιστη περικοπή
dc.subject	Parallel algorithms
dc.subject	tree layout problems
dc.subject	general graphs
dc.subject	minimum length linear arrangement
dc.subject	minimum cut
dc.title	Parallel algorithms for the minimum cut and the minimum length tree layout problems	en
heal.type	journalArticle
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.keywordURI	http://id.loc.gov/authorities/subjects/sh98003394
heal.contributorName	Toran, Jacobo	en
heal.identifier.secondary	DOI: 10.1016/S0304-3975(96)00274-5
heal.language	en
heal.access	free
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1997-07-30
heal.bibliographicCitation	Diaz, J., Gibbons, A., Pantziou, G., Serna, M. and Spirakis, P. (1997) Parallel algorithms for the minimum cut and the minimum length tree layout problems. Theoretical Computer Science. [Online] 181 (2). pp.267-287. Available from: http://www.sciencedirect.com [Accessed 25/05/2015]	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 is in NC for bounded degree trees. To the best of our knowledge, these are the first parallel algorithms for the minimum length and the minimum cut linear arrangement problems.	en
heal.publisher	Elsevier	en
heal.journalName	Theoretical Computer Science	en
heal.journalType	peer-reviewed
heal.fullTextAvailability	true