scientific article; zbMATH DE number 4049076

From MaRDI portal
Publication:3785965





Suppose G is a fixed finite connected graph and for any two vertices x and y in G, \(d_ G(x,y)\) denotes the distance in G between x and y, i.e., the number of edges in a shortest path connecting x and y. Given an infinite sequence \(Q=(q_ 1,q_ 2,...)\) of vertices in G, suppose we would like to find another sequence \(P=P_ Q=(p_ 0,p_ 1,...)\) of vertices so that the quantity \[ \nu (P)\quad =\limsup_{N\to \infty}N^{-1}\sum^{N}_{i=1}(d(p_{i-1},p_ i)+d(p_ i,q_ i)) \] is as small as possible. This question represents a general formulation of a class of problems arising in self-adjusting data structures. In this paper we will investigate this and a number of related graph searching problems, such as requiring \(p_ n\) to be chosen before \(q_{n+i}\), \(i\geq k\), is known, and show how a number of interesting structural and algorithmic concepts from graph theory come together rather naturally, e.g., isometric embedding, Steiner points in graphs, retracts, diameters and linear programming.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3785965)