Let G = (V, E) be an undirected graph, a subset of vertices T be a set of terminals. Then a natural combinatorial problem consists in finding the maximum number of vertex-disjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum non-bipartite matching and thus gives an O(mn^1/2 log(n^2/m)/log(n))-time algorithm (hereinafter n := |V|, m := |E|). Now let us consider the fractional relaxation, i.e. allow T-path packings with arbitrary nonnegative real weights. It is known that there always exists a half-integral solution, that is, one only needs to assign weights 0, 1/2, 1 to maximize the total weight of T-paths. It is also known that an optimum half-integral packing can be found in strongly-polynomial time but the actual time bounds are far from being satisfactory. In this paper we present a novel algorithm that solves the half-integral problem within O(mn^1/2 log(n^2/m)/log(n)) time, thus matching the complexities of integral and half-integral versions.

We consider the hub label optimization problem, which arises in designing fast preprocessing-based shortest-path algorithms. We give O (log n )-approximation algorithms for the objectives of minimizing the maximum label size (ℓ ∞ -norm) and simultaneously minimizing a constant number of ℓ p -norms. Prior to this, an O (log n )-approximation algorithm was known [Cohen et al. 2003] only for minimizing the total label size (ℓ 1 -norm).

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 σ ≤ n, our method builds the wavelet tree in time, improving upon the state-of-the-art algorithm by a factor of . As a consequence, given an array of n integers we can construct in time a data structure consisting of (n) machine words and capable of answering rank/select queries for the subranges of the array in (log n/log log n) time. This is a log log n-factor improvement in query time compared to Chan and Pâtraşcu (SODA 2010) and a -factor improvement in construction time compared to Brodal et al. (Theor. Comput. Sci. 2011). 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 (n) words, takes 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 (log |x|) time the following two natural analogues of rank/select queries for suffixes of substrings: 1.1) For substrings x and y of w (given by their endpoints) count the number of suffixes of x that are lexicographically smaller than y;2.2) For a substring x of w (given by its endpoints) 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 (again, given by its endpoints) in (s log |x|) time, where s denotes the length of the resulting run-length encoding. This answers a question by Cormode and Muthukrishnan (SODA 2005), who considered an analogous problem for Lempel-Ziv compression. All our algorithms, except for the construction of wavelet suffix trees, which additionally requires (n) time in expectation, are deterministic and operate in the word RAM model.

By a T-star we mean a complete bipartite graph K_{1,t} for some t <= T. For an undirected graph G, a T-star packing is a collection of node-disjoint T-stars in G. For example, we get ordinary matchings for $T = 1$ and packings of paths of length 1 and 2 for $T = 2$. Hereinafter we assume that T >= 2. Hell and Kirkpatrick devised an ad-hoc augmenting algorithm that finds a T-star packing covering the maximum number of nodes. The latter algorithm also yields a min-max formula. We show that T-star packings are reducible to network flows, hence the above problem is solvable in $O(m sqrt(n))$ time (hereinafter n denotes the number of nodes in G, and m --- the number of edges). For the edge-weighted case (in which weights may be assumed positive) finding a maximum $T$-packing is NP-hard. A novel 9/4 T/(T + 1)-factor approximation algorithm is presented. For non-negative node weights the problem reduces to a special case of a max-cost flow. We develop a divide-and-conquer approach that solves it in O(m sqrt(n) log(n)) time. The node-weighted problem with arbitrary weights is more difficult. We prove that it is NP-hard for T >= 3 and is solvable in strongly-polynomial time for T = 2.