Classifying matrices separating rows and columns (Articolo in rivista)

Type
Label
  • Classifying matrices separating rows and columns (Articolo in rivista) (literal)
Anno
  • 2004-01-01T00:00:00+01:00 (literal)
Alternative label
  • Bertossi A.A.; Olariu S.; Pinotti M.C.; Zheng S.Q. (2004)
    Classifying matrices separating rows and columns
    in IEEE transactions on parallel and distributed systems (Print)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Bertossi A.A.; Olariu S.; Pinotti M.C.; Zheng S.Q. (literal)
Pagina inizio
  • 654 (literal)
Pagina fine
  • 665 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 15-7 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note
  • IEEE, 2004. (literal)
Note
  • ISI Web of Science (WOS) (literal)
Titolo
  • Classifying matrices separating rows and columns (literal)
Abstract
  • The classification problem transforms a set of N numbers in such a way that none of the first N/2 numbers exceeds any of the last N/2 numbers. A comparator network that solves the classification problem on a set of r numbers is commonly called an r-classifier. We show how the well-known Leighton's Columnsort algorithm can be modified to solve the classification problem of N=rs numbers, with 1 /spl les/ s /spl les/ r, using an r-classifier instead of an r-sorting network. Overall, the r-classifier is used O(s) times, namely, the same number of times that Columnsort applies an r-sorter. A hardware implementation is proposed that runs in optimal O(s+logr) time and uses an O(rlogr(s + logr)) work. The implementation shows that, when N= rlogr, there is a classifier network solving the classification problem on N numbers in the same O(logr) time and using the same O(rlogr) comparators as an r-classifier, thus saying a logr factor in the number of comparators over an (rlogr)-classifier. (literal)
Prodotto di

Incoming links:


Prodotto
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
data.CNR.it