An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1996-09

AUTHORS

S. Sunder, Xin He

ABSTRACT

We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takesO(log2n) time withO(n3) processors on a CREW PRAM, wheren is the number of vertices of the input graph. This is the first NC algorithm for solving the problem.

PAGES

243-262

References to SciGraph publications

  • 1989. Using bounded degree spanning trees in the design of efficient algorithms on claw-free graphs in ALGORITHMS AND DATA STRUCTURES
  • 1986. Two processor scheduling is in NC in VLSI ALGORITHMS AND ARCHITECTURES
  • 1991. A parallel algorithm for two processors precedence constraint scheduling in AUTOMATA, LANGUAGES AND PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01955675

    DOI

    http://dx.doi.org/10.1007/bf01955675

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer and Information Sciences, University of Delaware, 19716, Newark, DE, USA", 
              "id": "http://www.grid.ac/institutes/grid.33489.35", 
              "name": [
                "Department of Computer and Information Sciences, University of Delaware, 19716, Newark, DE, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sunder", 
            "givenName": "S.", 
            "id": "sg:person.07401535357.26", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07401535357.26"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA", 
              "id": "http://www.grid.ac/institutes/grid.273335.3", 
              "name": [
                "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "He", 
            "givenName": "Xin", 
            "id": "sg:person.011352641523.42", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-51542-9_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038622667", 
              "https://doi.org/10.1007/3-540-51542-9_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-54233-7_152", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030231156", 
              "https://doi.org/10.1007/3-540-54233-7_152"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-16766-8_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022250213", 
              "https://doi.org/10.1007/3-540-16766-8_2"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1996-09", 
        "datePublishedReg": "1996-09-01", 
        "description": "We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takesO(log2n) time withO(n3) processors on a CREW PRAM, wheren is the number of vertices of the input graph. This is the first NC algorithm for solving the problem.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf01955675", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "16"
          }
        ], 
        "keywords": [
          "series parallel graphs", 
          "parallel graphs", 
          "NC algorithm", 
          "time scheduling problem", 
          "parallel algorithm", 
          "first NC algorithm", 
          "scheduling problem", 
          "input graph", 
          "CREW PRAM", 
          "number of vertices", 
          "algorithm", 
          "graph", 
          "processors", 
          "PRAM", 
          "time schedule", 
          "vertices", 
          "wheren", 
          "schedule", 
          "number", 
          "time", 
          "problem", 
          "minimum weighted completion time scheduling problem", 
          "weighted completion time scheduling problem", 
          "completion time scheduling problem", 
          "transitive series parallel graphs", 
          "completion time schedule"
        ], 
        "name": "An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs", 
        "pagination": "243-262", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1025028196"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01955675"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01955675", 
          "https://app.dimensions.ai/details/publication/pub.1025028196"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T18:08", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_295.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf01955675"
      }
    ]
     

    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/bf01955675'

    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/bf01955675'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01955675'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01955675'


     

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

    106 TRIPLES      22 PREDICATES      55 URIs      44 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01955675 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N7f19c32e59b84ebea233c6168ff71d26
    4 schema:citation sg:pub.10.1007/3-540-16766-8_2
    5 sg:pub.10.1007/3-540-51542-9_13
    6 sg:pub.10.1007/3-540-54233-7_152
    7 schema:datePublished 1996-09
    8 schema:datePublishedReg 1996-09-01
    9 schema:description We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takesO(log2n) time withO(n3) processors on a CREW PRAM, wheren is the number of vertices of the input graph. This is the first NC algorithm for solving the problem.
    10 schema:genre article
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf N0ba4c90116d246e48d368a1f949d7853
    14 Nb93f61f64d524bbc8e4f281babc5223e
    15 sg:journal.1047644
    16 schema:keywords CREW PRAM
    17 NC algorithm
    18 PRAM
    19 algorithm
    20 completion time schedule
    21 completion time scheduling problem
    22 first NC algorithm
    23 graph
    24 input graph
    25 minimum weighted completion time scheduling problem
    26 number
    27 number of vertices
    28 parallel algorithm
    29 parallel graphs
    30 problem
    31 processors
    32 schedule
    33 scheduling problem
    34 series parallel graphs
    35 time
    36 time schedule
    37 time scheduling problem
    38 transitive series parallel graphs
    39 vertices
    40 weighted completion time scheduling problem
    41 wheren
    42 schema:name An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs
    43 schema:pagination 243-262
    44 schema:productId N01e61eff5663429eb365d77398b808fa
    45 N82312a7e08344fc585b14bc50787a02f
    46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025028196
    47 https://doi.org/10.1007/bf01955675
    48 schema:sdDatePublished 2022-01-01T18:08
    49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    50 schema:sdPublisher Nee75c1f4a8a84134888cab82477ae061
    51 schema:url https://doi.org/10.1007/bf01955675
    52 sgo:license sg:explorer/license/
    53 sgo:sdDataset articles
    54 rdf:type schema:ScholarlyArticle
    55 N01e61eff5663429eb365d77398b808fa schema:name dimensions_id
    56 schema:value pub.1025028196
    57 rdf:type schema:PropertyValue
    58 N0ba4c90116d246e48d368a1f949d7853 schema:issueNumber 3
    59 rdf:type schema:PublicationIssue
    60 N7f19c32e59b84ebea233c6168ff71d26 rdf:first sg:person.07401535357.26
    61 rdf:rest Ndba6e71d2ece4730a33f40239a74069d
    62 N82312a7e08344fc585b14bc50787a02f schema:name doi
    63 schema:value 10.1007/bf01955675
    64 rdf:type schema:PropertyValue
    65 Nb93f61f64d524bbc8e4f281babc5223e schema:volumeNumber 16
    66 rdf:type schema:PublicationVolume
    67 Ndba6e71d2ece4730a33f40239a74069d rdf:first sg:person.011352641523.42
    68 rdf:rest rdf:nil
    69 Nee75c1f4a8a84134888cab82477ae061 schema:name Springer Nature - SN SciGraph project
    70 rdf:type schema:Organization
    71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Information and Computing Sciences
    73 rdf:type schema:DefinedTerm
    74 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Computation Theory and Mathematics
    76 rdf:type schema:DefinedTerm
    77 sg:journal.1047644 schema:issn 0178-4617
    78 1432-0541
    79 schema:name Algorithmica
    80 schema:publisher Springer Nature
    81 rdf:type schema:Periodical
    82 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
    83 schema:familyName He
    84 schema:givenName Xin
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
    86 rdf:type schema:Person
    87 sg:person.07401535357.26 schema:affiliation grid-institutes:grid.33489.35
    88 schema:familyName Sunder
    89 schema:givenName S.
    90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07401535357.26
    91 rdf:type schema:Person
    92 sg:pub.10.1007/3-540-16766-8_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022250213
    93 https://doi.org/10.1007/3-540-16766-8_2
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/3-540-51542-9_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038622667
    96 https://doi.org/10.1007/3-540-51542-9_13
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/3-540-54233-7_152 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030231156
    99 https://doi.org/10.1007/3-540-54233-7_152
    100 rdf:type schema:CreativeWork
    101 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
    102 schema:name Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
    103 rdf:type schema:Organization
    104 grid-institutes:grid.33489.35 schema:alternateName Department of Computer and Information Sciences, University of Delaware, 19716, Newark, DE, USA
    105 schema:name Department of Computer and Information Sciences, University of Delaware, 19716, Newark, DE, USA
    106 rdf:type schema:Organization
     




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


    ...