1 Search Results for "Gorain, Barun"


Document
Deterministic Graph Exploration with Advice

Authors: Barun Gorain and Andrzej Pelc

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)


Abstract
We consider the task of graph exploration. An n-node graph has unlabeled nodes, and all ports at any node of degree d are arbitrarily numbered 0,..., d-1. A mobile agent has to visit all nodes and stop. The exploration time is the number of edge traversals. We consider the problem of how much knowledge the agent has to have a priori, in order to explore the graph in a given time, using a deterministic algorithm. This a priori information (advice) is provided to the agent by an oracle, in the form of a binary string, whose length is called the size of advice. We consider two types of oracles. The instance oracle knows the entire instance of the exploration problem, i.e., the port-numbered map of the graph and the starting node of the agent in this map. The map oracle knows the port-numbered map of the graph but does not know the starting node of the agent. What is the minimum size of advice that must be given to the agent by each of these oracles, so that the agent explores the graph in a given time? We first consider exploration in polynomial time, and determine the exact minimum size of advice to achieve it. This size is log(log(log(n))) - Theta(1), for both types of oracles. When advice is large, there are two natural time thresholds: Theta(n^2) for a map oracle, and Theta(n) for an instance oracle, that can be achieved with sufficiently large advice. We show that, with a map oracle, time Theta(n^2) cannot be improved in general, regardless of the size of advice. We also show that the smallest size of advice to achieve this time is larger than n^delta, for any delta <1/3. For an instance oracle, advice of size O(n*log(n)) is enough to achieve time O(n). We show that, with any advice of size o(n*log(n)), the time of exploration must be at least n^epsilon, for any epsilon <2, and with any advice of size O(n), the time must be Omega(n^2). We also investigate minimum advice sufficient for fast exploration of Hamiltonian graphs.

Cite as

Barun Gorain and Andrzej Pelc. Deterministic Graph Exploration with Advice. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 132:1-132:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{gorain_et_al:LIPIcs.ICALP.2017.132,
  author =	{Gorain, Barun and Pelc, Andrzej},
  title =	{{Deterministic Graph Exploration with Advice}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{132:1--132:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.132},
  URN =		{urn:nbn:de:0030-drops-73701},
  doi =		{10.4230/LIPIcs.ICALP.2017.132},
  annote =	{Keywords: algorithm, graph, exploration, mobile agent, advice}
}
  • Refine by Author
  • 1 Gorain, Barun
  • 1 Pelc, Andrzej

  • Refine by Classification

  • Refine by Keyword
  • 1 advice
  • 1 algorithm
  • 1 exploration
  • 1 graph
  • 1 mobile agent

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail