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-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"
          }, 
          {
            "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"
          }
        ], 
        "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": "2021-11-01T18:02", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/article/article_299.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 N36987bf5caf142c3ae3bb476598c1845
    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 Nbc9074649a3d4474a93d6f10671c4c34
    14 Nf6972e92c508496b978f1c7a089023d2
    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 Nadb5424cd0fc41cd8a6da5f69b4d797d
    45 Nb1c3043bb5244973b16ff2d004701d22
    46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025028196
    47 https://doi.org/10.1007/bf01955675
    48 schema:sdDatePublished 2021-11-01T18:02
    49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    50 schema:sdPublisher N61afd950fcf2461ab6314c7e151aebf5
    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 N36987bf5caf142c3ae3bb476598c1845 rdf:first sg:person.07401535357.26
    56 rdf:rest Ndc18d48386d7475bb5e4afaae0840a26
    57 N61afd950fcf2461ab6314c7e151aebf5 schema:name Springer Nature - SN SciGraph project
    58 rdf:type schema:Organization
    59 Nadb5424cd0fc41cd8a6da5f69b4d797d schema:name doi
    60 schema:value 10.1007/bf01955675
    61 rdf:type schema:PropertyValue
    62 Nb1c3043bb5244973b16ff2d004701d22 schema:name dimensions_id
    63 schema:value pub.1025028196
    64 rdf:type schema:PropertyValue
    65 Nbc9074649a3d4474a93d6f10671c4c34 schema:issueNumber 3
    66 rdf:type schema:PublicationIssue
    67 Ndc18d48386d7475bb5e4afaae0840a26 rdf:first sg:person.011352641523.42
    68 rdf:rest rdf:nil
    69 Nf6972e92c508496b978f1c7a089023d2 schema:volumeNumber 16
    70 rdf:type schema:PublicationVolume
    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)


    ...