Source author record

Maxim Babenko

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

Catalog footprint

Research overview

5works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

On the Complexity of Hub Labeling

Hub Labeling (HL) is a data structure for distance oracles. Hierarchical HL (HHL) is a special type of HL, that received a lot of attention from a practical point of view. However, theoretical questions such as NP-hardness and approximation guarantee for HHL algorithms have been left aside. In this paper we study HL and HHL from the complexity theory point of view. We prove that both HL and HHL are NP-hard, and present upper and lower bounds for the approximation ratios of greedy HHL algorithms used in practice. We also introduce a new variant of the greedy HHL algorithm and a proof that it produces small labels for graphs with small highway dimension.

preprint2015arXiv

Wavelet Trees Meet Suffix Trees

We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n over an alphabet of size $σ\leq n$ , our method builds the wavelet tree in $O(n \log σ/ \sqrt{\log{n}})$ time, improving upon the state-of-the-art algorithm by a factor of $\sqrt{\log n}$ . As a consequence, given an array of n integers we can construct in $O(n \sqrt{\log n})$ time a data structure consisting of $O(n)$ machine words and capable of answering rank/select queries for the subranges of the array in $O(\log n / \log \log n)$ time. This is a $\log \log n$ -factor improvement in query time compared to Chan and Pătraşcu and a $\sqrt{\log n}$ -factor improvement in construction time compared to Brodal et al. Next, we switch to stringological context and propose a novel notion of wavelet suffix trees. For a string w of length n, this data structure occupies $O(n)$ words, takes $O(n \sqrt{\log n})$ time to construct, and simultaneously captures the combinatorial structure of substrings of w while enabling efficient top-down traversal and binary search. In particular, with a wavelet suffix tree we are able to answer in $O(\log |x|)$ time the following two natural analogues of rank/select queries for suffixes of substrings: for substrings x and y of w count the number of suffixes of x that are lexicographically smaller than y, and for a substring x of w and an integer k, find the k-th lexicographically smallest suffix of x. We further show that wavelet suffix trees allow to compute a run-length-encoded Burrows-Wheeler transform of a substring x of w in $O(s \log |x|)$ time, where s denotes the length of the resulting run-length encoding. This answers a question by Cormode and Muthukrishnan, who considered an analogous problem for Lempel-Ziv compression.

preprint2013arXiv

Substring Suffix Selection

We study the following substring suffix selection problem: given a substring of a string T of length n, compute its k-th lexicographically smallest suffix. This a natural generalization of the well-known question of computing the maximal suffix of a string, which is a basic ingredient in many other problems. We first revisit two special cases of the problem, introduced by Babenko, Kolesnichenko and Starikovskaya [CPM'13], in which we are asked to compute the minimal non-empty and the maximal suffixes of a substring. For the maximal suffixes problem, we give a linear-space structure with O(1) query time and linear preprocessing time, i.e., we manage to achieve optimal construction and optimal query time simultaneously. For the minimal suffix problem, we give a linear-space data structure with O(τ) query time and O(n log n / τ) preprocessing time, where 1 <= τ<= log n is a parameter of the data structure. As a sample application, we show that this data structure can be used to compute the Lyndon decomposition of any substring of T in O(k τ) time, where k is the number of distinct factors in the decomposition. Finally, we move to the general case of the substring suffix selection problem, where using any combinatorial properties seems more difficult. Nevertheless, we develop a linear-space data structure with O(log^{2+ε} n) query time.

preprint2010arXiv

A Linear Time Algorithm for Finding Three Edge-Disjoint Paths in Eulerian Networks

Consider an undirected graph $G = (VG, EG)$ and a set of six \emph{terminals} $T = \set{s_1, s_2, s_3, t_1, t_2, t_3} \subseteq VG$ . The goal is to find a collection $\calP$ of three edge-disjoint paths $P_1$ , $P_2$ , and $P_3$ , where $P_i$ connects nodes $s_i$ and $t_i$ ( $i = 1, 2, 3$ ). Results obtained by Robertson and Seymour by graph minor techniques imply a polynomial time solvability of this problem. The time bound of their algorithm is $O(m^3)$ (hereinafter we assume $n := \abs{VG}$, $m := \abs{EG}$, $n = O(m)$ ). In this paper we consider a special, \emph{Eulerian} case of $G$ and $T$ . Namely, construct the \emph{demand graph} $H = (VG, \set{s_1t_1, s_2t_2, s_3t_3})$ . The edges of $H$ correspond to the desired paths in $\calP$. In the Eulerian case the degrees of all nodes in the (multi-) graph $G + H$ ( $= (VG, EG \cup EH)$ ) are even. Schrijver showed that, under the assumption of Eulerianess, cut conditions provide a criterion for the existence of $\calP$. This, in particular, implies that checking for existence of $\calP$ can be done in $O(m)$ time. Our result is a combinatorial $O(m)$ -time algorithm that constructs $\calP$ (if the latter exists).

preprint2010arXiv

Triangle-Free 2-Matchings Revisited

A \emph{2-matching} in an undirected graph $G = (VG, EG)$ is a function $f \colon EG \to \set{0,1,2}$ such that for each node $v \in VG$ the sum of values $f(e)$ on all edges $e$ incident to $v$ does not exceed~2. The \emph{size} of $f$ is the sum $\sum_e f(e)$ . If $\set{e \in EG \mid f(e) \ne 0}$ contains no triangles then $f$ is called \emph{triangle-free}. Cornuéjols and Pulleyblank devised a combinatorial $O(mn)$ -algorithm that finds a triangle free 2-matching of maximum size (hereinafter $n := \abs{VG}$, $m := \abs{EG}$) and also established a min-max theorem. We claim that this approach is, in fact, superfluous by demonstrating how their results may be obtained directly from the Edmonds--Gallai decomposition. Applying the algorithm of Micali and Vazirani we are able to find a maximum triangle-free 2-matching in $O(m\sqrt{n})$ -time. Also we give a short self-contained algorithmic proof of the min-max theorem. Next, we consider the case of regular graphs. It is well-known that every regular graph admits a perfect 2-matching. One can easily strengthen this result and prove that every $d$ -regular graph (for $d \geq 3$ ) contains a perfect triangle-free 2-matching. We give the following algorithms for finding a perfect triangle-free 2-matching in a $d$ -regular graph: an O(n)-algorithm for $d = 3$ , an $O(m + n^{3/2})$ -algorithm for $d = 2k$ ( $k \ge 2$ ), and an $O(n^2)$ -algorithm for $d = 2k + 1$ ( $k \ge 2$ ). We also prove that there exists a constant $c > 1$ such that every 3-regular graph contains at least $c^n$ perfect triangle-free 2-matchings.

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.