Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Dessmark, Anders
Fraigniaud, Pierre
Kowalski, Dariusz
Pelc, Andrzej

dblp
dblp
dblp
dblp

Not MPG Author(s):

Dessmark, Anders
Fraigniaud, Pierre
Pelc, Andrzej

BibTeX cite key*:

DFKP2006

Title

Title*:

Deterministic Rendezvous in Graphs

Journal

Journal Title*:

Algorithmica

Journal's URL:


Download URL
for the article:

http://www.springerlink.com/content/21088gl733452723/fulltext.pdf

Language:

English

Publisher

Publisher's
Name:


Publisher's URL:


Publisher's
Address:


ISSN:

0178-4617

Vol, No, pp, Date

Volume*:

46

Number:

1

Publishing Date:

2006

Pages*:

69-96

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:

Part of this work was published in ISAAC 2004.

(LaTeX) Abstract:

Two mobile agents having distinct identifiers and located in nodes of an unknown anonymous connected graph, have to meet at some node of the graph. We seek fast deterministic algorithms for this rendezvous problem, under two scenarios: simultaneous startup, when both agents start executing the algorithm at the same time, and arbitrary startup, when starting times of the agents are arbitrarily decided by an adversary. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of steps since the startup of the later agent until rendezvous is achieved. We first show that rendezvous can be completed at cost O(n + log l) on any n-node tree, where l is the smaller of the two identifiers, even with arbitrary startup. This complexity of the cost cannot be improved for some trees, even with simultaneous startup. Efficient rendezvous in trees relies on fast network exploration and cannot be used when the graph contains cycles. We further study the simplest such network, i.e., the ring. We prove that, with simultaneous startup, optimal cost of rendezvous on any ring is Θ(D log l), where D is the initial distance between agents. We also establish bounds on rendezvous cost in rings with arbitrary startup. For arbitrary connected graphs, our main contribution is a deterministic rendezvous algorithm with cost polynomial in n, τ and log l, where τ is the difference between startup times of the agents. We also show a lower bound Ω (n2) on the cost of rendezvous in some family of graphs. If simultaneous startup is assumed, we construct a generic rendezvous algorithm, working for all connected graphs, which is optimal for the class of graphs of bounded degree, if the initial distance between agents is bounded.

URL for the Abstract:

http://portal.acm.org/citation.cfm?id=1165000.1165008&coll=ACM&dl=ACM&CFID=15151515&CFTOKEN=6184618
http://www.springerlink.com/content/21088gl733452723/

Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{DFKP2006,
AUTHOR = {Dessmark, Anders and Fraigniaud, Pierre and Kowalski, Dariusz and Pelc, Andrzej},
TITLE = {Deterministic Rendezvous in Graphs},
JOURNAL = {Algorithmica},
YEAR = {2006},
NUMBER = {1},
VOLUME = {46},
PAGES = {69--96},
ISBN = {0178-4617},
NOTE = {Part of this work was published in ISAAC 2004.},
}


Entry last modified by Uwe Brahm, 07/18/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Ulrich Meyer
Created
02/05/2007 07:27:21 PM
Revisions
10.
9.
8.
7.
6.
Editor(s)
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
2007-07-18 14:46:36
07/07/2007 00:46:03
05.02.2007 19:34:40
05.02.2007 19:33:41
05.02.2007 19:27:14