1. Αρχική σελίδα
  2. Αναζήτηση

Optimal parallel algorithms for sparse graphs

Το τεκμήριο παρέχεται από τον φορέα :
ΤΕΙ Αθήνας   

Αποθετήριο :
Υπατία - Ιδρυματικό Αποθετήριο   

δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*



Optimal parallel algorithms for sparse graphs (EN)
Σπυράκης, Παύλος (EL)
Ζαρολιάγκης, Χρήστος (EL)
Πάντζιου, Γραμματή Ε. (EL)
full paper
conferenceItem
2015-05-29T19:48:20Z
2015-05-29
1991-06-20
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)
Proceedings of the 16th International Workshop WG '90 (EN)
maximal coloring
**N/A**-Πληροφορική
αραιά γραφήματα
sparse graphs
planar graphs
maximal independent set
Science
http://skos.um.es/unescothes/C03532
http://skos.um.es/unescothes/C00750
processors
επίπεδα γραφήματα
Parallel algorithms
http://id.loc.gov/authorities/subjects/sh98003394
Πληροφορική
Computer science
επεξεργαστές
**N/A**-Επιστήμες
παράλληλοι αλγόριθμοι
Επιστήμες
μέγιστος χρωματισμός
μέγιστο ανεξάρτητο σύνολο
Springer Berlin Heidelberg (EN)
Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε. (EL)
http://link.springer.com/chapter/10.1007/3-540-53832-1_27
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες
http://creativecommons.org/licenses/by-nc-nd/3.0/us/
forever
ΤΕΙ Αθήνας
Υπατία - Ιδρυματικό Αποθετήριο
Δημοσιεύσεις



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.