Search

Your search keyword '"dynamic data structure"' showing total 98 results
Start Over Descriptor "dynamic data structure"
98 results on '"dynamic data structure"'

1. Listing the bonds of a graph in [formula omitted]–delay.

Author

Raffaele, Alice, Rizzi, Romeo, and Uno, Takeaki

Subjects
*LISTING of securities, *GRAPH theory, *GRAPH connectivity, *DATA structures, *SUBGRAPHS
Abstract

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]

Published
2024
Full Text
View/download PDF

2. DETERMINISTIC NEAR-OPTIMAL APPROXIMATION ALGORITHMS FOR DYNAMIC SET COVER.

Author

BHATTACHARYA, SAYAN, HENZINGER, MONIKA, NANONGKAI, DANUPON, and XIAOWEI WU

Subjects
*APPROXIMATION algorithms, *DETERMINISTIC algorithms, *ONLINE algorithms, *DATA structures
Abstract

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]

Published
2023
Full Text
View/download PDF

3. Dynamically Allocated Bloom Filter-Based PIT Architectures

Author

Saeyoung Jang, Hayoung Byun, and Hyesook Lim

Subjects
Bloom filter, dynamic data structure, named data networking, pending Interest table, Electrical engineering. Electronics. Nuclear engineering, TK1-9971
Abstract

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.

Published
2022
Full Text
View/download PDF

4. Dynamic Data Structures for Timed Automata Acceptance.

Author

Grez, Alejandro, Mazowiecki, Filip, Pilipczuk, Michał, Puppis, Gabriele, and Riveros, Cristian

Subjects
*DATA structures, *ROBOTS, *SIGNS & symbols
Abstract

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]

Published
2022
Full Text
View/download PDF

5. Covering Users by a Connected Swarm Efficiently

Author

Danilchenko, Kiril, Segal, Michael, Nutov, Zeev, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Pinotti, Cristina M., editor, Navarra, Alfredo, editor, and Bagchi, Amitabha, editor

Published
2020
Full Text
View/download PDF

6. Dynamically Reconstructing Minimum Spanning Trees After Swapping Pairwise Vertices

Author

Zhang-Hua Fu, Si-Bo Chen, Yi-Fei Ming, Yong-Quan Chen, and Xiang-Jing Lai

Subjects
Dynamic data structure, Steiner/spanning tree problems, swap-vertex move operator, Electrical engineering. Electronics. Nuclear engineering, TK1-9971
Abstract

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.

Published
2019
Full Text
View/download PDF

8. Longest Common Factor After One Edit Operation

Author

Amir, Amihood, Charalampopoulos, Panagiotis, Iliopoulos, Costas S., Pissis, Solon P., Radoszewski, Jakub, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Fici, Gabriele, editor, Sciortino, Marinella, editor, and Venturini, Rossano, editor

Published
2017
Full Text
View/download PDF

9. Counterexample Validation and Interpolation-Based Refinement for Forest Automata

Author

Holík, Lukáš, Hruška, Martin, Lengál, Ondřej, Rogalewicz, Adam, Vojnar, Tomáš, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bouajjani, Ahmed, editor, and Monniaux, David, editor

Published
2017
Full Text
View/download PDF

10. Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing

Author

Takagi, Takuya, Inenaga, Shunsuke, Sadakane, Kunihiko, Arimura, Hiroki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Mäkinen, Veli, editor, Puglisi, Simon J., editor, and Salmela, Leena, editor

Published
2016
Full Text
View/download PDF

14. Engineering Radix Sort for Strings

Author

Kärkkäinen, Juha, Rantala, Tommi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Amir, Amihood, editor, Turpin, Andrew, editor, and Moffat, Alistair, editor

Published
2009
Full Text
View/download PDF

15. DaStGen—A Data Structure Generator for Parallel C++ HPC Software

Author

Bungartz, Hans–Joachim, Eckhardt, Wolfgang, Mehl, Miriam, Weinzierl, Tobias, Hutchison, editor, Kanade, editor, Kittler, editor, Kleinberg, editor, Mattern, editor, Mitchell, editor, Naor, editor, Nierstrasz, editor, Pandu Rangan, editor, Steffen, editor, Sudan, editor, Terzopoulos, editor, Tygar, editor, Vardi, editor, Weikum, editor, Bubak, Marian, editor, van Albada, Geert Dick, editor, Dongarra, Jack, editor, and Sloot, Peter M. A., editor

