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]

In the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal min\{ O(log n), f\} approximation factor. (Throughout, n, m, f, and C are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when f = \Omega (log n), this was achieved by a deterministic O(log n)-approximation algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537--550]. In this paper we consider the low-frequency range, when f =O(log n), and obtain deterministic algorithms with a (1 + \epsilon)f-approximation ratio and the following guarantees on the update time. (1) O((f/\epsilon) \cdot log(Cn)) amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was O(f2) of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206--218]. In contrast, the only result with O(f)-approximation was that of Abboud et al. [Dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114--125], who designed a randomized (1+\epsilon)f-approximation algorithm with O((f2/\epsilon) \cdot log n) amortized update time. (2) O \bigl(f2/\epsilon 3 + (f/\epsilon 2) \cdot logC \bigr) amortized update time: This result improves the above update time bound for most values of f in the low-frequency range, i.e., f =o(log n). It is also the first result that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically maintaining a (2 + \epsilon)-approximate minimum vertex cover in O(1/\epsilon 2) amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872--1885] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). (3) O((f/\epsilon 3) \cdot log2(Cn)) worst-case update time: No nontrivial worst-case update time was previously known for the dynamic set cover problem. Our bound subsumes and improves by a logarithmic factor the O(log3 n/\sansp \sanso \sansl \sansy (\epsilon)) worst-case update time for the unweighted dynamic vertex cover problem (i.e., when f = 2 and C = 1) of Bhattacharya, Henzinger, and Nanongkai [Fully dynamic approximate maximum matching and minimum vertex cover in O(log3)n worst case update time, in Proceedings SODA 2017, SIAM, pp. 470--489]. We achieve our results via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual approach uses a local update scheme that maintains relaxed complementary slackness conditions for every set. For our first result we use instead a global update scheme that does not always maintain complementary slackness conditions. For our second result we combine the global and the local update schema. To achieve our third result we use a hierarchy of background schedulers. It is an interesting open question whether this background scheduler technique can also be used to transform algorithms with amortized running time bounds into algorithms with worst-case running time bounds. [ABSTRACT FROM AUTHOR]

As a key component in implementing Named Data Networking (NDN), Pending Interest Table (PIT) requires an efficient exact-matching algorithm for a scalable and fast PIT lookup. A Bloom filter (BF) is a memory-efficient data structure for performing exact matching operations. In this paper, three different BF-based PIT architectures are proposed: PIT using functional Bloom filters (FBF-PIT), PIT using counting Bloom filters with return values (rCBF-PIT), and a refined rCBF-PIT with signatures (R-rCBF-PIT). The proposed BF-based PITs incrementally allocate a new BF for storing multiple incoming faces of Interest packets with the same content name. For a Data packet lookup, the proposed PIT architectures simultaneously access every BF structure to find matching faces and delete the faces (i.e., matching Interest packet information). The functional Bloom filter (FBF) used in an FBF-PIT is a key-value data structure that stores values only without keys. However, because the number of non-reusable conflict cells in the FBF increases as the number of stored packets increases in the FBF-PIT, the indeterminable rate increases. To decrease the indeterminable rate, we propose the rCBF-PIT, which uses counting Bloom filters with return values (rCBFs), allowing reusable conflict cells. False positives for Interest packets lead to incorrect deletions that can cause false negatives for incoming Data packets. Because most of the false positives occur in the first BF structure, we finally propose the R-rCBF-PIT, in which the first rCBF is replaced with an rCBF with a signature field. The proposed PITs also provide an aging mechanism using a valid bit and a hit bit for entry expiration. Simulation results show that rCBF-PIT and R-rCBF-PIT both reduce the indeterminable rate by more than 81% compared with FBF-PIT. The results also show that R-rCBF-PIT resolves false negatives caused by incorrect deletions by including the signature fields in the first rCBF.

