Parallel Algorithm for Special Graphs View Homepage


Ontology type: schema:MonetaryGrant     


Grant Info

YEARS

1990-1993

FUNDING AMOUNT

35581 USD

ABSTRACT

This project is concerned with the design of efficient parallel algorithms for solving various graph problems arising from disparate areas in Computer Science. These problems can be roughly divided into three categories: graph layout problems, some fundamental problems for planar graphs, and optimization problems for a class of special graphs including permutation graphs, comparability graphs, and cographs. Because of their broad applications in a variety of applied science disciplines, sequential algorithms for these problems have been extensively studied. But it appears difficult to solve them in parallel. Either no fast parallel algorithms for solving them are known; or parallel algorithms exist, but require a very large number of processors. The properties of these graphs and intrinsic structures of these problems will be investigated, and new parallel algorithms for solving them will be developed (or the efficiency of existing parallel algorithms will be improved). A main concern of this project is to identify common characteristics and to find algorithmic tools for the problems in each category. The results produced from this study will provide not only efficient parallel algorithms for individual problems, but also new understanding of these special graphs and new techniques for designing parallel algorithms. More... »

URL

http://www.nsf.gov/awardsearch/showAward?AWD_ID=9011214&HistoricalAwards=false

Related SciGraph Publications

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/2201", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2208", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "type": "DefinedTerm"
      }
    ], 
    "amount": {
      "currency": "USD", 
      "type": "MonetaryAmount", 
      "value": "35581"
    }, 
    "description": "This project is concerned with the design of efficient parallel algorithms for solving various graph problems arising from disparate areas in Computer Science. These problems can be roughly divided into three categories: graph layout problems, some fundamental problems for planar graphs, and optimization problems for a class of special graphs including permutation graphs, comparability graphs, and cographs. Because of their broad applications in a variety of applied science disciplines, sequential algorithms for these problems have been extensively studied. But it appears difficult to solve them in parallel. Either no fast parallel algorithms for solving them are known; or parallel algorithms exist, but require a very large number of processors. The properties of these graphs and intrinsic structures of these problems will be investigated, and new parallel algorithms for solving them will be developed (or the efficiency of existing parallel algorithms will be improved). A main concern of this project is to identify common characteristics and to find algorithmic tools for the problems in each category. The results produced from this study will provide not only efficient parallel algorithms for individual problems, but also new understanding of these special graphs and new techniques for designing parallel algorithms.", 
    "endDate": "1993-05-31T00:00:00Z", 
    "funder": {
      "id": "https://www.grid.ac/institutes/grid.457785.c", 
      "type": "Organization"
    }, 
    "id": "sg:grant.3383643", 
    "identifier": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "3383643"
        ]
      }, 
      {
        "name": "nsf_id", 
        "type": "PropertyValue", 
        "value": [
          "9011214"
        ]
      }
    ], 
    "inLanguage": [
      "en"
    ], 
    "keywords": [
      "project", 
      "cographs", 
      "efficiency", 
      "broad application", 
      "planar graphs", 
      "new parallel algorithms", 
      "sequential algorithms", 
      "problem", 
      "parallel", 
      "graph layout problems", 
      "categories", 
      "parallel algorithms", 
      "disparate areas", 
      "algorithmic tools", 
      "intrinsic structure", 
      "class", 
      "study", 
      "efficient parallel algorithms", 
      "design", 
      "various graph problems", 
      "properties", 
      "results", 
      "computer science", 
      "science disciplines", 
      "large number", 
      "main concern", 
      "common characteristics", 
      "parallel algorithm", 
      "variety", 
      "permutation graphs", 
      "processors", 
      "special graphs", 
      "fundamental problem", 
      "individual problems", 
      "comparability graphs", 
      "Special Graphs", 
      "optimization problem", 
      "graph", 
      "new technique", 
      "parallel algorithms exist", 
      "new understanding"
    ], 
    "name": "Parallel Algorithm for Special Graphs", 
    "recipient": [
      {
        "id": "https://www.grid.ac/institutes/grid.273335.3", 
        "type": "Organization"
      }, 
      {
        "affiliation": {
          "id": "https://www.grid.ac/institutes/grid.273335.3", 
          "name": "SUNY at Buffalo", 
          "type": "Organization"
        }, 
        "familyName": "He", 
        "givenName": "Xin", 
        "id": "sg:person.011352641523.42", 
        "type": "Person"
      }, 
      {
        "member": "sg:person.011352641523.42", 
        "roleName": "PI", 
        "type": "Role"
      }
    ], 
    "sameAs": [
      "https://app.dimensions.ai/details/grant/grant.3383643"
    ], 
    "sdDataset": "grants", 
    "sdDatePublished": "2019-03-07T12:30", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com.uberresearch.data.processor/core_data/20181219_192338/projects/base/nsf_projects_19.xml.gz", 
    "startDate": "1990-06-15T00:00:00Z", 
    "type": "MonetaryGrant", 
    "url": "http://www.nsf.gov/awardsearch/showAward?AWD_ID=9011214&HistoricalAwards=false"
  }
]
 

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/grant.3383643'

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

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/grant.3383643'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/grant.3383643'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/grant.3383643'


 

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

