Search

Given a connected graph G = (V , E) , with n ≔ | V | vertices and m ≔ | E | edges, a cut can be represented as a bipartition { S , S ¯ } of the vertices or as the set of those edges in E having one endpoint in S and the other in S ¯ , denoted by δ G (S , S ¯). A cut is minimal, or also called bond , if and only if the two induced subgraphs obtained by removing the edges in the cut are both connected. When the bond separates two given vertices s and t , we talk about s , t - bond. In this work, we consider the problems of listing all the bonds and listing all the s , t -bonds in a graph. These fundamental problems find application in many research areas, such as, beyond graph theory, network reliability, bioinformatics, and chemistry. The state-of-the-art algorithm exploits binary partition to output each s , t -bond in O (m) per bond, being thus classified as an O (m) -delay algorithm. Here we present two new algorithms to address these problems. The first one implements a slightly different branching strategy than the state of the art, though achieving the same complexity. Anyway, we can improve it by relying on dynamic data structures and amortized analysis, obtaining an algorithm that outputs a new bond in O ˜ (n). By assuming only the two bond-shores are output for every bond, this is the first output-linear algorithm listing bonds. In case we commit to explicitly providing the entire edge-set of every bond, the delay becomes O ˜ (n) + | δ G (S , S ¯) |. • We study the problem of listing all minimal cuts (or bonds) in a graph. • We exploit a different branching strategy than Tsukiyama et al. (1980). • We provide a first algorithm having the same complexity as Tsukiyama et al. (1980). • We rely on dynamic data structures and amortized analysis to improve our approach. • We propose the first O ˜ (n) -delay algorithm to list all bonds in a graph. [ABSTRACT FROM AUTHOR]

Abstract: We present a linear-space data structure that maintains a dynamic set of n points with coordinates of real numbers in the plane to support orthogonal range counting in worst-case time, and insertions and deletions in amortized time. This provides faster support for updates than previous results with the same bounds on space cost and query time. We also consider the same problem for points on a grid, and design the first succinct data structure for a dynamic integer sequence, S, to support range counting queries defined as follows: Given a range, , of indices and a range, , of values, count the number of entries of that store integers from . [Copyright &y& Elsevier]

Abstract: Recently new algorithms appeared for updating the Burrows–Wheeler Transform or the suffix array, when the text they index is modified. These algorithms proceed by reordering entries and the number of such reordered entries may be as high as the length of the text. However, in practice, these algorithms are faster for updating the Burrows–Wheeler Transform or the suffix array than the fastest reconstruction algorithms. In this article we focus on the number of elements to be reordered for real-life texts. We show that this number is related to LCP values and that, on average, entries are reordered, where denotes the average LCP value, defined as the average length of the longest common prefix between two consecutive sorted suffixes. Since we know little about the LCP distribution for real-life texts, we conduct experiments on a corpus that consists of DNA sequences and natural language texts. The results show that apart from texts containing large repetitions, the average LCP value is close to the one expected on a random text. [Copyright &y& Elsevier]

We consider the problem of translating a (finite or infinite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied if it contains k or more points of S. The main set of problems we study have to do with translating an infinite grid so that the number of k-occupied cells is maximized or minimized. For these problems we obtain running times of the form O(kn polylog (n)). We also consider the problem of translating a finite size grid, with m cells, in order to maximize the number of k-occupied cells. Here we obtain a running time of the form O(knm polylog (nm)). In solving these problems, we design a data structure T that maintains in O(logn) time per operation, a function f :R→R under the following query and update operations where [a,b) is a continuous interval in R: