Search

Let S be a family of subsets of a set X of cardinality m and VC-dim (S) be the Vapnik–Chervonenkis dimension of S. Haussler et al. (1994) proved that if G 1 (S) = (V , E) is the subgraph of the hypercube Q m induced by S (called the 1-inclusion graph of S), then | E | | V | ≤ VC-dim (S). Haussler (1995) presented an elegant proof of this inequality using the shifting operation. In this note, we adapt the shifting technique to prove that if S is an arbitrary set family and G 1 , 2 (S) = (V , E) is the 1,2-inclusion graph of S (i.e., the subgraph of the square Q m 2 of the hypercube Q m induced by S), then | E | | V | ≤ d 2 , where d ≔ cVC-dim ∗ (S) is the clique-VC-dimension of S (which we introduce in this paper). The 1,2-inclusion graphs are exactly the subgraphs of halved cubes and comprise subgraphs of Johnson graphs as a subclass. [ABSTRACT FROM AUTHOR]

k -Approximate distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the k -approximation of the distance between any two vertices u and v can be determined efficiently by merely inspecting the labels of u and v , without using any other information. One of the important problems is finding natural classes of graphs admitting exact or approximate distance labeling schemes with labels of polylogarithmic size. In this paper, we describe a 4-approximate distance labeling scheme for the class of K 4 -free bridged graphs. This scheme uses labels of poly-logarithmic length O (log ⁡ n 3) allowing a constant decoding time. Given the labels of two vertices u and v , the decoding function returns a value between the exact distance d G (u , v) and its quadruple 4 d G (u , v). [ABSTRACT FROM AUTHOR]

Abstract: A mobile robot, represented by a point moving along a polygonal line in the plane, has to explore an unknown polygon and return to the starting point. The robot has a sensing area which can be a circle or a square centered at the robot. This area shifts while the robot moves inside the polygon, and at each point of its trajectory the robot “sees” (explores) all points for which the segment between the robot and the point is contained in the polygon and in the sensing area. We focus on two tasks: exploring the entire polygon and exploring only its boundary. We consider several scenarios: both shapes of the sensing area and the Manhattan and the Euclidean metrics. We focus on two quality benchmarks for exploration performance: optimality (the length of the trajectory of the robot is equal to that of the optimal robot knowing the polygon) and competitiveness (the length of the trajectory of the robot is at most a constant multiple of that of the optimal robot knowing the polygon). Most of our results concern rectilinear polygons. We show that optimal exploration is possible in only one scenario, that of exploring the boundary by a robot with square sensing area, starting at the boundary and using the Manhattan metric. For this case we give an optimal exploration algorithm, and in all other scenarios we prove impossibility of optimal exploration. For competitiveness the situation is more optimistic: we show a competitive exploration algorithm for rectilinear polygons whenever the sensing area is a square, for both tasks, regardless of the metric and of the starting point. Finally, we show a competitive exploration algorithm for arbitrary convex polygons, for both shapes of the sensing area, regardless of the metric and of the starting point. [Copyright &y& Elsevier]

Abstract: A mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q is at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity , where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity , where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains (if one of the parameters A or k is known) or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. (A terrain with obstacles is c-fat if , where R is the radius of the smallest disc containing and r is the radius of the largest disc contained in .) We also prove a matching lower bound on the complexity of exploration for limited vision, even if the terrain is known to the robot. [Copyright &y& Elsevier]