Efficient parallel algorithms forr-dominating set andp-center problems on trees View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1990-06

AUTHORS

Xin He, Yaacov Yesha

ABSTRACT

We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log2n log logn) time withn processors.

PAGES

129

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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 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"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer and Information Science, Ohio State University, 43210, Columbus, OH, USA", 
          "id": "http://www.grid.ac/institutes/grid.261331.4", 
          "name": [
            "Department of Computer and Information Science, Ohio State University, 43210, Columbus, OH, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yesha", 
        "givenName": "Yaacov", 
        "id": "sg:person.013530270751.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013530270751.05"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01581045", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017065901", 
          "https://doi.org/10.1007/bf01581045"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01762121", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029138284", 
          "https://doi.org/10.1007/bf01762121"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1990-06", 
    "datePublishedReg": "1990-06-01", 
    "description": "We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log2n log logn) time withn processors.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01840381", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "5"
      }
    ], 
    "keywords": [
      "efficient parallel algorithms", 
      "parallel algorithm", 
      "set problem", 
      "algorithm", 
      "processors", 
      "PRAM", 
      "trees", 
      "set", 
      "problem", 
      "ther-dominating set", 
      "thep-center problems", 
      "concurrent-read exclusive-write PRAM", 
      "exclusive-write PRAM", 
      "ther-dominating set problem", 
      "time withn processors", 
      "withn processors", 
      "andp-center problems"
    ], 
    "name": "Efficient parallel algorithms forr-dominating set andp-center problems on trees", 
    "pagination": "129", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011414946"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01840381"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01840381", 
      "https://app.dimensions.ai/details/publication/pub.1011414946"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-12-01T19:07", 
    "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/article/article_223.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01840381"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

93 TRIPLES      22 PREDICATES      45 URIs      35 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01840381 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ne68ef0976bcd4839a07aed3487eeff83
4 schema:citation sg:pub.10.1007/bf01581045
5 sg:pub.10.1007/bf01762121
6 schema:datePublished 1990-06
7 schema:datePublishedReg 1990-06-01
8 schema:description We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log2n log logn) time withn processors.
9 schema:genre article
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf Nc80b8849fe0449d3829c505ba1a39bd9
13 Nf0b2ed4e22734503a79da40945aed202
14 sg:journal.1047644
15 schema:keywords PRAM
16 algorithm
17 andp-center problems
18 concurrent-read exclusive-write PRAM
19 efficient parallel algorithms
20 exclusive-write PRAM
21 parallel algorithm
22 problem
23 processors
24 set
25 set problem
26 thep-center problems
27 ther-dominating set
28 ther-dominating set problem
29 time withn processors
30 trees
31 withn processors
32 schema:name Efficient parallel algorithms forr-dominating set andp-center problems on trees
33 schema:pagination 129
34 schema:productId N294d0f70bcc6405ea5911d9ed1a42e17
35 N6b144b94dcb04b0a9d2a66a169ecd2a9
36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011414946
37 https://doi.org/10.1007/bf01840381
38 schema:sdDatePublished 2021-12-01T19:07
39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
40 schema:sdPublisher N737f9653a133404cabb0cad2202b6286
41 schema:url https://doi.org/10.1007/bf01840381
42 sgo:license sg:explorer/license/
43 sgo:sdDataset articles
44 rdf:type schema:ScholarlyArticle
45 N294d0f70bcc6405ea5911d9ed1a42e17 schema:name doi
46 schema:value 10.1007/bf01840381
47 rdf:type schema:PropertyValue
48 N6b144b94dcb04b0a9d2a66a169ecd2a9 schema:name dimensions_id
49 schema:value pub.1011414946
50 rdf:type schema:PropertyValue
51 N737f9653a133404cabb0cad2202b6286 schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 Nc33dbd22852747e5b708e581465e5640 rdf:first sg:person.013530270751.05
54 rdf:rest rdf:nil
55 Nc80b8849fe0449d3829c505ba1a39bd9 schema:volumeNumber 5
56 rdf:type schema:PublicationVolume
57 Ne68ef0976bcd4839a07aed3487eeff83 rdf:first sg:person.011352641523.42
58 rdf:rest Nc33dbd22852747e5b708e581465e5640
59 Nf0b2ed4e22734503a79da40945aed202 schema:issueNumber 1-4
60 rdf:type schema:PublicationIssue
61 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
62 schema:name Information and Computing Sciences
63 rdf:type schema:DefinedTerm
64 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
65 schema:name Computation Theory and Mathematics
66 rdf:type schema:DefinedTerm
67 sg:journal.1047644 schema:issn 0178-4617
68 1432-0541
69 schema:name Algorithmica
70 schema:publisher Springer Nature
71 rdf:type schema:Periodical
72 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
73 schema:familyName He
74 schema:givenName Xin
75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
76 rdf:type schema:Person
77 sg:person.013530270751.05 schema:affiliation grid-institutes:grid.261331.4
78 schema:familyName Yesha
79 schema:givenName Yaacov
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013530270751.05
81 rdf:type schema:Person
82 sg:pub.10.1007/bf01581045 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017065901
83 https://doi.org/10.1007/bf01581045
84 rdf:type schema:CreativeWork
85 sg:pub.10.1007/bf01762121 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029138284
86 https://doi.org/10.1007/bf01762121
87 rdf:type schema:CreativeWork
88 grid-institutes:grid.261331.4 schema:alternateName Department of Computer and Information Science, Ohio State University, 43210, Columbus, OH, USA
89 schema:name Department of Computer and Information Science, Ohio State University, 43210, Columbus, OH, USA
90 rdf:type schema:Organization
91 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
92 schema:name Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
93 rdf:type schema:Organization
 




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


...