Conflict-free sorting algorithms under single-channel and multi-channel broadcast communication models View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1991

AUTHORS

Chang-Biau Yang , R. C. T. Lee , Wen-Tsuen Chen

ABSTRACT

In this paper, we shall first propose an optimal conflict-free parallel sorting algorithm under the single-channel broadcast communication model. The time complexity of this algorithm is O((n/p)log(n/p)+n) if p processors are used to sort n data elements. We then apply our single-channel sorting algorithm to improve the multi-channel sorting algorithm proposed by Marberg and Gafni. Since there is a constraint for the Marberg and Gafni's algorithm, we shall propose another conflict-free multi-channel sorting algorithm without this constraint. The time complexity of this algorithm is O((n/p)log(n/p)+(n/k)log2k) if there are n data elements to be sorted by using p processors with k channels. More... »

PAGES

350-359

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-54029-6_183

DOI

http://dx.doi.org/10.1007/3-540-54029-6_183

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1011806861


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan 80424, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.412036.2", 
          "name": [
            "Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan 80424, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yang", 
        "givenName": "Chang-Biau", 
        "id": "sg:person.013201414347.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013201414347.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lee", 
        "givenName": "R. C. T.", 
        "id": "sg:person.07540250215.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.38348.34", 
          "name": [
            "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Wen-Tsuen", 
        "id": "sg:person.011630052612.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011630052612.15"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1991", 
    "datePublishedReg": "1991-01-01", 
    "description": "In this paper, we shall first propose an optimal conflict-free parallel sorting algorithm under the single-channel broadcast communication model. The time complexity of this algorithm is O((n/p)log(n/p)+n) if p processors are used to sort n data elements. We then apply our single-channel sorting algorithm to improve the multi-channel sorting algorithm proposed by Marberg and Gafni. Since there is a constraint for the Marberg and Gafni's algorithm, we shall propose another conflict-free multi-channel sorting algorithm without this constraint. The time complexity of this algorithm is O((n/p)log(n/p)+(n/k)log2k) if there are n data elements to be sorted by using p processors with k channels.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Fiala", 
        "givenName": "Frantisek", 
        "type": "Person"
      }, 
      {
        "familyName": "Koczkodaj", 
        "givenName": "Waldemar W.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-54029-6_183", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-54029-8", 
        "978-3-540-47359-6"
      ], 
      "name": "Advances in Computing and Information \u2014 ICCI '91", 
      "type": "Book"
    }, 
    "keywords": [
      "broadcast communication model", 
      "sorting algorithm", 
      "time complexity", 
      "communication model", 
      "data elements", 
      "single-channel broadcast communication model", 
      "parallel sorting algorithm", 
      "algorithm", 
      "processors", 
      "complexity", 
      "constraints", 
      "Marberg", 
      "Gafni", 
      "model", 
      "channels", 
      "elements", 
      "paper", 
      "optimal conflict-free parallel sorting algorithm", 
      "conflict-free parallel sorting algorithm", 
      "multi-channel sorting algorithm", 
      "Gafni's algorithm", 
      "conflict-free multi-channel sorting algorithm", 
      "Conflict-free sorting algorithms", 
      "multi-channel broadcast communication models"
    ], 
    "name": "Conflict-free sorting algorithms under single-channel and multi-channel broadcast communication models", 
    "pagination": "350-359", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011806861"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-54029-6_183"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-54029-6_183", 
      "https://app.dimensions.ai/details/publication/pub.1011806861"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T19:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_144.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-54029-6_183"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-54029-6_183'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-54029-6_183'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-54029-6_183'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-54029-6_183'


 

This table displays all metadata directly associated to this object as RDF triples.

