Sequences of Radius k for Complete Bipartite Graphs

Michał Dębski , Zbigniew Lonc , Paweł Rzążewski


Let $G$ be a graph. A emph{$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})leq(1+epsilon)d_kfrac{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)geq d_kfrac{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$.
Author Michał Dębski ZAK
Michał Dębski,,
- Department of Algebra and Combinatorics
, Zbigniew Lonc ZAK
Zbigniew Lonc,,
- Department of Algebra and Combinatorics
, Paweł Rzążewski ZSPI
Paweł Rzążewski,,
- Department of Information Processing Systems
Publication size in sheets0.55
Book Heggernes Pinar (eds.): GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2016, vol. 9941, 2016, SPRINGER INT PUBLISHING AG, ISBN 978-3-662-53536-3, [978-3-662-53535-6]
Keywords in Englishsequence, k-radius sequences, bipartite graphs, maximum cut
Abstract in PolishCiągiem o promieniu k dla grafu G nazywamy ciąg wierzchołków grafu G (z możliwymi powtórzeniami), w którym końce każdej krawędzi występują jako elementy oddalone o co najwyżej k. W pracy pokazujemy, że problem znajdowania najkrótszego takiego ciągu jest problemem NP-trudnym. Ponadto pokazujemy dolne i górne ograniczenia na długość najkrótszego ciągu o promieniu k dla grafów pełnych dwudzielnych.
Languageen angielski
Score (nominal)15
ScoreMinisterial score = 15.0, 27-06-2017, BookChapterMatConf
Ministerial score (2013-2016) = 15.0, 27-06-2017, BookChapterMatConf
Citation count*0
Share Share

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.