2011-10-01, English, Article, Report edition: Derandomizing random walks in undirected graphs using locally fair exploration strategies.(Report) Cooper, Colin; Ilcinkas, David; Klasing, Ralf; ...

User activity

Share to:
 
Bookmark: https://trove.nla.gov.au/version/171025977
Physical Description
  • Report
  • Magazine/​Journal article
Published
  • Springer, 2011 Oct
Language
  • English

Edition details

Title
  • Derandomizing random walks in undirected graphs using locally fair exploration strategies.(Report)
Also Titled
  • Derandomizing random walks in undirected graphs using locally fair exploration strategies.
Appears In
  • Distributed Computing, v.24, no.2, 2011 Oct, p.91(9) (ISSN: 0178-2770)
Author
  • Cooper, Colin
  • Ilcinkas, David
  • Klasing, Ralf
  • Kosowski, Adrian
Published
  • Springer, 2011 Oct
Physical Description
  • Report
  • Magazine/​Journal article
Subjects
Target Audience
  • Academic
Summary
  • Byline: Colin Cooper (1), David Ilcinkas (2), Ralf Klasing (2), Adrian Kosowski (3) Keywords: Graph exploration; Random walk; Rotor-router model; Local knowledge; Deterministic strategy Abstract: We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural counterparts for undirected graphs of the rotor-router model for symmetric directed graphs. The first of the studied strategies, known as Oldest-First, always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph G =​ (V, E) of diameter D within time O(D|E|), and in the long run traverses all edges of G with the same frequency. Author Affiliation: (1) Department of Computer Science, King's College London, London, WC2R 2LS, UK (2) LaBRI - Universite de Bordeaux - CNRS, 351 cours de la Liberation, 33405, Talence, France (3) INRIA Bordeaux Sud-Ouest, 351 cours de la Liberation, 33405, Talence, France Article History: Registration Date: 25/​08/​2011 Received Date: 20/​07/​2010 Accepted Date: 25/​08/​2011 Online Date: 11/​09/​2011 Article note: The research was partially supported by the ANR project "ALADDIN", the INRIA equipe-project "CEPAGE", and the Royal Society IJP grant "Random walks, interacting particles and faster network exploration". A. Kosowski was partially supported by Polish Ministry Grant N206 491738.
Terms of Use
  • COPYRIGHT 2011 Springer
Language
  • English
Database
  • Gale Academic OneFile
Identifier
  • 267613028

Get this edition

Via a library membership

Library View online via
Australian College of Physical Education. Australian College of Physical Education Library.
Australian Catholic University. Alumni Access.
Australian Catholic University.
Australian Institute of Professional Education.
Australian Lutheran College. Lohe Memorial Library.
Avondale College. Avondale College of Higher Education Sydney Campus Library.
University of Adelaide. Barr Smith Library.
Blue Mountains International Hotel Management School.
Bond University. John and Alison Kearney Library .
Campion College Australia.
Charles Darwin University. Casuarina Campus Library.
Cengage Education.
Christian Heritage College. Christian Heritage College Library.
Deakin University. Deakin University Library.
Edith Cowan University. Edith Cowan University Library.
Australian College of Natural Medicine Pty Ltd. Endeavour College of Natural Health Library.
Excelsia College. Excelsia College Library.
Kaplan Professional. Library.
Fire & Rescue NSW. FRNSW Library.
University of Notre Dame Australia. Galvin Medical Library.
Holmesglen Institute of TAFE. Holmesglen Learning Commons.
International College of Management, Sydney. ICMS Library.
Macquarie University. Macquarie University Library.
Marcus Oldham College. Sir James Darling Resource Centre.
Melbourne Library Service.
Monash University. Monash University Library.
Moore Theological College. Moore Theological College Library.
SA Mental Health Services.
Sydney Missionary and Bible College. J.T.H. Kerr Library.
South Australian Research and Development Institute. South Australian Aquatic Sciences Centre Library.
South Western Sydney Institute of TAFE.
Swinburne University of Technology. Swinburne Library.
Tabor College Victoria.
Tabor Adelaide. Tabor College Library.
The Southport School. Senior Library.
Think: Education Group. Think Education Group Learning Resource Centre.
University of New England. Dixson Library.
University of Canberra. University of Canberra Library.
University of Wollongong. University of Wollongong Library.
University of Queensland. University of Queensland Library. UQ Library Cyberschool.
Catholic Institute of Sydney. Veech Library.
Western Sydney University. Hawkesbury Campus Library.
Show 0 more libraries...
Library View online via
University of Canberra. University of Canberra Library.
Show 0 more libraries...
Library View online via
Australian College of Physical Education. Australian College of Physical Education Library.
Australian Catholic University. Alumni Access.
Australian Catholic University.
Australian Institute of Professional Education.
Avondale College. Avondale College of Higher Education Sydney Campus Library.
Blue Mountains International Hotel Management School.
Campion College Australia.
Cengage Education.
Excelsia College. Excelsia College Library.
Kaplan Professional. Library.
Fire & Rescue NSW. FRNSW Library.
International College of Management, Sydney. ICMS Library.
Macquarie University. Macquarie University Library.
Moore Theological College. Moore Theological College Library.
Sydney Missionary and Bible College. J.T.H. Kerr Library.
South Western Sydney Institute of TAFE.
Think: Education Group. Think Education Group Learning Resource Centre.
University of New England. Dixson Library.
University of Wollongong. University of Wollongong Library.
Catholic Institute of Sydney. Veech Library.
Western Sydney University. Hawkesbury Campus Library.
Show 0 more libraries...
Library View online via
Charles Darwin University. Casuarina Campus Library.
Show 0 more libraries...
Library View online via
Bond University. John and Alison Kearney Library .
Christian Heritage College. Christian Heritage College Library.
Australian College of Natural Medicine Pty Ltd. Endeavour College of Natural Health Library.
The Southport School. Senior Library.
University of Queensland. University of Queensland Library. UQ Library Cyberschool.
Show 0 more libraries...
Library View online via
Australian Lutheran College. Lohe Memorial Library.
University of Adelaide. Barr Smith Library.
SA Mental Health Services.
South Australian Research and Development Institute. South Australian Aquatic Sciences Centre Library.
Tabor Adelaide. Tabor College Library.
Show 0 more libraries...
Library View online via
Deakin University. Deakin University Library.
Holmesglen Institute of TAFE. Holmesglen Learning Commons.
Marcus Oldham College. Sir James Darling Resource Centre.
Melbourne Library Service.
Monash University. Monash University Library.
Swinburne University of Technology. Swinburne Library.
Tabor College Victoria.
Show 0 more libraries...

