Parallel maximal matching on minimal vertex series parallel digraphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1995

AUTHORS

Luca Baffi , Rossella Petreschi

ABSTRACT

In this paper is presented a parallel algorithm to find a maximal matching on a minimal vertex series parallel dag. The algorithm requires O(m) processors and runs in O(logn) parallel time on a PRAM-EREW model of computation. This algorithm improves of a factor log n the parallel time of the general algorithm when it is specified to this class of graphs. Also the number of processors decreases from O(n + m) to O(m). More... »

PAGES

34-47

Book

TITLE

Algorithms, Concurrency and Knowledge

ISBN

978-3-540-60688-8
978-3-540-49262-7

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-60688-2_33

DOI

http://dx.doi.org/10.1007/3-540-60688-2_33

DIMENSIONS

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


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/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Department of Computer Science, University \u201dLa Sapienza\u201d, Via Salaria 113, 00198\u00a0Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Baffi", 
        "givenName": "Luca", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Department of Computer Science, University \u201dLa Sapienza\u201d, Via Salaria 113, 00198\u00a0Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Petreschi", 
        "givenName": "Rossella", 
        "id": "sg:person.011402427702.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1995", 
    "datePublishedReg": "1995-01-01", 
    "description": "In this paper is presented a parallel algorithm to find a maximal matching on a minimal vertex series parallel dag. The algorithm requires O(m) processors and runs in O(logn) parallel time on a PRAM-EREW model of computation. This algorithm improves of a factor log n the parallel time of the general algorithm when it is specified to this class of graphs. Also the number of processors decreases from O(n + m) to O(m).", 
    "editor": [
      {
        "familyName": "Kanchanasut", 
        "givenName": "Kanchana", 
        "type": "Person"
      }, 
      {
        "familyName": "L\u00e9vy", 
        "givenName": "Jean-Jacques", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-60688-2_33", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-60688-8", 
        "978-3-540-49262-7"
      ], 
      "name": "Algorithms, Concurrency and Knowledge", 
      "type": "Book"
    }, 
    "name": "Parallel maximal matching on minimal vertex series parallel digraphs", 
    "pagination": "34-47", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-60688-2_33"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "053cdf52b7f2c1183e6a7ed572ec6562e12a8067cc362fe0902c77088770b323"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001099328"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-60688-2_33", 
      "https://app.dimensions.ai/details/publication/pub.1001099328"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T00:32", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8700_00000001.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-60688-2_33"
  }
]
 

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-60688-2_33'

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-60688-2_33'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-60688-2_33'

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-60688-2_33'


 

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

76 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-60688-2_33 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N8860fce911e749efb01f62a7449b730e
4 schema:datePublished 1995
5 schema:datePublishedReg 1995-01-01
6 schema:description In this paper is presented a parallel algorithm to find a maximal matching on a minimal vertex series parallel dag. The algorithm requires O(m) processors and runs in O(logn) parallel time on a PRAM-EREW model of computation. This algorithm improves of a factor log n the parallel time of the general algorithm when it is specified to this class of graphs. Also the number of processors decreases from O(n + m) to O(m).
7 schema:editor N7c0d050026db4022b023092fb2526321
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N23e1203cc7794bf9b131f460bc7029a8
12 schema:name Parallel maximal matching on minimal vertex series parallel digraphs
13 schema:pagination 34-47
14 schema:productId N17022b607ef0406ea695a3a84fe661ab
15 N9b6b8c784b804479bf5e8dfd3b6a5f75
16 Naf8892e4e75f462fa722a9756eeb1724
17 schema:publisher N1ee4edf90ee04f05bf09e2d90191c410
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001099328
19 https://doi.org/10.1007/3-540-60688-2_33
20 schema:sdDatePublished 2019-04-16T00:32
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N00b1bcecac5d406190fbe5584aabb623
23 schema:url http://link.springer.com/10.1007/3-540-60688-2_33
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N00b1bcecac5d406190fbe5584aabb623 schema:name Springer Nature - SN SciGraph project
28 rdf:type schema:Organization
29 N17022b607ef0406ea695a3a84fe661ab schema:name doi
30 schema:value 10.1007/3-540-60688-2_33
31 rdf:type schema:PropertyValue
32 N1ee4edf90ee04f05bf09e2d90191c410 schema:location Berlin, Heidelberg
33 schema:name Springer Berlin Heidelberg
34 rdf:type schema:Organisation
35 N23e1203cc7794bf9b131f460bc7029a8 schema:isbn 978-3-540-49262-7
36 978-3-540-60688-8
37 schema:name Algorithms, Concurrency and Knowledge
38 rdf:type schema:Book
39 N2b0a3ff3190c4e419bfb29f5888afc89 schema:familyName Lévy
40 schema:givenName Jean-Jacques
41 rdf:type schema:Person
42 N412d120f69394eb498723fd9c7c0fd3c schema:familyName Kanchanasut
43 schema:givenName Kanchana
44 rdf:type schema:Person
45 N5b1466ef984446dcaeea5c8e6a033ea2 rdf:first sg:person.011402427702.78
46 rdf:rest rdf:nil
47 N7c0d050026db4022b023092fb2526321 rdf:first N412d120f69394eb498723fd9c7c0fd3c
48 rdf:rest N9ddcfe5ab5e14ab194f314fadb2693ba
49 N8860fce911e749efb01f62a7449b730e rdf:first Ne6faf2babdf1461e8782b2c99fc10869
50 rdf:rest N5b1466ef984446dcaeea5c8e6a033ea2
51 N9b6b8c784b804479bf5e8dfd3b6a5f75 schema:name dimensions_id
52 schema:value pub.1001099328
53 rdf:type schema:PropertyValue
54 N9ddcfe5ab5e14ab194f314fadb2693ba rdf:first N2b0a3ff3190c4e419bfb29f5888afc89
55 rdf:rest rdf:nil
56 Naf8892e4e75f462fa722a9756eeb1724 schema:name readcube_id
57 schema:value 053cdf52b7f2c1183e6a7ed572ec6562e12a8067cc362fe0902c77088770b323
58 rdf:type schema:PropertyValue
59 Ne6faf2babdf1461e8782b2c99fc10869 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
60 schema:familyName Baffi
61 schema:givenName Luca
62 rdf:type schema:Person
63 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
64 schema:name Information and Computing Sciences
65 rdf:type schema:DefinedTerm
66 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
67 schema:name Computer Software
68 rdf:type schema:DefinedTerm
69 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
70 schema:familyName Petreschi
71 schema:givenName Rossella
72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
73 rdf:type schema:Person
74 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
75 schema:name Department of Computer Science, University ”La Sapienza”, Via Salaria 113, 00198 Rome, Italy
76 rdf:type schema:Organization
 




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


...