Fast RNC and NC algorithms for finding a maximal set of paths with an application View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1996

AUTHORS

Ryuhei Uehara , Zhi-Zhong Chen , Xin He

ABSTRACT

We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. The former runs in O(log n) expected time with O(n + m) processors on a CRCW PRAM. The latter runs in O(log2n) time with O(Δ2(n + m)/log n) processors on an EREW PRAM. The results improve on the best previous ones and can also be extended to digraphs. We then use the results to design an NC approximation algorithm for a variation of the shortest superstring problem introduced by Jiang et al. The approximation algorithm achieves a compression ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\frac{1}{{3 + \varepsilon }}$$ \end{document}for any ε >0. More... »

PAGES

209-218

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-61332-3_154

DOI

http://dx.doi.org/10.1007/3-540-61332-3_154

DIMENSIONS

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


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": "Center for Inform. Sci., Tokyo Woman's Christian Univ., Suginami, 167, Tokyo", 
          "id": "http://www.grid.ac/institutes/grid.443010.2", 
          "name": [
            "Center for Inform. Sci., Tokyo Woman's Christian Univ., Suginami, 167, Tokyo"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Uehara", 
        "givenName": "Ryuhei", 
        "id": "sg:person.011467765731.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011467765731.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Math. Sci., Tokyo Denki Univ., Hatoyama, 350-03, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Dept. of Math. Sci., Tokyo Denki Univ., Hatoyama, 350-03, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Zhi-Zhong", 
        "id": "sg:person.015654265661.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Comput. Sci., SUNY at Buffalo, 14260, Buffalo, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Dept. of Comput. Sci., SUNY 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"
      }
    ], 
    "datePublished": "1996", 
    "datePublishedReg": "1996-01-01", 
    "description": "We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. The former runs in O(log n) expected time with O(n + m) processors on a CRCW PRAM. The latter runs in O(log2n) time with O(\u03942(n + m)/log n) processors on an EREW PRAM. The results improve on the best previous ones and can also be extended to digraphs. We then use the results to design an NC approximation algorithm for a variation of the shortest superstring problem introduced by Jiang et al. The approximation algorithm achieves a compression ratio of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$\\frac{1}{{3 + \\varepsilon }}$$\n\\end{document}for any \u03b5 >0.", 
    "editor": [
      {
        "familyName": "Cai", 
        "givenName": "Jin-Yi", 
        "type": "Person"
      }, 
      {
        "familyName": "Wong", 
        "givenName": "Chak Kuen", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-61332-3_154", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-61332-9", 
        "978-3-540-68461-9"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "approximation algorithm", 
      "best previous ones", 
      "NC approximation algorithm", 
      "parallel algorithm", 
      "maximal set", 
      "shortest superstring problem", 
      "NC algorithm", 
      "compression ratio", 
      "EREW PRAM", 
      "CRCW PRAM", 
      "algorithm", 
      "undirected graph", 
      "Jiang et al", 
      "processors", 
      "PRAM", 
      "former runs", 
      "previous ones", 
      "set", 
      "path", 
      "graph", 
      "digraphs", 
      "applications", 
      "RNC", 
      "time", 
      "results", 
      "et al", 
      "one", 
      "run", 
      "al", 
      "variation", 
      "ratio", 
      "problem", 
      "superstring problem", 
      "Fast RNC"
    ], 
    "name": "Fast RNC and NC algorithms for finding a maximal set of paths with an application", 
    "pagination": "209-218", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037309368"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-61332-3_154"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-61332-3_154", 
      "https://app.dimensions.ai/details/publication/pub.1037309368"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:45", 
    "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_102.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-61332-3_154"
  }
]
 

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-61332-3_154'

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-61332-3_154'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-61332-3_154'

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-61332-3_154'


 

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