Published in

Some editions of the publication "Distributed computing" are available from these libraries. The edition containing this article ( v.24, no.2, 2011 Oct, p.91(9) ) may not be available:

None of your libraries hold this item.

These 18 locations in All:

Library Access Call number(s) Formats held Language
Australian Nuclear Science and Technology Organisation. ANSTO Library. Not open to the public Held. Check with Library Periodical; Journal, magazine, other English
CAVAL. CARM Centre. May not be open to the public brn.180332; Held; 11(1997)-15:3(2002)Inc. Periodical; Journal, magazine, other English
Charles Sturt University. CSU Library - Electronic Resources (shared). Open to the public 002055076; Full Text Available; Springer Standard Collection - Available from 1997 Periodical; Journal, magazine, other English
Charles Sturt University. Wagga Wagga Campus Library. Open to the public 001099160; P004.36 D5; v.11:no.2(1998:Apr.)-v.18:no.4(2006:Aug.) Periodical; Journal, magazine, other English
CSIRO. Black Mountain Library. May not be open to the public 997462970001981; MACQ P DIS; Vol. 11, no. 2 (1998)-v. 13, no. 3 (2000); v. 16 (2003)-v. 18, no. 4 (Mar. 2006) Periodical; Journal, magazine, other English
CSIRO. Library Services. Not open to the public 999738680001981; ProQuest SciTech Collection. Online Access. Available for document delivery. Restrictions apply.; Available from 2000; Most recent 1 year(s) not available.; ProQuest Central (New). Online Access. Available for document delivery. Restrictions apply.; Available from 2000; Most recent 1 year(s) not available.; Springer Standard Collection. Online Access. Available for document delivery. Restrictions apply.; Available from 1997 Periodical; Journal, magazine, other English
Cumberland Council. Auburn Library. Open to the public Periodical; Journal, magazine, other English
Edith Cowan University. Edith Cowan University Library. Open to the public Periodical; Journal, magazine, other English
Griffith University. Griffith University Library. Open to the public .b16521511; Electronic Resource : Publ. may restrict Doc. Del. Periodical; Journal, magazine, other English
Griffith University. Nathan Campus Library. Open to the public .b16521511; QA76.9.D5 D47 Vol.3 (1988) - vol.16 (2003). Periodical; Journal, magazine, other English
Monash University. Monash University Library. Open to the public 998040401751; 004.3605 D614; v. 1, no. 1 (Jan.1986) to v. 18, no. 4 (Mar. 2006); OS; YOS-SER Periodical; Journal, magazine, other English
NSW Department of Industry. DTIRIS: Electronic Resources Library. Not open to the public V 9 1995- Periodical; Journal, magazine, other English
Shellharbour City Council. Shellharbour City Library Service. Open to the public Held. Not for ILL. Periodical; Journal, magazine, other English
Southern Cross University. University Library Lismore. Open to the public Electronic resource - Check catalogue for holdings Periodical; Journal, magazine, other English
The University of Sydney. University of Sydney Library. Open to the public Periodical; Journal, magazine, other English
University of Queensland. University of Queensland Library. Open to the public .b11895755; psep QA76.9.D5 D47 : 1(1986)-16(2003); Online access via SpringerLink journal archives : (1986-1996). Available for document delivery - restrictions apply; Online access via SpringerLink : (1997)-. Available for document delivery - restrictions apply Periodical; Journal, magazine, other English
University of Tasmania. Open to the public .b12421844; Scien ser v6-v12n1;1992-1999 Periodical; Journal, magazine, other English
University of Western Australia. University of Western Australia Library. Open to the public 9963272102101; HELD; V. 1-21 ; 1986-2009 Periodical; Journal, magazine, other English
Show 0 more libraries...