Published
2008
Full Text
View/download PDF

16. An Improved Succinct Representation for Dynamic k-ary Trees

Author

Arroyuelo, Diego, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ferragina, Paolo, editor, and Landau, Gad M., editor

Published
2008
Full Text
View/download PDF

17. I/O-Efficient Point Location in a Set of Rectangles

Author

Nekrich, Yakov, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Laber, Eduardo Sany, editor, Bornstein, Claudson, editor, Nogueira, Loana Tito, editor, and Faria, Luerbio, editor

Published
2008
Full Text
View/download PDF

18. Computing the Minimum Bottleneck Moving Spanning Tree

Author

Haitao Wang and Yiming Zhao, Wang, Haitao, Zhao, Yiming, Haitao Wang and Yiming Zhao, Wang, Haitao, and Zhao, Yiming

Abstract

Given a set P of n points that are moving in the plane, we consider the problem of computing a spanning tree for these moving points that does not change its combinatorial structure during the point movement. The objective is to minimize the bottleneck weight of the spanning tree (i.e., the largest Euclidean length of all edges) during the whole movement. The problem was solved in O(n²) time previously [Akitaya, Biniaz, Bose, De Carufel, Maheshwari, Silveira, and Smid, WADS 2021]. In this paper, we present a new algorithm of O(n^{4/3} log³ n) time.

Published
2022
Full Text
View/download PDF

19. Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-Shortest Induced Paths

Author

Yung-Chung Chiu and Hsueh-I Lu, Chiu, Yung-Chung, Lu, Hsueh-I, Yung-Chung Chiu and Hsueh-I Lu, Chiu, Yung-Chung, and Lu, Hsueh-I

Abstract

For vertices u and v of an n-vertex graph G, a uv-trail of G is an induced uv-path of G that is not a shortest uv-path of G. Berger, Seymour, and Spirkl [Discrete Mathematics 2021] gave the previously only known polynomial-time algorithm, running in O(n^{18}) time, to either output a uv-trail of G or ensure that G admits no uv-trail. We reduce the complexity to the time required to perform a poly-logarithmic number of multiplications of n²× n² Boolean matrices, leading to a largely improved O(n^{4.75})-time algorithm.

Published
2022
Full Text
View/download PDF

20. Discrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric

Author

Atallah, Mikhail J., Blanton, Marina, Goodrich, Michael T., Polu, Stanislas, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dehne, Frank, editor, Sack, Jörg-Rüdiger, editor, and Zeh, Norbert, editor

Published
2007
Full Text
View/download PDF

21. Orthogonal Range Searching in Linear and Almost-Linear Space

Author

Nekrich, Yakov, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dehne, Frank, editor, Sack, Jörg-Rüdiger, editor, and Zeh, Norbert, editor

Published
2007
Full Text
View/download PDF

22. Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space

Author

Jansson, Jesper, Sadakane, Kunihiko, Sung, Wing-Kin, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Arvind, V., editor, and Prasad, Sanjiva, editor

Published
2007
Full Text
View/download PDF

23. Dynamic Connectivity for Axis-Parallel Rectangles

Author

Afshani, Peyman, Chan, Timothy M., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Azar, Yossi, editor, and Erlebach, Thomas, editor

Published
2006
Full Text
View/download PDF

24. Dynamic Entropy-Compressed Sequences and Full-Text Indexes

Author

Mäkinen, Veli, Navarro, Gonzalo, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Lewenstein, Moshe, editor, and Valiente, Gabriel, editor

Published
2006
Full Text
View/download PDF

25. Oblio: Design and Performance

Author

Dobrian, Florin, Pothen, Alex, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dongarra, Jack, editor, Madsen, Kaj, editor, and Waśniewski, Jerzy, editor

Published
2006
Full Text
View/download PDF

26. Verifying Programs with Dynamic 1-Selector-Linked Structures in Regular Model Checking

Author

Bouajjani, Ahmed, Habermehl, Peter, Moro, Pierre, Vojnar, Tomáš, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Halbwachs, Nicolas, editor, and Zuck, Lenore D., editor