We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so through the lenses of parameterized dynamic data structures: we assume that the automaton is fixed and its size is the parameter, while the input word is revealed as in a stream, one symbol at a time following the natural order on positions. The goal is to design a dynamic data structure that can be efficiently updated upon revealing the next symbol, while maintaining the answer to the query on whether the word consisting of symbols revealed so far is accepted by the automaton. We provide complexity bounds for this dynamic acceptance problem for timed automata that process symbols interleaved with time spans. The main contribution is a dynamic data structure that maintains acceptance of a fixed one-clock timed automaton A with amortized update time 2 O (| A |) per input symbol. [ABSTRACT FROM AUTHOR]

The minimum spanning tree (MST) problem is a fundamental problem in computer science and operations research, which has many real-life network design applications. Given a graph G with n vertices and m edges, starting from an MST (denoted by T) covering a subgraph of G, it is usually needed to reconstruct a new MST after swapping two vertices v ∈ T and v' ∉ T. For this purpose, the most popular choice is to reconstruct an MST from scratch, for which the current fastest algorithm (Kruskal's algorithm based on Fibonacci heap) requires a time complexity of O(m + n · log n), implying that a high time complexity of O(n2) · O(m + n · log n) is needed to evaluate all the O(n2) possible swapping-based moves. In order to evaluate these moves more efficiently, we integrate a series of dynamic techniques to develop a fast dynamic swap-vertex move operator, which significantly reduces the overall time complexity from O(n2) · O(m + n · log n) to O(n) · O(m · log n). We also strictly prove the correctness of the introduced method. Finally, we choose three well-studied Steiner/spanning tree problems as our test bed and carry out extensive experiments on 140 representative instances to show the effectiveness and efficiency of the proposed method. More importantly, as a general-purpose method, the dynamic swap-vertex move operator could be easily adapted to many other tree-related problems.

For a set of colored points, a region is called color-spanning if it contains at least one point of each color. In this paper, we first consider the problem of maintaining the smallest color-spanning interval for a set of n points with k colors on the real line, such that the insertion and deletion of an arbitrary point takes O (log² n) the worst-case time. Then, we exploit the data structure to show that there is O(n log² n) time algorithm to compute the smallest color-spanning square for a set of n points with k colors in the plane. This is a new way to improve O (nk log n) time algorithm presented by Abellanas et al. [1] when k = w(logn). We also consider the problem of computing the smallest color-spanning square in a special case in which we have, at most, two points from each color. We present O(nlogn) time algorithm to solve the problem which improves the result presented by Arkin et al. [2] by a factor of log n. [ABSTRACT FROM AUTHOR]

Radial distribution systems (RDS) require special load flow methods to solve power flow equations owing to their high R/X ratio. Increasing use of power electronic devices and effect of magnetic saturation cause harmonics in RDS. This paper proposes a novel algorithm to compute the power flow solution of a RDS accounting for all the harmonic components. It uses a recursive solution technique. The proposed method uses a novel dynamic data structure reported in the paper. The proposed method is tested upon a 33-bus RDS and the results are reported.

Test data generation is a process of creating program inputs that satisfy specific testing criteria. Many works have been focused on test generation with respect to numeric and string data. Dynamic data structures, such as trees and linked lists, have been widely used in modern programming, but on which there are few studies presented. In general, generating a dynamic data structure is associated with a proper shape and valid values generation. It would be difficult to generate such dynamic data structures, as both shapes and values are necessary to be valid simultaneously. This paper focuses on binary tree structures and proposes a novel test generation approach that combines search based testing with constraint solving techniques. The approach creates the shapes of binary tree structures by using GA, and generates the values in their data fields by using constraint solving techniques. The experimental results show that the presented approach is promising and effective. Moreover, the studies investigate factors affecting the performance of the approach, and arrive at a conclusion that the test generation cost is cubic growing as the number of pointer constraints increases. [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]

