Parallel algorithm for cograph recognition with applications View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1992

AUTHORS

Xin He

ABSTRACT

We present a parallel algorithm for recognizing cographs and constructing their cotrees. The algorithm takes O(log2n) time with O(n+m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of the graph. Using cotree representation, we obtain a parallel algorithm for the permutation representation problem for cographs using O(log n) time with O(n) processors. We also present a parallel algorithm for the depthfirst spanning tree problem for permutation graphs (a class properly contains cographs) which takes O(log2n) time with O(n) processors. More... »

PAGES

94-105

Book

TITLE

Algorithm Theory — SWAT '92

ISBN

978-3-540-55706-7
978-3-540-47275-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-55706-7_9

DOI

http://dx.doi.org/10.1007/3-540-55706-7_9

DIMENSIONS

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


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", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY"
          ], 
          "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"
      }
    ], 
    "datePublished": "1992", 
    "datePublishedReg": "1992-01-01", 
    "description": "We present a parallel algorithm for recognizing cographs and constructing their cotrees. The algorithm takes O(log2n) time with O(n+m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of the graph. Using cotree representation, we obtain a parallel algorithm for the permutation representation problem for cographs using O(log n) time with O(n) processors. We also present a parallel algorithm for the depthfirst spanning tree problem for permutation graphs (a class properly contains cographs) which takes O(log2n) time with O(n) processors.", 
    "editor": [
      {
        "familyName": "Nurmi", 
        "givenName": "Otto", 
        "type": "Person"
      }, 
      {
        "familyName": "Ukkonen", 
        "givenName": "Esko", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-55706-7_9", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-55706-7", 
        "978-3-540-47275-9"
      ], 
      "name": "Algorithm Theory \u2014 SWAT '92", 
      "type": "Book"
    }, 
    "keywords": [
      "parallel algorithm", 
      "cograph recognition", 
      "CRCW PRAM", 
      "cotree representation", 
      "algorithm", 
      "number of vertices", 
      "representation problem", 
      "processors", 
      "tree problem", 
      "permutation graphs", 
      "graph", 
      "cographs", 
      "PRAM", 
      "cotree", 
      "representation", 
      "recognition", 
      "applications", 
      "vertices", 
      "time", 
      "edge", 
      "number", 
      "problem", 
      "permutation representation problem", 
      "depthfirst"
    ], 
    "name": "Parallel algorithm for cograph recognition with applications", 
    "pagination": "94-105", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1043688111"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-55706-7_9"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-55706-7_9", 
      "https://app.dimensions.ai/details/publication/pub.1043688111"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:48", 
    "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/chapter/chapter_157.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-55706-7_9"
  }
]
 

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/3-540-55706-7_9'

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/3-540-55706-7_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-55706-7_9'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-55706-7_9'


 

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

89 TRIPLES      23 PREDICATES      50 URIs      43 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-55706-7_9 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N3968c2f62a1c4f3c8687b25e725e5400
4 schema:datePublished 1992
5 schema:datePublishedReg 1992-01-01
6 schema:description We present a parallel algorithm for recognizing cographs and constructing their cotrees. The algorithm takes O(log2n) time with O(n+m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of the graph. Using cotree representation, we obtain a parallel algorithm for the permutation representation problem for cographs using O(log n) time with O(n) processors. We also present a parallel algorithm for the depthfirst spanning tree problem for permutation graphs (a class properly contains cographs) which takes O(log2n) time with O(n) processors.
7 schema:editor N5dd44259c1e8486ca726a47c75e5ce8f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N0aa1e8ce21a04b2d9e6a88387990b301
12 schema:keywords CRCW PRAM
13 PRAM
14 algorithm
15 applications
16 cograph recognition
17 cographs
18 cotree
19 cotree representation
20 depthfirst
21 edge
22 graph
23 number
24 number of vertices
25 parallel algorithm
26 permutation graphs
27 permutation representation problem
28 problem
29 processors
30 recognition
31 representation
32 representation problem
33 time
34 tree problem
35 vertices
36 schema:name Parallel algorithm for cograph recognition with applications
37 schema:pagination 94-105
38 schema:productId N4e534a1caed64b2f8ddae029b3125b7c
39 Nefd9c3afbd99458da36516aeafb79d66
40 schema:publisher Nc2c73e48216f45d0a6cdfa8b42f86dc9
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043688111
42 https://doi.org/10.1007/3-540-55706-7_9
43 schema:sdDatePublished 2021-11-01T18:48
44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
45 schema:sdPublisher Nb2460af6382c41819cef2e1805adfda7
46 schema:url https://doi.org/10.1007/3-540-55706-7_9
47 sgo:license sg:explorer/license/
48 sgo:sdDataset chapters
49 rdf:type schema:Chapter
50 N0aa1e8ce21a04b2d9e6a88387990b301 schema:isbn 978-3-540-47275-9
51 978-3-540-55706-7
52 schema:name Algorithm Theory — SWAT '92
53 rdf:type schema:Book
54 N2a82335e8378466c817ebc17679aa8dd schema:familyName Nurmi
55 schema:givenName Otto
56 rdf:type schema:Person
57 N36e1c52b758d4d029a35c1c174fd2e4d rdf:first Nc42a720a52fa43708551b0ae0b90d3c7
58 rdf:rest rdf:nil
59 N3968c2f62a1c4f3c8687b25e725e5400 rdf:first sg:person.011352641523.42
60 rdf:rest rdf:nil
61 N4e534a1caed64b2f8ddae029b3125b7c schema:name doi
62 schema:value 10.1007/3-540-55706-7_9
63 rdf:type schema:PropertyValue
64 N5dd44259c1e8486ca726a47c75e5ce8f rdf:first N2a82335e8378466c817ebc17679aa8dd
65 rdf:rest N36e1c52b758d4d029a35c1c174fd2e4d
66 Nb2460af6382c41819cef2e1805adfda7 schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 Nc2c73e48216f45d0a6cdfa8b42f86dc9 schema:name Springer Nature
69 rdf:type schema:Organisation
70 Nc42a720a52fa43708551b0ae0b90d3c7 schema:familyName Ukkonen
71 schema:givenName Esko
72 rdf:type schema:Person
73 Nefd9c3afbd99458da36516aeafb79d66 schema:name dimensions_id
74 schema:value pub.1043688111
75 rdf:type schema:PropertyValue
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
80 schema:name Computation Theory and Mathematics
81 rdf:type schema:DefinedTerm
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 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY
88 schema:name Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY
89 rdf:type schema:Organization
 




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


...