Published
2005
Full Text
View/download PDF

27. Reliable Scheduling of Advanced Transactions

Author

Xin, Tai, Zhu, Yajie, Ray, Indrakshi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Jajodia, Sushil, editor, and Wijesekera, Duminda, editor

Published
2005
Full Text
View/download PDF

28. Data Structure Optimization of AS_PATH in BGP

Author

Jiang, Weirong, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Lu, Xicheng, editor, and Zhao, Wei, editor

Published
2005
Full Text
View/download PDF

29. On Dynamic Bit-Probe Complexity

Author

Pǎtraşcu, Corina E., Pǎtraşcu, Mihai, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Caires, Luís, editor, Italiano, Giuseppe F., editor, Monteiro, Luís, editor, Palamidessi, Catuscia, editor, and Yung, Moti, editor

Published
2005
Full Text
View/download PDF

30. Predator: A Tool for Verification of Low-Level List Manipulation : (Competition Contribution)

Author

Dudka, Kamil, Müller, Petr, Peringer, Petr, Vojnar, Tomáš, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Piterman, Nir, editor, and Smolka, Scott A., editor

Published
2013
Full Text
View/download PDF

31. Rapid Prototyping for Web Applications

Author

Lim, Chee Chern, Yu, Man Hing, Jin, Jesse J., Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Li, Qing, editor, Wang, Guoren, editor, and Feng, Ling, editor

Published
2004
Full Text
View/download PDF

34. Efficiently computing the smallest axis-parallel squares spanning all colors.

Author

Khanteimouri, P., Mohades, A., Abam, M. A., Kazemi, M. R., and Sedighin, S.

Subjects
SPANNING trees, DATA structures, PROBLEM solving, ALGORITHMS, ELECTRONIC data processing
Abstract

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]

Published
2017
Full Text
View/download PDF

39. Computing the Minimum Bottleneck Moving Spanning Tree

Author

Wang, Haitao and Zhao, Yiming

Subjects
Computational Geometry (cs.CG), FOS: Computer and information sciences, moving points, Theory of computation → Design and analysis of algorithms, Computer Science - Data Structures and Algorithms, dynamic data structure, Theory of computation → Computational geometry, Computer Science - Computational Geometry, Data Structures and Algorithms (cs.DS), unit-disk range emptiness query, minimum spanning tree
Abstract

Given a set $P$ of $n$ points that are moving in the plane, we consider the problem of computing a spanning tree for these moving points that does not change its combinatorial structure during the point movement. The objective is to minimize the bottleneck weight of the spanning tree (i.e., the largest Euclidean length of all edges) during the whole movement. The problem was solved in $O(n^2)$ time previously [Akitaya, Biniaz, Bose, De Carufel, Maheshwari, Silveira, and Smid, WADS 2021]. In this paper, we present a new algorithm of $O(n^{4/3} \log^3 n)$ time., Comment: A preliminary version to appear in MFCS 2022

Published
2022
Full Text
View/download PDF

40. Dynamic Data Structures for Timed Automata Acceptance

Author

Grez, A., Mazowiecki, F., Pilipczuk, M., Puppis, G., and Riveros, C.

Subjects
Theory of computation ��� Models of computation, General Computer Science, Applied Mathematics, Data stream, Dynamic data structure, Timed automata, Computer Science::Formal Languages and Automata Theory, Computer Science Applications
Abstract

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 ���� with amortized update time 2^{����(|����|)} per input symbol., LIPIcs, Vol. 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), pages 20:1-20:18

Published
2022

42. HARMONIC LOAD FLOW FOR RADIAL DISTRIBUTION SYSTEMS

Author

A. ARUNAGIRI and B. VENKATESH

Subjects
Radial distribution systems, Magnetic saturation, Harmonics, Dynamic data structure, Engineering (General). Civil engineering (General), TA1-2040, Technology (General), T1-995
Abstract

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.

Published
2011

47. Dynamic algorithms for the Dyck languages

Author

Frandsen, Gudmund Skovbjerg, Husfeldt, Thore, Miltersen, Peter Bro, Rauhe, Theis, Skyum, Søren, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Akl, Selim G., editor, Dehne, Frank, editor, Sack, Jörg-Rüdiger, editor, and Santoro, Nicola, editor

Published
1995
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results