Randomized Time-Space Tradeoffs for Directed Graph Connectivity View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2003

AUTHORS

Parikshit Gopalan , Richard J. Lipton , Aranyak Mehta

ABSTRACT

We present a spectrum of randomized time-space tradeoffs for solving directed graph connectivity or STCONN in small space. We use a strategy parameterized by a parameter k that uses k pebbles and performs short random walks of length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$n^{\frac{1}{k}}$\end{document} using a probabilistic counter. We use this to get a family of algorithms that ranges between log2n and log n in space and 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$^{{\rm log^2}n}$\end{document} and nn in running time. Our approach allows us to look at Savitch’s algorithm and the random walk algorithm as two extremes of the same basic divide and conquer strategy. More... »

PAGES

208-216

Book

TITLE

FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science

ISBN

978-3-540-20680-4
978-3-540-24597-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-24597-1_18

DOI

http://dx.doi.org/10.1007/978-3-540-24597-1_18

DIMENSIONS

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


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": "College of Computing, Georgia Institute of Technology, 30309, Atlanta, GA, USA", 
          "id": "http://www.grid.ac/institutes/grid.213917.f", 
          "name": [
            "College of Computing, Georgia Institute of Technology, 30309, Atlanta, GA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gopalan", 
        "givenName": "Parikshit", 
        "id": "sg:person.011621327233.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011621327233.73"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "College of Computing, Georgia Institute of Technology, 30309, Atlanta, GA, USA", 
          "id": "http://www.grid.ac/institutes/grid.213917.f", 
          "name": [
            "College of Computing, Georgia Institute of Technology, 30309, Atlanta, GA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lipton", 
        "givenName": "Richard J.", 
        "id": "sg:person.010133373171.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010133373171.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "College of Computing, Georgia Institute of Technology, 30309, Atlanta, GA, USA", 
          "id": "http://www.grid.ac/institutes/grid.213917.f", 
          "name": [
            "College of Computing, Georgia Institute of Technology, 30309, Atlanta, GA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehta", 
        "givenName": "Aranyak", 
        "id": "sg:person.010106546671.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2003", 
    "datePublishedReg": "2003-01-01", 
    "description": "We present a spectrum of randomized time-space tradeoffs for solving directed graph connectivity or STCONN in small space. We use a strategy parameterized by a parameter k that uses k pebbles and performs short random walks of length \\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}{k}}$\\end{document} using a probabilistic counter. We use this to get a family of algorithms that ranges between log2n and log n in space and 2\\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}$^{{\\rm log^2}n}$\\end{document} and nn in running time. Our approach allows us to look at Savitch\u2019s algorithm and the random walk algorithm as two extremes of the same basic divide and conquer strategy.", 
    "editor": [
      {
        "familyName": "Pandya", 
        "givenName": "Paritosh K.", 
        "type": "Person"
      }, 
      {
        "familyName": "Radhakrishnan", 
        "givenName": "Jaikumar", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-24597-1_18", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-20680-4", 
        "978-3-540-24597-1"
      ], 
      "name": "FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science", 
      "type": "Book"
    }, 
    "keywords": [
      "time-space tradeoff", 
      "graph connectivity", 
      "family of algorithms", 
      "short random walks", 
      "random walk algorithm", 
      "random walk", 
      "walk algorithm", 
      "parameter k", 
      "log n", 
      "probabilistic counter", 
      "algorithm", 
      "space", 
      "walk", 
      "tradeoff", 
      "small space", 
      "log2n", 
      "connectivity", 
      "approach", 
      "spectra", 
      "length", 
      "extremes", 
      "time", 
      "counter", 
      "strategies", 
      "pebbles", 
      "family", 
      "divide", 
      "basic divide"
    ], 
    "name": "Randomized Time-Space Tradeoffs for Directed Graph Connectivity", 
    "pagination": "208-216", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045262108"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-24597-1_18"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-24597-1_18", 
      "https://app.dimensions.ai/details/publication/pub.1045262108"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_286.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-24597-1_18"
  }
]
 

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/978-3-540-24597-1_18'

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/978-3-540-24597-1_18'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24597-1_18'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24597-1_18'


 

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

107 TRIPLES      23 PREDICATES      54 URIs      47 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-24597-1_18 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N130652f9c7694524855e9e9cc0bc5d36
4 schema:datePublished 2003
5 schema:datePublishedReg 2003-01-01
6 schema:description We present a spectrum of randomized time-space tradeoffs for solving directed graph connectivity or STCONN in small space. We use a strategy parameterized by a parameter k that uses k pebbles and performs short random walks of length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$n^{\frac{1}{k}}$\end{document} using a probabilistic counter. We use this to get a family of algorithms that ranges between log2n and log n in space and 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$^{{\rm log^2}n}$\end{document} and nn in running time. Our approach allows us to look at Savitch’s algorithm and the random walk algorithm as two extremes of the same basic divide and conquer strategy.
7 schema:editor N792638487048466e9d22a55fa8b4abe6
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N11b0e8dd7b7b40e4b69b42d769be15e6
12 schema:keywords algorithm
13 approach
14 basic divide
15 connectivity
16 counter
17 divide
18 extremes
19 family
20 family of algorithms
21 graph connectivity
22 length
23 log n
24 log2n
25 parameter k
26 pebbles
27 probabilistic counter
28 random walk
29 random walk algorithm
30 short random walks
31 small space
32 space
33 spectra
34 strategies
35 time
36 time-space tradeoff
37 tradeoff
38 walk
39 walk algorithm
40 schema:name Randomized Time-Space Tradeoffs for Directed Graph Connectivity
41 schema:pagination 208-216
42 schema:productId N64fc0f73c8f6446ab12d57775f82b3c4
43 N67fb19a2da324532b1f15da7d3ce18e7
44 schema:publisher N05711ea5ae97427fbbf98636c0a6ba96
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045262108
46 https://doi.org/10.1007/978-3-540-24597-1_18
47 schema:sdDatePublished 2022-05-10T10:45
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher N577db32e76d041a6b648008030170bfe
50 schema:url https://doi.org/10.1007/978-3-540-24597-1_18
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N05711ea5ae97427fbbf98636c0a6ba96 schema:name Springer Nature
55 rdf:type schema:Organisation
56 N11b0e8dd7b7b40e4b69b42d769be15e6 schema:isbn 978-3-540-20680-4
57 978-3-540-24597-1
58 schema:name FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
59 rdf:type schema:Book
60 N130652f9c7694524855e9e9cc0bc5d36 rdf:first sg:person.011621327233.73
61 rdf:rest Nca78c2d73f6c473bb8fd6386f86b63a5
62 N13d2b87604b3448db6051cf62bc3dcb2 schema:familyName Pandya
63 schema:givenName Paritosh K.
64 rdf:type schema:Person
65 N577db32e76d041a6b648008030170bfe schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N64fc0f73c8f6446ab12d57775f82b3c4 schema:name dimensions_id
68 schema:value pub.1045262108
69 rdf:type schema:PropertyValue
70 N67fb19a2da324532b1f15da7d3ce18e7 schema:name doi
71 schema:value 10.1007/978-3-540-24597-1_18
72 rdf:type schema:PropertyValue
73 N706568ca2695400384da6d2ad5fe0f18 rdf:first Na10d54680a344237b9500192d4680371
74 rdf:rest rdf:nil
75 N792638487048466e9d22a55fa8b4abe6 rdf:first N13d2b87604b3448db6051cf62bc3dcb2
76 rdf:rest N706568ca2695400384da6d2ad5fe0f18
77 Na10d54680a344237b9500192d4680371 schema:familyName Radhakrishnan
78 schema:givenName Jaikumar
79 rdf:type schema:Person
80 Nb51b5113f7d74111a6f5020423d49b19 rdf:first sg:person.010106546671.08
81 rdf:rest rdf:nil
82 Nca78c2d73f6c473bb8fd6386f86b63a5 rdf:first sg:person.010133373171.27
83 rdf:rest Nb51b5113f7d74111a6f5020423d49b19
84 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
85 schema:name Information and Computing Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
88 schema:name Computation Theory and Mathematics
89 rdf:type schema:DefinedTerm
90 sg:person.010106546671.08 schema:affiliation grid-institutes:grid.213917.f
91 schema:familyName Mehta
92 schema:givenName Aranyak
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08
94 rdf:type schema:Person
95 sg:person.010133373171.27 schema:affiliation grid-institutes:grid.213917.f
96 schema:familyName Lipton
97 schema:givenName Richard J.
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010133373171.27
99 rdf:type schema:Person
100 sg:person.011621327233.73 schema:affiliation grid-institutes:grid.213917.f
101 schema:familyName Gopalan
102 schema:givenName Parikshit
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011621327233.73
104 rdf:type schema:Person
105 grid-institutes:grid.213917.f schema:alternateName College of Computing, Georgia Institute of Technology, 30309, Atlanta, GA, USA
106 schema:name College of Computing, Georgia Institute of Technology, 30309, Atlanta, GA, USA
107 rdf:type schema:Organization
 




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


...