scientific article; zbMATH DE number 4049076
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.
- Cube intersection concepts in median graphs
- Amortized efficiency of a path retrieval data structure
- An on-line graph coloring algorithm with sublinear performance ratio
- A new fixed point approach for stable networks and stable marriages
- Recognizing median graphs in subquadratic time
- On the natural imprint function of a graph
- Clique-gated graphs
- The majority strategy on graphs
- Quasi-median graphs, their generalizations, and tree-like equalities
- Semi-dynamic breadth-first search in digraphs
- On median nature and enumerative properties of Fibonacci-like cubes
- Peripheral convex expansions of resonance graphs
- Graph Searching in a Crime Wave
- Quasi‐median graphs and algebras
- Dynamic lookup networks
- Efficient search in graph databases using cross filtering
- Dynamic resource location with tropical algebra
- A dynamic location problem for graphs
- Dynamic location problems with limited look-ahead
- Cost thresholds for dynamic resource location
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)