88 TRIPLES      19 PREDICATES      64 URIs      55 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:grant.3383643 schema:about anzsrc-for:2201
2 anzsrc-for:2208
3 schema:amount N819a5808b6fa43159768267540775138
4 schema:description This project is concerned with the design of efficient parallel algorithms for solving various graph problems arising from disparate areas in Computer Science. These problems can be roughly divided into three categories: graph layout problems, some fundamental problems for planar graphs, and optimization problems for a class of special graphs including permutation graphs, comparability graphs, and cographs. Because of their broad applications in a variety of applied science disciplines, sequential algorithms for these problems have been extensively studied. But it appears difficult to solve them in parallel. Either no fast parallel algorithms for solving them are known; or parallel algorithms exist, but require a very large number of processors. The properties of these graphs and intrinsic structures of these problems will be investigated, and new parallel algorithms for solving them will be developed (or the efficiency of existing parallel algorithms will be improved). A main concern of this project is to identify common characteristics and to find algorithmic tools for the problems in each category. The results produced from this study will provide not only efficient parallel algorithms for individual problems, but also new understanding of these special graphs and new techniques for designing parallel algorithms.
5 schema:endDate 1993-05-31T00:00:00Z
6 schema:funder https://www.grid.ac/institutes/grid.457785.c
7 schema:identifier N906e59a385974b44a035ccc646b41cbb
8 N997eb624f54248239117af685e9a2a48
9 schema:inLanguage en
10 schema:keywords Special Graphs
11 algorithmic tools
12 broad application
13 categories
14 class
15 cographs
16 common characteristics
17 comparability graphs
18 computer science
19 design
20 disparate areas
21 efficiency
22 efficient parallel algorithms
23 fundamental problem
24 graph
25 graph layout problems
26 individual problems
27 intrinsic structure
28 large number
29 main concern
30 new parallel algorithms
31 new technique
32 new understanding
33 optimization problem
34 parallel
35 parallel algorithm
36 parallel algorithms
37 parallel algorithms exist
38 permutation graphs
39 planar graphs
40 problem
41 processors
42 project
43 properties
44 results
45 science disciplines
46 sequential algorithms
47 special graphs
48 study
49 variety
50 various graph problems
51 schema:name Parallel Algorithm for Special Graphs
52 schema:recipient N1f56aab829494f35817b39eb1d0fa0ce
53 sg:person.011352641523.42
54 https://www.grid.ac/institutes/grid.273335.3
55 schema:sameAs https://app.dimensions.ai/details/grant/grant.3383643
56 schema:sdDatePublished 2019-03-07T12:30
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher Na656123784f04d1dbf7abcd444f7b4f8
59 schema:startDate 1990-06-15T00:00:00Z
60 schema:url http://www.nsf.gov/awardsearch/showAward?AWD_ID=9011214&HistoricalAwards=false
61 sgo:license sg:explorer/license/
62 sgo:sdDataset grants
63 rdf:type schema:MonetaryGrant
64 N1f56aab829494f35817b39eb1d0fa0ce schema:member sg:person.011352641523.42
65 schema:roleName PI
66 rdf:type schema:Role
67 N819a5808b6fa43159768267540775138 schema:currency USD
68 schema:value 35581
69 rdf:type schema:MonetaryAmount
70 N906e59a385974b44a035ccc646b41cbb schema:name nsf_id
71 schema:value 9011214
72 rdf:type schema:PropertyValue
73 N997eb624f54248239117af685e9a2a48 schema:name dimensions_id
74 schema:value 3383643
75 rdf:type schema:PropertyValue
76 Na656123784f04d1dbf7abcd444f7b4f8 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 anzsrc-for:2201 schema:inDefinedTermSet anzsrc-for:
79 rdf:type schema:DefinedTerm
80 anzsrc-for:2208 schema:inDefinedTermSet anzsrc-for:
81 rdf:type schema:DefinedTerm
82 sg:person.011352641523.42 schema:affiliation https://www.grid.ac/institutes/grid.273335.3
83 schema:familyName He
84 schema:givenName Xin
85 rdf:type schema:Person
86 https://www.grid.ac/institutes/grid.273335.3 schema:name SUNY at Buffalo
87 rdf:type schema:Organization
88 https://www.grid.ac/institutes/grid.457785.c schema:Organization
 




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


...