NDLI: Deterministic Rendezvous in Graphs

Content Provider	Springer Nature Link
Author	Dessmark, Anders Fraigniaud, Pierre Kowalski, Dariusz R. Pelc, Andrzej
Copyright Year	2006
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.
Starting Page	69
Ending Page	96
Page Count	28
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	46
Issue Number	1
e-ISSN	14320541
Language	English
Publisher	Springer-Verlag
Publisher Date	2006-06-19
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory Theory of Computation Algorithm Analysis and Problem Complexity Mathematics of Computing Algorithms
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Deterministic Communication in Radio Networks with Large Labels

Using Nondeterminism to Design Efficient Deterministic Algorithms

Cleaning Interval Graphs

Drawing Planar Graphs Symmetrically, II: Biconnected Planar Graphs

Anonymous Meeting in Networks

Motorcycle Graphs and Straight Skeletons

Detecting Holes and Antiholes in Graphs

Rigid Components in Molecular Graphs

Disk Embeddings of Planar Graphs

Deterministic Rendezvous in Graphs

Similar Documents

Deterministic Communication in Radio Networks with Large Labels

Using Nondeterminism to Design Efficient Deterministic Algorithms

Cleaning Interval Graphs

Drawing Planar Graphs Symmetrically, II: Biconnected Planar Graphs

Anonymous Meeting in Networks

Motorcycle Graphs and Straight Skeletons

Detecting Holes and Antiholes in Graphs

Rigid Components in Molecular Graphs

Disk Embeddings of Planar Graphs

Deterministic Rendezvous in Graphs