An efficient parallel algorithm for finding rectangular duals of plane triangular graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1995-06

AUTHORS

Xin He

ABSTRACT

We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takesO(log2n) time withO(n) processors on a CRCW PRAM, wheren is the number of vertices of the graph. More... »

PAGES

553-572

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01840403", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020471605", 
          "https://doi.org/10.1007/bf01840403"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02187706", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008881195", 
          "https://doi.org/10.1007/bf02187706"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02187705", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027312329", 
          "https://doi.org/10.1007/bf02187705"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01762117", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003139574", 
          "https://doi.org/10.1007/bf01762117"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1995-06", 
    "datePublishedReg": "1995-06-01", 
    "description": "We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takesO(log2n) time withO(n) processors on a CRCW PRAM, wheren is the number of vertices of the graph.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01189069", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "6", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "13"
      }
    ], 
    "keywords": [
      "efficient parallel algorithms", 
      "parallel algorithm", 
      "rectangular duals", 
      "NC algorithm", 
      "CRCW PRAM", 
      "number of vertices", 
      "algorithm", 
      "VLSI design", 
      "graph", 
      "processors", 
      "PRAM", 
      "applications", 
      "vertices", 
      "design", 
      "wheren", 
      "triangular graph", 
      "number", 
      "time", 
      "dual", 
      "problem", 
      "plane triangular graphs", 
      "floor-planning problems"
    ], 
    "name": "An efficient parallel algorithm for finding rectangular duals of plane triangular graphs", 
    "pagination": "553-572", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1028799691"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01189069"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01189069", 
      "https://app.dimensions.ai/details/publication/pub.1028799691"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-11-01T18:00", 
    "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_263.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01189069"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

96 TRIPLES      22 PREDICATES      52 URIs      40 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01189069 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N4acf9b18c3b44971857bd7f5f8eb4a27
4 schema:citation sg:pub.10.1007/bf01762117
5 sg:pub.10.1007/bf01840403
6 sg:pub.10.1007/bf02187705
7 sg:pub.10.1007/bf02187706
8 schema:datePublished 1995-06
9 schema:datePublishedReg 1995-06-01
10 schema:description We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takesO(log2n) time withO(n) processors on a CRCW PRAM, wheren is the number of vertices of the graph.
11 schema:genre article
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf Nc3c9dc5681eb43f997a658686b0234d2
15 Ncf71c85760894b03b01af3225d90de4b
16 sg:journal.1047644
17 schema:keywords CRCW PRAM
18 NC algorithm
19 PRAM
20 VLSI design
21 algorithm
22 applications
23 design
24 dual
25 efficient parallel algorithms
26 floor-planning problems
27 graph
28 number
29 number of vertices
30 parallel algorithm
31 plane triangular graphs
32 problem
33 processors
34 rectangular duals
35 time
36 triangular graph
37 vertices
38 wheren
39 schema:name An efficient parallel algorithm for finding rectangular duals of plane triangular graphs
40 schema:pagination 553-572
41 schema:productId N27bbb26da1d44d59b2aa7ea32935faa4
42 Nf4acb5b7a55d4a64bd86ce6daacffb96
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028799691
44 https://doi.org/10.1007/bf01189069
45 schema:sdDatePublished 2021-11-01T18:00
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher Nbce63972b4794b509c720f352f5a7e16
48 schema:url https://doi.org/10.1007/bf01189069
49 sgo:license sg:explorer/license/
50 sgo:sdDataset articles
51 rdf:type schema:ScholarlyArticle
52 N27bbb26da1d44d59b2aa7ea32935faa4 schema:name doi
53 schema:value 10.1007/bf01189069
54 rdf:type schema:PropertyValue
55 N4acf9b18c3b44971857bd7f5f8eb4a27 rdf:first sg:person.011352641523.42
56 rdf:rest rdf:nil
57 Nbce63972b4794b509c720f352f5a7e16 schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 Nc3c9dc5681eb43f997a658686b0234d2 schema:volumeNumber 13
60 rdf:type schema:PublicationVolume
61 Ncf71c85760894b03b01af3225d90de4b schema:issueNumber 6
62 rdf:type schema:PublicationIssue
63 Nf4acb5b7a55d4a64bd86ce6daacffb96 schema:name dimensions_id
64 schema:value pub.1028799691
65 rdf:type schema:PropertyValue
66 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
67 schema:name Information and Computing Sciences
68 rdf:type schema:DefinedTerm
69 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
70 schema:name Computation Theory and Mathematics
71 rdf:type schema:DefinedTerm
72 sg:journal.1047644 schema:issn 0178-4617
73 1432-0541
74 schema:name Algorithmica
75 schema:publisher Springer Nature
76 rdf:type schema:Periodical
77 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
78 schema:familyName He
79 schema:givenName Xin
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
81 rdf:type schema:Person
82 sg:pub.10.1007/bf01762117 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003139574
83 https://doi.org/10.1007/bf01762117
84 rdf:type schema:CreativeWork
85 sg:pub.10.1007/bf01840403 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020471605
86 https://doi.org/10.1007/bf01840403
87 rdf:type schema:CreativeWork
88 sg:pub.10.1007/bf02187705 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027312329
89 https://doi.org/10.1007/bf02187705
90 rdf:type schema:CreativeWork
91 sg:pub.10.1007/bf02187706 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008881195
92 https://doi.org/10.1007/bf02187706
93 rdf:type schema:CreativeWork
94 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
95 schema:name Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
96 rdf:type schema:Organization
 




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


...