119 TRIPLES      23 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-61332-3_154 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N2eb7b4f742ba4879a92656d0a17ef6f8
4 schema:datePublished 1996
5 schema:datePublishedReg 1996-01-01
6 schema:description We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. The former runs in O(log n) expected time with O(n + m) processors on a CRCW PRAM. The latter runs in O(log2n) time with O(Δ2(n + m)/log n) processors on an EREW PRAM. The results improve on the best previous ones and can also be extended to digraphs. We then use the results to design an NC approximation algorithm for a variation of the shortest superstring problem introduced by Jiang et al. The approximation algorithm achieves a compression ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\frac{1}{{3 + \varepsilon }}$$ \end{document}for any ε >0.
7 schema:editor Nd6ee00a4563a449a851bf6b6336602ad
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N68c69d598eba4eef89849ed20d46f702
12 schema:keywords CRCW PRAM
13 EREW PRAM
14 Fast RNC
15 Jiang et al
16 NC algorithm
17 NC approximation algorithm
18 PRAM
19 RNC
20 al
21 algorithm
22 applications
23 approximation algorithm
24 best previous ones
25 compression ratio
26 digraphs
27 et al
28 former runs
29 graph
30 maximal set
31 one
32 parallel algorithm
33 path
34 previous ones
35 problem
36 processors
37 ratio
38 results
39 run
40 set
41 shortest superstring problem
42 superstring problem
43 time
44 undirected graph
45 variation
46 schema:name Fast RNC and NC algorithms for finding a maximal set of paths with an application
47 schema:pagination 209-218
48 schema:productId N2303005c9b2e46a4b8f6fe348b9d4feb
49 N45dc2fe9d1ce4d5998815439f9ace7a6
50 schema:publisher Nbf2a49c5bca344f0b8729aa9422b9d87
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037309368
52 https://doi.org/10.1007/3-540-61332-3_154
53 schema:sdDatePublished 2021-11-01T18:45
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher Nfde5c1cb304845c5b1228f8ed82df4e6
56 schema:url https://doi.org/10.1007/3-540-61332-3_154
57 sgo:license sg:explorer/license/
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N044965b35e664992a1217c68a0172fe0 rdf:first sg:person.011352641523.42
61 rdf:rest rdf:nil
62 N2303005c9b2e46a4b8f6fe348b9d4feb schema:name dimensions_id
63 schema:value pub.1037309368
64 rdf:type schema:PropertyValue
65 N2eb7b4f742ba4879a92656d0a17ef6f8 rdf:first sg:person.011467765731.43
66 rdf:rest N9cf797d98bac4423b826b372689bd26b
67 N381a87e21d08422198dd96c00ee23b1f schema:familyName Wong
68 schema:givenName Chak Kuen
69 rdf:type schema:Person
70 N42a5975a80a14045bb8b2459a3c13259 schema:familyName Cai
71 schema:givenName Jin-Yi
72 rdf:type schema:Person
73 N45dc2fe9d1ce4d5998815439f9ace7a6 schema:name doi
74 schema:value 10.1007/3-540-61332-3_154
75 rdf:type schema:PropertyValue
76 N68c69d598eba4eef89849ed20d46f702 schema:isbn 978-3-540-61332-9
77 978-3-540-68461-9
78 schema:name Computing and Combinatorics
79 rdf:type schema:Book
80 N9cf797d98bac4423b826b372689bd26b rdf:first sg:person.015654265661.98
81 rdf:rest N044965b35e664992a1217c68a0172fe0
82 Nbf2a49c5bca344f0b8729aa9422b9d87 schema:name Springer Nature
83 rdf:type schema:Organisation
84 Nd6ee00a4563a449a851bf6b6336602ad rdf:first N42a5975a80a14045bb8b2459a3c13259
85 rdf:rest Nec5c37e8d5784503b4b29f82da2533d5
86 Nec5c37e8d5784503b4b29f82da2533d5 rdf:first N381a87e21d08422198dd96c00ee23b1f
87 rdf:rest rdf:nil
88 Nfde5c1cb304845c5b1228f8ed82df4e6 schema:name Springer Nature - SN SciGraph project
89 rdf:type schema:Organization
90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
91 schema:name Information and Computing Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
94 schema:name Computation Theory and Mathematics
95 rdf:type schema:DefinedTerm
96 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
97 schema:familyName He
98 schema:givenName Xin
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
100 rdf:type schema:Person
101 sg:person.011467765731.43 schema:affiliation grid-institutes:grid.443010.2
102 schema:familyName Uehara
103 schema:givenName Ryuhei
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011467765731.43
105 rdf:type schema:Person
106 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
107 schema:familyName Chen
108 schema:givenName Zhi-Zhong
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
110 rdf:type schema:Person
111 grid-institutes:grid.273335.3 schema:alternateName Dept. of Comput. Sci., SUNY at Buffalo, 14260, Buffalo, NY, USA
112 schema:name Dept. of Comput. Sci., SUNY at Buffalo, 14260, Buffalo, NY, USA
113 rdf:type schema:Organization
114 grid-institutes:grid.412773.4 schema:alternateName Dept. of Math. Sci., Tokyo Denki Univ., Hatoyama, 350-03, Saitama, Japan
115 schema:name Dept. of Math. Sci., Tokyo Denki Univ., Hatoyama, 350-03, Saitama, Japan
116 rdf:type schema:Organization
117 grid-institutes:grid.443010.2 schema:alternateName Center for Inform. Sci., Tokyo Woman's Christian Univ., Suginami, 167, Tokyo
118 schema:name Center for Inform. Sci., Tokyo Woman's Christian Univ., Suginami, 167, Tokyo
119 rdf:type schema:Organization
 




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


...