Graph Theoretic Concepts in Computer Science
Let G be a graph. A k radius sequence for G is a sequence of vertices of G such that for every edge uv of G vertices u and v appear at least once within distance k in the sequence. The length of a shortest k radius sequence for G is denoted by fk(G) Such sequences appear in a problem related to computing values of some 2 argument functions. Suppose we have a set V of large objects, stored in an external database, and our cache can accommodate at most k 1 objects from V at one time. If we are given a set E of pairs of objects for which we want to compute the value of some 2 argument function, and assume that our cache is managed in FIFO manner, then fk(G) (where G (V, E) is the minimum number of times we need to copy an object from the database to the cache. We give an asymptotically tight estimation on fk(G) for complete bipartite graphs. We show that for every 0 we have fk(Km,n) (1 )dk mn k provided that both m and n are sufficiently large where dk depends only on k. This upper bound asymptotically coincides with the lower bound fk(G) dk e(G) k valid for all bipartite graphs. We also show that determining fk(G) for an arbitrary graph G is NP hard for every constant k 1.
Lecture Notes in Computer Science