111 TRIPLES      23 PREDICATES      50 URIs      43 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-54029-6_183 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nbbccb73523ce448483b1ca3954b2a513
4 schema:datePublished 1991
5 schema:datePublishedReg 1991-01-01
6 schema:description In this paper, we shall first propose an optimal conflict-free parallel sorting algorithm under the single-channel broadcast communication model. The time complexity of this algorithm is O((n/p)log(n/p)+n) if p processors are used to sort n data elements. We then apply our single-channel sorting algorithm to improve the multi-channel sorting algorithm proposed by Marberg and Gafni. Since there is a constraint for the Marberg and Gafni's algorithm, we shall propose another conflict-free multi-channel sorting algorithm without this constraint. The time complexity of this algorithm is O((n/p)log(n/p)+(n/k)log2k) if there are n data elements to be sorted by using p processors with k channels.
7 schema:editor N9292e699cfb343bc97bcba32141b985f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nf20f52eee3c14a0189931979c32ea622
12 schema:keywords Conflict-free sorting algorithms
13 Gafni
14 Gafni's algorithm
15 Marberg
16 algorithm
17 broadcast communication model
18 channels
19 communication model
20 complexity
21 conflict-free multi-channel sorting algorithm
22 conflict-free parallel sorting algorithm
23 constraints
24 data elements
25 elements
26 model
27 multi-channel broadcast communication models
28 multi-channel sorting algorithm
29 optimal conflict-free parallel sorting algorithm
30 paper
31 parallel sorting algorithm
32 processors
33 single-channel broadcast communication model
34 sorting algorithm
35 time complexity
36 schema:name Conflict-free sorting algorithms under single-channel and multi-channel broadcast communication models
37 schema:pagination 350-359
38 schema:productId N1610aa1744f745d9b7bc575cb3de66be
39 N22693329d88749e29dd26b20b99ed835
40 schema:publisher N0a3550d4497d45479f8454d54e83c7f6
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011806861
42 https://doi.org/10.1007/3-540-54029-6_183
43 schema:sdDatePublished 2021-12-01T19:57
44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
45 schema:sdPublisher N11679b87ce9c437d8d29359ee4abfe4b
46 schema:url https://doi.org/10.1007/3-540-54029-6_183
47 sgo:license sg:explorer/license/
48 sgo:sdDataset chapters
49 rdf:type schema:Chapter
50 N0a3550d4497d45479f8454d54e83c7f6 schema:name Springer Nature
51 rdf:type schema:Organisation
52 N11679b87ce9c437d8d29359ee4abfe4b schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N123db3100f534c63a660cb3fc95d3bdd rdf:first N91998601346641b38cd4833227ac0080
55 rdf:rest N6b32a74927b74427bf12ff1c8552995a
56 N1610aa1744f745d9b7bc575cb3de66be schema:name dimensions_id
57 schema:value pub.1011806861
58 rdf:type schema:PropertyValue
59 N22693329d88749e29dd26b20b99ed835 schema:name doi
60 schema:value 10.1007/3-540-54029-6_183
61 rdf:type schema:PropertyValue
62 N6445802b78d94ce5a76fca45c73d8600 schema:familyName Dehne
63 schema:givenName Frank
64 rdf:type schema:Person
65 N6b32a74927b74427bf12ff1c8552995a rdf:first Nf9ef94d786bb40b2b476025c4cd59b83
66 rdf:rest rdf:nil
67 N7fe23b487afd469f90333517899f6c1f rdf:first sg:person.07540250215.50
68 rdf:rest Nd176ef2552294dc2b00ded510014f322
69 N91998601346641b38cd4833227ac0080 schema:familyName Fiala
70 schema:givenName Frantisek
71 rdf:type schema:Person
72 N9292e699cfb343bc97bcba32141b985f rdf:first N6445802b78d94ce5a76fca45c73d8600
73 rdf:rest N123db3100f534c63a660cb3fc95d3bdd
74 Nbbccb73523ce448483b1ca3954b2a513 rdf:first sg:person.013201414347.02
75 rdf:rest N7fe23b487afd469f90333517899f6c1f
76 Nd176ef2552294dc2b00ded510014f322 rdf:first sg:person.011630052612.15
77 rdf:rest rdf:nil
78 Nf20f52eee3c14a0189931979c32ea622 schema:isbn 978-3-540-47359-6
79 978-3-540-54029-8
80 schema:name Advances in Computing and Information — ICCI '91
81 rdf:type schema:Book
82 Nf9ef94d786bb40b2b476025c4cd59b83 schema:familyName Koczkodaj
83 schema:givenName Waldemar W.
84 rdf:type schema:Person
85 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
86 schema:name Information and Computing Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
89 schema:name Artificial Intelligence and Image Processing
90 rdf:type schema:DefinedTerm
91 sg:person.011630052612.15 schema:affiliation grid-institutes:grid.38348.34
92 schema:familyName Chen
93 schema:givenName Wen-Tsuen
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011630052612.15
95 rdf:type schema:Person
96 sg:person.013201414347.02 schema:affiliation grid-institutes:grid.412036.2
97 schema:familyName Yang
98 schema:givenName Chang-Biau
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013201414347.02
100 rdf:type schema:Person
101 sg:person.07540250215.50 schema:affiliation grid-institutes:grid.38348.34
102 schema:familyName Lee
103 schema:givenName R. C. T.
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50
105 rdf:type schema:Person
106 grid-institutes:grid.38348.34 schema:alternateName Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, Republic of China
107 schema:name Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, Republic of China
108 rdf:type schema:Organization
109 grid-institutes:grid.412036.2 schema:alternateName Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan 80424, Republic of China
110 schema:name Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan 80424, Republic of China
111 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...