Computer Science – Data Structures and Algorithms
Scientific paper
2012-04-13
Computer Science
Data Structures and Algorithms
20 pages, 7 figures
Scientific paper
The graph exploration problem is to visit all the nodes of a connected graph by a mobile entity, e.g., a robot. The robot has no a priori knowledge of the topology of the graph or of its size. Cohen et al. \cite{Ilcinkas08} introduced label guided graph exploration which allows the system designer to add short labels to the graph nodes in a preprocessing stage; these labels can guide the robot in the exploration of the graph. In this paper, we address the problem of adjustable 1-bit label guided graph exploration. We focus on the labeling schemes that not only enable a robot to explore the graph but also allow the system designer to adjust the ratio of the number of different labels. This flexibility is necessary when maintaining different labels may have different costs or when the ratio is pre-specified. We present 1-bit labeling (two colors, namely black and white) schemes for this problem along with a labeling algorithm for generating the required labels. Given an $n$-node graph and a rational number $\rho$, we can design a 1-bit labeling scheme such that $n/b\geq \rho$ where $b$ is the number of nodes labeled black. The robot uses $O(\rho\log\Delta)$ bits of memory for exploring all graphs of maximum degree $\Delta$. The exploration is completed in time $O(n\Delta^{\frac{16\rho+7}{3}}/\rho+\Delta^{\frac{40\rho+10}{3}})$. Moreover, our labeling scheme can work on graphs containing loops and multiple edges, while that of Cohen et al. focuses on simple graphs.
Tang Jijun
Zhang Meng
Zhang Yi
No associations
LandOfFree
Label-Guided Graph Exploration with Adjustable Ratio of Labels does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Label-Guided Graph Exploration with Adjustable Ratio of Labels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Label-Guided Graph Exploration with Adjustable Ratio of Labels will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-143934