Memory Paging for Connectivity and Path Problems in Graphs
Esteban Feuerstein, Alberto Marchetti-Spaccamela · Journal of Graph Algorithms and Applications · 1998
We extend the Paging Problem to the case in which the items that are stored in the cache memory represent information about a graph. We propose on-line algorithms for two dierent connectivity problems in this context, for particular classes of graphs and under dierent cost assumptions. In the Path-paging problem we assume that the cache contains edges of the graph and queries to be answered are of the kind \\report a path from i to j"; to answer the query it is necessary to have in memory all the edges of a path from i to j. In this case the answer to a query is not a single piece of information stored in memory. In the Connectivity problem the edges of the transitive closure of a given graph are stored in memory and we want to answer connectivity queries. In order to positively answer connectivity queries of the type \\is i connected with j?", it is possible to answer the query even if the cache does not contain the edge (i; j). Most of our algorithms are optimal and fairly simple. Co...