This single location in Australian Capital Territory:

Library Access Call number(s) Formats held Language
CSIRO. Black Mountain Library. May not be open to the public 997462970001981; MACQ P DIS; Vol. 11, no. 2 (1998)-v. 13, no. 3 (2000); v. 16 (2003)-v. 18, no. 4 (Mar. 2006) Periodical; Journal, magazine, other English
Show 0 more libraries...

These 8 locations in New South Wales:

Library Access Call number(s) Formats held Language
Australian Nuclear Science and Technology Organisation. ANSTO Library. Not open to the public Held. Check with Library Periodical; Journal, magazine, other English
Charles Sturt University. CSU Library - Electronic Resources (shared). Open to the public 002055076; Full Text Available; Springer Standard Collection - Available from 1997 Periodical; Journal, magazine, other English
Charles Sturt University. Wagga Wagga Campus Library. Open to the public 001099160; P004.36 D5; v.11:no.2(1998:Apr.)-v.18:no.4(2006:Aug.) Periodical; Journal, magazine, other English
Cumberland Council. Auburn Library. Open to the public Periodical; Journal, magazine, other English
NSW Department of Industry. DTIRIS: Electronic Resources Library. Not open to the public V 9 1995- Periodical; Journal, magazine, other English
Shellharbour City Council. Shellharbour City Library Service. Open to the public Held. Not for ILL. Periodical; Journal, magazine, other English
Southern Cross University. University Library Lismore. Open to the public Electronic resource - Check catalogue for holdings Periodical; Journal, magazine, other English
The University of Sydney. University of Sydney Library. Open to the public Periodical; Journal, magazine, other English
Show 0 more libraries...
None of your libraries hold this item.

These 3 locations in Queensland:

Library Access Call number(s) Formats held Language
Griffith University. Griffith University Library. Open to the public .b16521511; Electronic Resource : Publ. may restrict Doc. Del. Periodical; Journal, magazine, other English
Griffith University. Nathan Campus Library. Open to the public .b16521511; QA76.9.D5 D47 Vol.3 (1988) - vol.16 (2003). Periodical; Journal, magazine, other English
University of Queensland. University of Queensland Library. Open to the public .b11895755; psep QA76.9.D5 D47 : 1(1986)-16(2003); Online access via SpringerLink journal archives : (1986-1996). Available for document delivery - restrictions apply; Online access via SpringerLink : (1997)-. Available for document delivery - restrictions apply Periodical; Journal, magazine, other English
Show 0 more libraries...
None of your libraries hold this item.

This single location in Tasmania:

Library Access Call number(s) Formats held Language
University of Tasmania. Open to the public .b12421844; Scien ser v6-v12n1;1992-1999 Periodical; Journal, magazine, other English
Show 0 more libraries...

These 3 locations in Victoria:

Library Access Call number(s) Formats held Language
CAVAL. CARM Centre. May not be open to the public brn.180332; Held; 11(1997)-15:3(2002)Inc. Periodical; Journal, magazine, other English
CSIRO. Library Services. Not open to the public 999738680001981; ProQuest SciTech Collection. Online Access. Available for document delivery. Restrictions apply.; Available from 2000; Most recent 1 year(s) not available.; ProQuest Central (New). Online Access. Available for document delivery. Restrictions apply.; Available from 2000; Most recent 1 year(s) not available.; Springer Standard Collection. Online Access. Available for document delivery. Restrictions apply.; Available from 1997 Periodical; Journal, magazine, other English
Monash University. Monash University Library. Open to the public 998040401751; 004.3605 D614; v. 1, no. 1 (Jan.1986) to v. 18, no. 4 (Mar. 2006); OS; YOS-SER Periodical; Journal, magazine, other English
Show 0 more libraries...
None of your libraries hold this item.

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment