On the cover time of random walks on graphs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1989-01

AUTHORS

Jeff D. Kahn, Nathan Linial, Noam Nisan, Michael E. Saks

ABSTRACT

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n2) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of Ω(n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight. More... »

PAGES

121-128

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf01048274

DOI

http://dx.doi.org/10.1007/bf01048274

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Rutgers University, New Brunswick, New Jersey", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers University, New Brunswick, New Jersey"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kahn", 
        "givenName": "Jeff D.", 
        "id": "sg:person.07651605463.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07651605463.67"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Department, Hebrew University, Jerusalem, Israel", 
          "id": "http://www.grid.ac/institutes/grid.9619.7", 
          "name": [
            "IBM Almaden, 650 Harry Road, 95120, San Jose, California", 
            "Computer Science Department, Hebrew University, Jerusalem, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Linial", 
        "givenName": "Nathan", 
        "id": "sg:person.015760032537.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015760032537.47"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Division, University of California, Berkeley, California", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, University of California, Berkeley, California"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nisan", 
        "givenName": "Noam", 
        "id": "sg:person.015566427161.36", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015566427161.36"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Bell Communications Research, Morristown, New Jersey", 
          "id": "http://www.grid.ac/institutes/grid.432790.b", 
          "name": [
            "Department of Mathematics, Rutgers University, New Brunswick, New Jersey", 
            "Bell Communications Research, Morristown, New Jersey"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "Michael E.", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1989-01", 
    "datePublishedReg": "1989-01-01", 
    "description": "This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n2) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of \u03a9(n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01048274", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136853", 
        "issn": [
          "0894-9840", 
          "1572-9230"
        ], 
        "name": "Journal of Theoretical Probability", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "2"
      }
    ], 
    "keywords": [
      "cover time", 
      "random walk", 
      "finite graphs", 
      "arbitrary graphs", 
      "regular graphs", 
      "graph", 
      "walk", 
      "present examples", 
      "bounds", 
      "vertices", 
      "time", 
      "trees", 
      "article", 
      "expectations", 
      "example"
    ], 
    "name": "On the cover time of random walks on graphs", 
    "pagination": "121-128", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1025511391"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01048274"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01048274", 
      "https://app.dimensions.ai/details/publication/pub.1025511391"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-10-01T06:28", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_212.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01048274"
  }
]
 

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/bf01048274'

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/bf01048274'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01048274'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01048274'


 

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

104 TRIPLES      20 PREDICATES      39 URIs      31 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01048274 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N3a0b4cc7169f4d8db49fc4194986cf3f
4 schema:datePublished 1989-01
5 schema:datePublishedReg 1989-01-01
6 schema:description This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n2) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of Ω(n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.
7 schema:genre article
8 schema:isAccessibleForFree true
9 schema:isPartOf N12e65cc97d8b4be9bc15bec98f565eab
10 N283aa6dafeba40daa57c97f5f2676ded
11 sg:journal.1136853
12 schema:keywords arbitrary graphs
13 article
14 bounds
15 cover time
16 example
17 expectations
18 finite graphs
19 graph
20 present examples
21 random walk
22 regular graphs
23 time
24 trees
25 vertices
26 walk
27 schema:name On the cover time of random walks on graphs
28 schema:pagination 121-128
29 schema:productId N2561cba47f09426e8867dc241277f5bf
30 Nee609fdae01642fea7a5fc0c423dd1dc
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025511391
32 https://doi.org/10.1007/bf01048274
33 schema:sdDatePublished 2022-10-01T06:28
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher Ne464d2c608a44fc7ba929254861f0a38
36 schema:url https://doi.org/10.1007/bf01048274
37 sgo:license sg:explorer/license/
38 sgo:sdDataset articles
39 rdf:type schema:ScholarlyArticle
40 N12e65cc97d8b4be9bc15bec98f565eab schema:issueNumber 1
41 rdf:type schema:PublicationIssue
42 N2561cba47f09426e8867dc241277f5bf schema:name doi
43 schema:value 10.1007/bf01048274
44 rdf:type schema:PropertyValue
45 N283aa6dafeba40daa57c97f5f2676ded schema:volumeNumber 2
46 rdf:type schema:PublicationVolume
47 N3a0b4cc7169f4d8db49fc4194986cf3f rdf:first sg:person.07651605463.67
48 rdf:rest N6e49e0a918e84aecb8feeeb67532d49b
49 N5ba95607aeda406ea9685ef60ea72ffe rdf:first sg:person.015566427161.36
50 rdf:rest Ne5eafeaba22c4524a451b3d8ded804a8
51 N6e49e0a918e84aecb8feeeb67532d49b rdf:first sg:person.015760032537.47
52 rdf:rest N5ba95607aeda406ea9685ef60ea72ffe
53 Ne464d2c608a44fc7ba929254861f0a38 schema:name Springer Nature - SN SciGraph project
54 rdf:type schema:Organization
55 Ne5eafeaba22c4524a451b3d8ded804a8 rdf:first sg:person.011520224512.05
56 rdf:rest rdf:nil
57 Nee609fdae01642fea7a5fc0c423dd1dc schema:name dimensions_id
58 schema:value pub.1025511391
59 rdf:type schema:PropertyValue
60 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
61 schema:name Mathematical Sciences
62 rdf:type schema:DefinedTerm
63 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
64 schema:name Pure Mathematics
65 rdf:type schema:DefinedTerm
66 sg:journal.1136853 schema:issn 0894-9840
67 1572-9230
68 schema:name Journal of Theoretical Probability
69 schema:publisher Springer Nature
70 rdf:type schema:Periodical
71 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.432790.b
72 schema:familyName Saks
73 schema:givenName Michael E.
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
75 rdf:type schema:Person
76 sg:person.015566427161.36 schema:affiliation grid-institutes:grid.47840.3f
77 schema:familyName Nisan
78 schema:givenName Noam
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015566427161.36
80 rdf:type schema:Person
81 sg:person.015760032537.47 schema:affiliation grid-institutes:grid.9619.7
82 schema:familyName Linial
83 schema:givenName Nathan
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015760032537.47
85 rdf:type schema:Person
86 sg:person.07651605463.67 schema:affiliation grid-institutes:grid.430387.b
87 schema:familyName Kahn
88 schema:givenName Jeff D.
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07651605463.67
90 rdf:type schema:Person
91 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, New Brunswick, New Jersey
92 schema:name Department of Mathematics, Rutgers University, New Brunswick, New Jersey
93 rdf:type schema:Organization
94 grid-institutes:grid.432790.b schema:alternateName Bell Communications Research, Morristown, New Jersey
95 schema:name Bell Communications Research, Morristown, New Jersey
96 Department of Mathematics, Rutgers University, New Brunswick, New Jersey
97 rdf:type schema:Organization
98 grid-institutes:grid.47840.3f schema:alternateName Computer Science Division, University of California, Berkeley, California
99 schema:name Computer Science Division, University of California, Berkeley, California
100 rdf:type schema:Organization
101 grid-institutes:grid.9619.7 schema:alternateName Computer Science Department, Hebrew University, Jerusalem, Israel
102 schema:name Computer Science Department, Hebrew University, Jerusalem, Israel
103 IBM Almaden, 650 Harry Road, 95120, San Jose, California
104 rdf:type schema:Organization
 




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


...