Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Sequences of Radius k for Complete Bipartite Graphs
verfasst von : Michał Dębski, Zbigniew Lonc, Paweł Rzążewski
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 \(f_k(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 \(f_k(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 \(f_k(G)\) for complete bipartite graphs. We show that for every \(\epsilon >0\) we have \(f_k(K_{m,n})\le (1+\epsilon )d_k\frac{mn}{k}\), provided that both m and n are sufficiently large – where \(d_k\) depends only on k. This upper bound asymptotically coincides with the lower bound \(f_k(G)\ge d_k\frac{e(G)}{k}\), valid for all bipartite graphs.
We also show that determining \(f_k(G)\) for an arbitrary graph G is NP-hard for every constant \(k>1\).