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-11-24T20:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_214.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 Ne873e7823908439ca0ae93d415e6ee7f
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 N3e25558fcd9c40d68aa06dd0a7da48f6
10 Ndab508474821418bbaedc7cbddc3e652
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 N264d0fda1f5c4d09a21244ef0c867a29
30 N60071a597d9747ab9553af38c86257d2
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025511391
32 https://doi.org/10.1007/bf01048274
33 schema:sdDatePublished 2022-11-24T20:46
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher N98dd2177035f4ef09ab50d3715f0f5ea
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 N264d0fda1f5c4d09a21244ef0c867a29 schema:name doi
41 schema:value 10.1007/bf01048274
42 rdf:type schema:PropertyValue
43 N3e25558fcd9c40d68aa06dd0a7da48f6 schema:volumeNumber 2
44 rdf:type schema:PublicationVolume
45 N4736baa2eed44044a5ff481bdd1796d6 rdf:first sg:person.015760032537.47
46 rdf:rest Nc7cc2882632d4c42896addcf569261fe
47 N60071a597d9747ab9553af38c86257d2 schema:name dimensions_id
48 schema:value pub.1025511391
49 rdf:type schema:PropertyValue
50 N8e7a30ac1b4f4b00a03c07c4be2a7ef0 rdf:first sg:person.011520224512.05
51 rdf:rest rdf:nil
52 N98dd2177035f4ef09ab50d3715f0f5ea schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 Nc7cc2882632d4c42896addcf569261fe rdf:first sg:person.015566427161.36
55 rdf:rest N8e7a30ac1b4f4b00a03c07c4be2a7ef0
56 Ndab508474821418bbaedc7cbddc3e652 schema:issueNumber 1
57 rdf:type schema:PublicationIssue
58 Ne873e7823908439ca0ae93d415e6ee7f rdf:first sg:person.07651605463.67
59 rdf:rest N4736baa2eed44044a5ff481bdd1796d6
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)


...