Point location is an extremely well-studied problem both in internal memory models and recently also in the external memory model. In this paper, we present an I/O-efficient dynamic data structure for point location in general planar subdivisions. Our structure uses linear space to store a subdivision with N segments. Insertions and deletions of segments can be performed in amortized O(log N) I/Os and queries can be answered in $O(\log_{B}^{2} N)$ I/Os in the worst-case. The previous best known linear space dynamic structure also answers queries in $O(\log_{B}^{2} N)$ I/Os, but only supports insertions in amortized $O(\log_{B}^{2} N)$ I/Os. Our structure is also considerably simpler than previous structures. [ABSTRACT FROM AUTHOR]

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 present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R2) or the skip octree (for point data in Rd, with constant d > 2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined “box”-shaped regions of region quadtrees and the logarithmic-height search and update hierarchical structure of skip lists. Indeed, the bottom level of our structure is exactly a region quadtree (or octree for higher dimensional data). We describe efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location, approximate range, and approximate nearest neighbor queries. [ABSTRACT FROM AUTHOR]

The traditional approach to relational database design is based on the logical organization of data into a number of related normalized tables. One assumption is that the nature and structure of the data is known at the design stage. In the case of designing a relational database to store historical dental epidemiological data from individual clinical surveys, the structure of the data is not known until the data is presented for inclusion into the database. This paper addresses the issues concerned with the theoretical design of a clinical dynamic database capable of adapting the internal table structure to accommodate clinical survey data, and presents a prototype database application capable of processing, displaying, and querying the dental data. [ABSTRACT FROM AUTHOR]

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:

Two vertices of an undirected graph are called k -edge-connected if there exist k edge-disjoint paths between them (equivalently, they cannot be disconnected by the removal of less than k edges from the graph). Equivalence classes of this relation are called classes of k -edge-connectivity or k -edge-connected components. This paper describes graph structures relevant to classes of 4 -edge-connectivity and traces their transformations as new edges are inserted into the graph. Data structures and an algorithm to maintain these classes incrementally are given. Starting with the empty graph, any sequence of q Same-4-Class? queries and n Insert-Vertex and m Insert-Edge updates can be performed in O(q + m + n log n) total time. Each individual query requires O(1) time in the worst-case. In addition, an algorithm for maintaining the classes of k -edge-connectivity ( k arbitrary) in a (k-1) -edge-connected graph is presented. Its complexity is O(q + m + n) , with O(M +k 2 n log (n/k)) preprocessing, where M is the number of edges initially in the graph and n is the number of its vertices. [ABSTRACT FROM AUTHOR]

We consider the problem of maintaining on-line the triconnected components of a graph G. Let n be the current number of vertices of G. We present an O(n)-space data structure that supports insertions of vertices and edges, and queries of the type 'Are there three vertex-disjoint paths between vertices v and v?' A sequence of k operations takes time O(k·α(k, n)) if G is biconnected (α(k, n) denotes the well-known Ackermann's function inverse), and time O( n log n+ k) if G is not biconnected. Note that the bounds do not depend on the number of edges of G. We use the SPQR-tree, a versatile data structure that represents the decomposition of a biconnected graph with respect to its triconnected components, and the BC-tree, which represents the decomposition of a connected graph with respect to its biconnected components. [ABSTRACT FROM AUTHOR]

We show that a planar st-graph G admits two total orders on the set V∪ E ∪ F, where V, E, and F are respectively the set of vertices, edges, and faces of G, with ¦ V¦ = n. Assuming that G is to be dynamically modified by means of insertions of edges and expansions of vertices (and their inverses), we exhibit an O( n)-space dynamic data structure for the maintenance of these orders such that an update can be performed in time O(log n). The discovered structural properties of planar st-graphs provide a unifying theoretical underpinning for several applications, such as dynamic point location in planar monotone subdivisions, dynamic transitive-closure query in planar st-graphs, and dynamic contact-chain query in convex subdivisions. The presented techniques significantly outperform previously known solutions of the same problems. [ABSTRACT FROM AUTHOR]

Given a point set in the plane and a fixed planar region (window) a window query consists of enumerating the points in a translate of the region. A recently presented result demonstrates that there is a static data structure, of optimal size, that solves window queries for convex regions in optimal time. We give a data structure, of optimal size, that not only supports window queries in optimal time for, possibly nonconvex, polygonal windows, but also allows updating of the point set in optimal time. [ABSTRACT FROM AUTHOR]