Source author record

Ralf Klasing

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.CO Discrete Mathematics

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Improved Analysis of Deterministic Load-Balancing Schemes

We consider the problem of deterministic load balancing of tokens in the discrete model. A set of $n$ processors is connected into a $d$ -regular undirected network. In every time step, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible. Rabani et al. (1998) present a general technique for the analysis of a wide class of discrete load balancing algorithms. Their approach is to characterize the deviation between the actual loads of a discrete balancing algorithm with the distribution generated by a related Markov chain. The Markov chain can also be regarded as the underlying model of a continuous diffusion algorithm. Rabani et al. showed that after time $T = O(\log (Kn)/μ)$ , any algorithm of their class achieves a discrepancy of $O(d\log n/μ)$ , where $μ$ is the spectral gap of the transition matrix of the graph, and $K$ is the initial load discrepancy in the system. In this work we identify some natural additional conditions on deterministic balancing algorithms, resulting in a class of algorithms reaching a smaller discrepancy. This class contains well-known algorithms, eg., the Rotor-Router. Specifically, we introduce the notion of cumulatively fair load-balancing algorithms where in any interval of consecutive time steps, the total number of tokens sent out over an edge by a node is the same (up to constants) for all adjacent edges. We prove that algorithms which are cumulatively fair and where every node retains a sufficient part of its load in each step, achieve a discrepancy of $O(\min\{d\sqrt{\log n/μ},d\sqrt{n}\})$ in time $O(T)$ . We also show that in general neither of these assumptions may be omitted without increasing discrepancy. We then show by a combinatorial potential reduction argument that any cumulatively fair scheme satisfying some additional assumptions achieves a discrepancy of $O(d)$ almost as quickly as the continuous diffusion process. This positive result applies to some of the simplest and most natural discrete load balancing schemes.

preprint2014arXiv

Centroidal bases in graphs

We introduce the notion of a centroidal locating set of a graph $G$ , that is, a set $L$ of vertices such that all vertices in $G$ are uniquely determined by their relative distances to the vertices of $L$ . A centroidal locating set of $G$ of minimum size is called a centroidal basis, and its size is the centroidal dimension $CD(G)$ . This notion, which is related to previous concepts, gives a new way of identifying the vertices of a graph. The centroidal dimension of a graph $G$ is lower- and upper-bounded by the metric dimension and twice the location-domination number of $G$ , respectively. The latter two parameters are standard and well-studied notions in the field of graph identification. We show that for any graph $G$ with $n$ vertices and maximum degree at least~2, $(1+o(1))\frac{\ln n}{\ln\ln n}\leq CD(G) \leq n-1$ . We discuss the tightness of these bounds and in particular, we characterize the set of graphs reaching the upper bound. We then show that for graphs in which every pair of vertices is connected via a bounded number of paths, $CD(G)=Ω\left(\sqrt{|E(G)|}\right)$ , the bound being tight for paths and cycles. We finally investigate the computational complexity of determining $CD(G)$ for an input graph $G$ , showing that the problem is hard and cannot even be approximated efficiently up to a factor of $o(\log n)$ . We also give an $O\left(\sqrt{n\ln n}\right)$ -approximation algorithm.

preprint2014arXiv

Rendezvous of Heterogeneous Mobile Agents in Edge-weighted Networks

We introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal times for the other agent. The goal of the agents is to meet on an edge or a node of the graph. In this scenario, we study the time required by the agents to meet, compared to the meeting time $T_{OPT}$ in the offline scenario in which the agents have complete knowledge about each others speed characteristics. When no additional assumptions are made, we show that rendezvous in our model can be achieved after time $O(n T_{OPT})$ in a $n$ -node graph, and that such time is essentially in some cases the best possible. However, we prove that the rendezvous time can be reduced to $Θ(T_{OPT})$ when the agents are allowed to exchange $Θ(n)$ bits of information at the start of the rendezvous process. We then show that under some natural assumption about the traversal times of edges, the hardness of the heterogeneous rendezvous problem can be substantially decreased, both in terms of time required for rendezvous without communication, and the communication complexity of achieving rendezvous in time $Θ(T_{OPT})$ .

preprint2012arXiv

On the size of identifying codes in triangle-free graphs

In an undirected graph $G$ , a subset $C\subseteq V(G)$ such that $C$ is a dominating set of $G$ , and each vertex in $V(G)$ is dominated by a distinct subset of vertices from $C$ , is called an identifying code of $G$ . The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph $G$ , let $\M(G)$ be the minimum cardinality of an identifying code in $G$ . In this paper, we show that for any connected identifiable triangle-free graph $G$ on $n$ vertices having maximum degree $Δ\geq 3$ , $\M(G)\le n-\tfrac{n}{Δ+o(Δ)}$. This bound is asymptotically tight up to constants due to various classes of graphs including $(Δ-1)$ -ary trees, which are known to have their minimum identifying code of size $n-\tfrac{n}{Δ-1+o(1)}$ . We also provide improved bounds for restricted subfamilies of triangle-free graphs, and conjecture that there exists some constant $c$ such that the bound $\M(G)\le n-\tfrac{n}Δ+c$ holds for any nontrivial connected identifiable graph $G$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.