Source author record

Ram Narayan Yadav

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

2works

3topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Advice Complexity of Treasure Hunt in Geometric Terrains

Treasure hunt is the task of finding an inert target by a mobile agent in an unknown environment. We consider treasure hunt in geometric terrains with obstacles. Both the terrain and the obstacles are modeled as polygons and both the agent and the treasure are modeled as points. The agent navigates in the terrain, avoiding obstacles, and finds the treasure when there is a segment of length at most 1 between them, unobstructed by the boundary of the terrain or by the obstacles. The cost of finding the treasure is the length of the trajectory of the agent. We investigate the amount of information that the agent needs a priori in order to find the treasure at cost $O(L)$ , where $L$ is the length of the shortest path in the terrain from the initial position of the agent to the treasure, avoiding obstacles. Following the paradigm of algorithms with advice, this information is given to the agent in advance as a binary string, by an oracle cooperating with the agent and knowing the whole environment: the terrain, the position of the treasure and the initial position of the agent. Advice complexity of treasure hunt is the minimum length of the advice string (up to multiplicative constants) that enables the agent to find the treasure at cost $O(L)$ . We first consider treasure hunt in regular terrains which are defined as convex polygons with convex $c$ -fat obstacles, for some constant $c>1$ . A polygon is $c$ -fat if the ratio of the radius of the smallest disc containing it to the radius of the largest disc contained in it is at most $c$ . For the class of regular terrains, we establish the exact advice complexity of treasure hunt. We then show that advice complexity of treasure hunt for the class of arbitrary terrains (even for non-convex polygons without obstacles, and even for those with only horizontal or vertical sides) is exponentially larger than for regular terrains.

preprint2020arXiv

Deterministic Leader Election in Anonymous Radio Networks

We consider leader election in anonymous radio networks modeled as simple undirected connected graphs. Nodes communicate in synchronous rounds. Nodes are anonymous and execute the same deterministic algorithm, so symmetry can be broken only in one way: by different wake-up times of the nodes. In which situations is it possible to break symmetry and elect a leader using time as symmetry breaker? To answer this question, we consider configurations. A configuration is the underlying graph with nodes tagged by non-negative integers with the following meaning. A node can either wake up spontaneously in the round shown on its tag, according to some global clock, or can be woken up hearing a message sent by one of its already awoken neighbours. The local clock of a node starts at its wakeup and nodes do not have access to the global clock determining their tags. A configuration is feasible if there exists a distributed algorithm that elects a leader for this configuration. Our main result is a complete algorithmic characterization of feasible configurations: we design a centralized decision algorithm, working in polynomial time, whose input is a configuration and which decides if the configuration is feasible. We also provide a dedicated deterministic distributed leader election algorithm for each feasible configuration that elects a leader for this configuration in time $O(n^2σ)$ , where $n$ is the number of nodes and $σ$ is the difference between the largest and smallest tag of the configuration. We then prove that there cannot exist a universal deterministic distributed algorithm electing a leader for all feasible configurations. In fact, we show that such a universal algorithm cannot exist even for the class of 4-node feasible configurations. We also prove that a distributed version of our decision algorithm cannot exist.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.