Bibliography¶
The entries are all the works that the library cites, i.e., those of the
\see lines of its headers and theory pages, those that the README names
and those cited by the chapters of this manual, together with the
textbooks and the libraries with which it is compared; each one carries
its DOI when it has one.
-
M. I. Abouelhoda, S. Kurtz, E. Ohlebusch. Replacing suffix trees with enhanced suffix arrays. Journal of Discrete Algorithms 2(1) (2004), 53–86, https://doi.org/10.1016/S1570-8667(03)00065-0.
-
D. Abrahams. Exception-safety in generic components. Generic Programming, LNCS 1766, Springer, 2000, 69–79, https://doi.org/10.1007/3-540-39953-4_6.
-
D. Abrahams, J. Siek, T. Witt. New iterator concepts. ISO/IEC JTC1 SC22 WG21 N1640, 2004, https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1640.html.
-
U. A. Acar, G. E. Blelloch, R. Harper. Adaptive functional programming. Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2002), 247–259, 2002, https://doi.org/10.1145/503272.503296.
-
U. A. Acar, A. Charguéraud, M. Rainey. Scheduling parallel programs by work stealing with private deques. Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2013, 219–228, https://doi.org/10.1145/2442516.2442538.
-
U. A. Acar, D. Anderson, G. E. Blelloch, L. Dhulipala. Parallel batch-dynamic graph connectivity. Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019), 2019, 381–392, https://doi.org/10.1145/3323165.3323196.
-
S. Adams. Efficient sets: a balancing act. Journal of Functional Programming 3(4) (1993), 553–561, https://doi.org/10.1017/S0956796800000885.
-
G. M. Adelson-Velsky, E. M. Landis. An algorithm for the organization of information. Soviet Mathematics Doklady 3 (1962), 1259–1263.
-
A. Aggarwal, J. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM 31(9) (1988), 1116–1127, https://doi.org/10.1145/48529.48535.
-
A. V. Aho, M. J. Corasick. Efficient string matching: an aid to bibliographic search. Communications of the ACM 18(6) (1975), 333–340, https://doi.org/10.1145/360825.360855.
-
A. V. Aho, J. E. Hopcroft, J. D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983.
-
R. K. Ahuja, K. Mehlhorn, J. Orlin, R. E. Tarjan. Faster algorithms for the shortest path problem. Journal of the ACM 37(2) (1990), 213–223, https://doi.org/10.1145/77600.77615.
-
S. G. Akl, G. T. Toussaint. A fast convex hull algorithm. Information Processing Letters 7(5) (1978), 219–222, https://doi.org/10.1016/0020-0190(78)90003-0.
-
M. Akra, L. Bazzi. On the solution of linear recurrence equations. Computational Optimization and Applications 10(2) (1998), 195–210, https://doi.org/10.1023/A:1018373005182.
-
M. Aldinucci, M. Danelutto, P. Kilpatrick, M. Meneghin, M. Torquati. An efficient unbounded lock-free queue for multi-core systems. Euro-Par 2012, LNCS 7484 (2012), 662–673, https://doi.org/10.1007/978-3-642-32820-6_65.
-
M. Aldinucci, M. Danelutto, P. Kilpatrick, M. Torquati. FastFlow: high-level and efficient streaming on multicore. In S. Pllana, F. Xhafa (eds.), Programming Multi-core and Many-core Computing Systems, Wiley, 2017, 261–280, https://doi.org/10.1002/9781119332015.ch13.
-
D. Aldous. Minimization algorithms and random walk on the d-cube. The Annals of Probability 11(2) (1983), 403–413, https://doi.org/10.1214/aop/1176993605.
-
A. Alexandrescu. Modern C++ Design: Generic Programming and Design Patterns Applied. Addison-Wesley, 2001.
-
D. Alistarh, J. Kopinsky, J. Li, G. Nadiradze. The power of choice in priority scheduling. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2017, 283–292, https://doi.org/10.1145/3087801.3087810.
-
L. Allison, T. I. Dix. A bit-string longest-common-subsequence algorithm. Information Processing Letters 23(5) (1986), 305–310, https://doi.org/10.1016/0020-0190(86)90091-8.
-
S. Alstrup, C. Gavoille, H. Kaplan, T. Rauhe. Nearest common ancestors: a survey and a new distributed algorithm. Proceedings of the 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2002, 258–264, https://doi.org/10.1145/564870.564914.
-
S. Alstrup, J. Holm, K. de Lichtenberg, M. Thorup. Maintaining information in fully dynamic trees with top trees. ACM Transactions on Algorithms 1(2) (2005), 243–264, https://doi.org/10.1145/1103963.1103966.
-
T. E. Anderson. The performance of spin lock alternatives for shared-memory multiprocessors. IEEE Transactions on Parallel and Distributed Systems 1(1) (1990), 6–16, https://doi.org/10.1109/71.80120.
-
R. J. Anderson, G. L. Miller. Deterministic parallel list ranking. Algorithmica 6(1-6) (1991), 859–868, https://doi.org/10.1007/BF01759076.
-
D. Anderson, G. E. Blelloch, L. Dhulipala, M. Dobson, Y. Sun. The problem-based benchmark suite (PBBS), V2. ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) (2022), 445–447, https://doi.org/10.1145/3503221.3508422.
-
A. Andersson. Improving partial rebuilding by using simple balance criteria. Algorithms and Data Structures (WADS 1989), LNCS 382 (1989), 393–402, https://doi.org/10.1007/3-540-51542-9_33.
-
A. Andersson. Balanced search trees made simple. Algorithms and Data Structures (WADS 1993), LNCS 709 (1993), 60–71, https://doi.org/10.1007/3-540-57155-8_236.
-
A. Andersson. General balanced trees. Journal of Algorithms 30(1) (1999), 1–18, https://doi.org/10.1006/jagm.1998.0967.
-
A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters 9(5) (1979), 216–219, https://doi.org/10.1016/0020-0190(79)90072-3.
-
E. Angriman, A. van der Grinten, M. Hamann, H. Meyerhenke, M. Penschuck. Algorithms for large-scale network analysis and the NetworKit toolkit. Algorithms for Big Data, LNCS 13201 (2022), 3–20, https://doi.org/10.1007/978-3-031-21534-6_1.
-
A. Apostolico, G. F. Italiano, G. Gambosi, M. Talamo. The set union problem with unlimited backtracking. SIAM Journal on Computing 23(1) (1994), 50–70, https://doi.org/10.1137/S0097539789173597.
-
V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, I. A. Faradzev. On economical construction of the transitive closure of an oriented graph. Soviet Mathematics Doklady 11 (1970), 1209–1210.
-
J. Arndt. Matters Computational: Ideas, Algorithms, Source Code. Springer, 2011, https://doi.org/10.1007/978-3-642-14764-7.
-
N. S. Arora, R. D. Blumofe, C. G. Plaxton. Thread scheduling for multiprogrammed multiprocessors. Theory of Computing Systems 34(2) (2001), 115–144, https://doi.org/10.1007/s00224-001-0004-z.
-
D. Arroyuelo, R. Cánovas, G. Navarro, K. Sadakane. Succinct trees in practice. Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX 2010), 84–97, 2010, https://doi.org/10.1137/1.9781611972900.9.
-
B. Aspvall, M. F. Plass, R. E. Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters 8(3) (1979), 121–123, https://doi.org/10.1016/0020-0190(79)90002-4.
-
AtCoder. AtCoder Library. Software, 2020, https://github.com/atcoder/ac-library.
-
M. D. Atkinson, J. R. Sack, N. Santoro, T. Strothotte. Min-max heaps and generalized priority queues. Communications of the ACM 29(10) (1986), 996–1000, https://doi.org/10.1145/6617.6621.
-
H. Attiya, R. Guerraoui, D. Hendler, P. Kuznetsov, M. M. Michael, M. Vechev. Laws of order: expensive synchronization in concurrent algorithms cannot be eliminated. Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), 2011, 487–498, https://doi.org/10.1145/1926385.1926442.
-
N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. On the worst-case complexity of TimSort. 26th Annual European Symposium on Algorithms (ESA 2018), LIPIcs 112 (2018), 4:1–4:13, https://doi.org/10.4230/LIPIcs.ESA.2018.4.
-
M. Aumüller, M. Dietzfelbinger, P. Woelfel. Explicit and efficient hash families suffice for cuckoo hashing with a stash. Algorithmica 70(3) (2014), 428–456, https://doi.org/10.1007/s00453-013-9840-x.
-
M. Axtmann, T. Bingmann, P. Sanders, C. Schulz. Practical massively parallel sorting. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015, 13–23, https://doi.org/10.1145/2755573.2755595.
-
M. Axtmann, S. Witt, D. Ferizovic, P. Sanders. In-place parallel super scalar samplesort (IPSSSSo). 25th Annual European Symposium on Algorithms (ESA 2017), LIPIcs 87 (2017), 9:1–9:14, https://doi.org/10.4230/LIPIcs.ESA.2017.9.
-
M. Axtmann, S. Witt, D. Ferizovic, P. Sanders. Engineering in-place (shared-memory) sorting algorithms. ACM Transactions on Parallel Computing 9(1) (2022), 1–62, https://doi.org/10.1145/3505286.
-
Y. Azar, A. Z. Broder, A. R. Karlin, E. Upfal. Balanced allocations. SIAM Journal on Computing 29(1) (1999), 180–200, https://doi.org/10.1137/S0097539795288490.
-
R. A. Baeza-Yates, G. H. Gonnet. A new approach to text searching. Communications of the ACM 35(10) (1992), 74–82, https://doi.org/10.1145/135239.135243.
-
R. Baeza-Yates. A fast set intersection algorithm for sorted sequences. In: Combinatorial Pattern Matching (CPM 2004), Lecture Notes in Computer Science 3109, Springer, 2004, 400–408, https://doi.org/10.1007/978-3-540-27801-6_30.
-
A. Bagchi, A. L. Buchsbaum, M. T. Goodrich. Biased skip lists. In: Algorithms and Computation (ISAAC 2002), Lecture Notes in Computer Science 2518, 2002, 1–13, https://doi.org/10.1007/3-540-36136-7_1.
-
P. Bagwell. Ideal hash trees. Technical report, EPFL, Lausanne, 2001.
-
J. Barbay, A. López-Ortiz, T. Lu, A. Salinger. An experimental investigation of set intersection algorithms for text searching. ACM Journal of Experimental Algorithmics 14 (2009), 3.7, https://doi.org/10.1145/1498698.1564507.
-
J. Basch, L. J. Guibas, J. Hershberger. Data structures for mobile data. Journal of Algorithms 31(1) (1999), 1–28, https://doi.org/10.1006/jagm.1998.0988.
-
K. E. Batcher. Sorting networks and their applications. Proceedings of the AFIPS Spring Joint Computer Conference 32, 1968, 307–314, https://doi.org/10.1145/1468075.1468121.
-
R. Bauer, D. Wagner. Batch dynamic single-source shortest-path algorithms: an experimental study. Proceedings of the 8th International Symposium on Experimental Algorithms (SEA 2009), LNCS 5526 (2009), 51–62, https://doi.org/10.1007/978-3-642-02011-7_7.
-
N. Baumstark, S. Gog, T. Heuer, J. Labeit. Practical range minimum queries revisited. 16th International Symposium on Experimental Algorithms (SEA 2017), LIPIcs 75, 2017, 12:1–12:16, https://doi.org/10.4230/LIPIcs.SEA.2017.12.
-
R. Bayer, E. M. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica 1(3) (1972), 173–189, https://doi.org/10.1007/BF00288683.
-
R. Bayer. Symmetric binary B-trees: data structure and maintenance algorithms. Acta Informatica 1(4) (1972), 290–306, https://doi.org/10.1007/BF00289509.
-
S. Beamer, K. Asanović, D. Patterson. Direction-optimizing breadth-first search. International Conference for High Performance Computing, Networking, Storage and Analysis (SC) (2012), 1–10, https://doi.org/10.1109/SC.2012.50.
-
S. Beamer, K. Asanović, D. Patterson. The GAP benchmark suite. arXiv:1508.03619, 2015, https://doi.org/10.48550/arXiv.1508.03619.
-
M. Beeler, R. W. Gosper, R. Schroeppel. HAKMEM. Memo 239, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, 1972.
-
D. Belazzougui, F. C. Botelho, M. Dietzfelbinger. Hash, displace, and compress. Proceedings of the 17th European Symposium on Algorithms (ESA 2009), LNCS 5757 (2009), 682–693, https://doi.org/10.1007/978-3-642-04128-0_61.
-
P. Beling. Fingerprinting-based minimal perfect hashing revisited. ACM Journal of Experimental Algorithmics 28 (2023), 1–16, https://doi.org/10.1145/3596453.
-
J. Bell, B. Stevens. A survey of known results and research areas for n-queens. Discrete Mathematics 309(1) (2009), 1–31, https://doi.org/10.1016/j.disc.2007.12.043.
-
R. Bellman. On a routing problem. Quarterly of Applied Mathematics 16(1) (1958), 87–90, https://doi.org/10.1090/qam/102435.
-
L. Bellomo, G. Cianci, L. de Rosa, P. Ferragina, M. Odorisio. A comparative study of compressed, learned, and traditional indexing methods for integer data. 23rd International Symposium on Experimental Algorithms (SEA 2025), LIPIcs 338, 2025, 5:1–5:23, https://doi.org/10.4230/LIPIcs.SEA.2025.5.
-
M. A. Bender, M. Farach-Colton. The LCA problem revisited. LATIN 2000: Theoretical Informatics, Lecture Notes in Computer Science 1776, Springer, 2000, 88–94, https://doi.org/10.1007/10719839_9.
-
M. A. Bender, R. Cole, E. D. Demaine, M. Farach-Colton, J. Zito. Two simplified algorithms for maintaining order in a list. Algorithms - ESA 2002, LNCS 2461 (2002), 152–164, https://doi.org/10.1007/3-540-45749-6_17.
-
M. A. Bender, M. Farach-Colton, B. C. Kuszmaul. Cache-oblivious string B-trees. Proceedings of the 25th ACM Symposium on Principles of Database Systems (PODS), 2006, 233–242, https://doi.org/10.1145/1142351.1142385.
-
D. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman, S. S. Rao. Representing trees of higher degree. Algorithmica 43(4) (2005), 275–292, https://doi.org/10.1007/s00453-004-1146-6.
-
M. Ben-Or. Lower bounds for algebraic computation trees. Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC), 1983, 80–86, https://doi.org/10.1145/800061.808735.
-
J. L. Bentley, A. C.-C. Yao. An almost optimal algorithm for unbounded searching. Information Processing Letters 5(3) (1976), 82–87, https://doi.org/10.1016/0020-0190(76)90071-5.
-
J. L. Bentley. Decomposable searching problems. Information Processing Letters 8(5) (1979), 244–251, https://doi.org/10.1016/0020-0190(79)90117-0.
-
J. L. Bentley, J. B. Saxe. Decomposable searching problems I: static-to-dynamic transformation. Journal of Algorithms 1(4) (1980), 301–358, https://doi.org/10.1016/0196-6774(80)90015-2.
-
J. L. Bentley. Multidimensional divide-and-conquer. Communications of the ACM 23(4) (1980), 214–229, https://doi.org/10.1145/358841.358850.
-
J. Bentley. Programming pearls: algorithm design techniques. Communications of the ACM 27(9) (1984), 865–873, https://doi.org/10.1145/358234.381162.
-
J. L. Bentley, D. D. Sleator, R. E. Tarjan, V. K. Wei. A locally adaptive data compression scheme. Communications of the ACM 29(4) (1986), 320–330, https://doi.org/10.1145/5684.5688.
-
J. L. Bentley, M. D. McIlroy. Engineering a sort function. Software: Practice and Experience 23(11) (1993), 1249–1265, https://doi.org/10.1002/spe.4380231105.
-
J. L. Bentley, R. Sedgewick. Fast algorithms for sorting and searching strings. Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1997, 360–369.
-
J. Bentley. Programming Pearls. 2nd edition, Addison-Wesley, 2000.
-
I. O. Bercea, G. Even. A dynamic space-efficient filter with constant time operations. In: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), LIPIcs 162, 2020, 11:1–11:17, https://doi.org/10.4230/LIPIcs.SWAT.2020.11.
-
C. Berge. Two theorems in graph theory. Proceedings of the National Academy of Sciences 43(9) (1957), 842–844, https://doi.org/10.1073/pnas.43.9.842.
-
E. D. Berger, K. S. McKinley, R. D. Blumofe, P. R. Wilson. Hoard: a scalable memory allocator for multithreaded applications. Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS IX), 2000, 117–128, https://doi.org/10.1145/378993.379232.
-
E. D. Berger, B. G. Zorn, K. S. McKinley. Reconsidering custom memory allocation. Proceedings of the 17th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2002, 1–12, https://doi.org/10.1145/582419.582421.
-
J. Berne, T. Doumler, A. Krzemieński, et al. Contracts for C++. P2900R14, ISO/IEC JTC1/SC22/WG21, 2025.
-
A. A. Bertossi, A. Montresor. Algoritmi e Strutture di Dati. 3rd edition, Città Studi, 2014.
-
N. Bertram, J. Fischer, L. Nalbach. Move-r: optimizing the r-index. Proceedings of the 22nd International Symposium on Experimental Algorithms (SEA 2024), LIPIcs 301, article 1, 2024, https://doi.org/10.4230/LIPIcs.SEA.2024.1.
-
D. Bez, F. Kurpicz, H.-P. Lehmann, P. Sanders. High performance construction of RecSplit based minimal perfect hash functions. 31st Annual European Symposium on Algorithms (ESA 2023), LIPIcs 274 (2023), 19:1–19:16, https://doi.org/10.4230/LIPIcs.ESA.2023.19.
-
P. Bille, A. R. Christiansen, M. B. Ettienne, I. L. Gørtz. Fast dynamic arrays. 25th Annual European Symposium on Algorithms (ESA 2017), LIPIcs 87 (2017), 16:1–16:13, https://doi.org/10.4230/LIPIcs.ESA.2017.16.
-
T. Bingmann, P. Sanders. Parallel string sample sort. Proceedings of the 21st European Symposium on Algorithms (ESA), LNCS 8125 (2013), 169–180, https://doi.org/10.1007/978-3-642-40450-4_15.
-
J. Black, S. Halevi, H. Krawczyk, T. Krovetz, P. Rogaway. UMAC: fast and secure message authentication. In: Advances in Cryptology (CRYPTO 1999), Lecture Notes in Computer Science 1666, 1999, 216–233, https://doi.org/10.1007/3-540-48405-1_14.
-
L. S. Blackford, J. Demmel, J. Dongarra, I. Duff, S. Hammarling, G. Henry, M. Heroux, L. Kaufman, A. Lumsdaine, A. Petitet, R. Pozo, K. Remington, R. C. Whaley. An updated set of basic linear algebra subprograms (BLAS). ACM Transactions on Mathematical Software 28(2) (2002), 135–151, https://doi.org/10.1145/567806.567807.
-
D. Blackman, S. Vigna. Scrambled linear pseudorandom number generators. ACM Transactions on Mathematical Software 47(4) (2021), 36:1–36:32, https://doi.org/10.1145/3460772.
-
G. E. Blelloch. Prefix sums and their applications. Technical Report CMU-CS-90-190, Carnegie Mellon University, 1990.
-
G. E. Blelloch, M. Reid-Miller. Fast set operations using treaps. Proceedings of the 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1998, 16–26, https://doi.org/10.1145/277651.277660.
-
G. E. Blelloch, J. T. Fineman, P. B. Gibbons, J. Shun. Internally deterministic parallel algorithms can be fast. ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) (2012), 181–192, https://doi.org/10.1145/2145816.2145840.
-
G. E. Blelloch, J. T. Fineman, J. Shun. Greedy sequential maximal independent set and matching are parallel on average. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2012), 308–317, https://doi.org/10.1145/2312005.2312058.
-
G. E. Blelloch, D. Ferizovic, Y. Sun. Just join for parallel ordered sets. Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016, 253–264, https://doi.org/10.1145/2935764.2935768.
-
G. E. Blelloch, D. Anderson, L. Dhulipala. ParlayLib: a toolkit for parallel algorithms on shared-memory multicore machines. Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020, 507–509, https://doi.org/10.1145/3350755.3400254.
-
G. E. Blelloch, D. Ferizovic, Y. Sun. Joinable parallel balanced binary trees. ACM Transactions on Parallel Computing 9(2) (2022), 1–41, https://doi.org/10.1145/3512769.
-
B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13(7) (1970), 422–426, https://doi.org/10.1145/362686.362692.
-
M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, R. E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences 7(4) (1973), 448–461, https://doi.org/10.1016/S0022-0000(73)80033-9.
-
A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen, J. Seiferas. The smallest automaton recognizing the subwords of a text. Theoretical Computer Science 40 (1985), 31–55, https://doi.org/10.1016/0304-3975(85)90157-4.
-
R. D. Blumofe, C. E. Leiserson. Scheduling multithreaded computations by work stealing. Journal of the ACM 46(5) (1999), 720–748, https://doi.org/10.1145/324133.324234.
-
H.-J. Boehm, S. V. Adve. Foundations of the C++ concurrency memory model. Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2008, 68–78, https://doi.org/10.1145/1375581.1375591.
-
H.-J. Boehm. Can seqlocks get along with programming language memory models? Proceedings of the ACM SIGPLAN Workshop on Memory Systems Performance and Correctness (MSPC), 2012, 12–20, https://doi.org/10.1145/2247684.2247688.
-
A. Boffa, P. Ferragina, G. Vinciguerra. A “learned” approach to quicken and compress rank/select dictionaries. Proceedings of the 23rd Symposium on Algorithm Engineering and Experiments (ALENEX 2021), 46–59, 2021, https://doi.org/10.1137/1.9781611976472.4.
-
A. Boffa, P. Ferragina, G. Vinciguerra. A learned approach to design compressed rank/select data structures. ACM Transactions on Algorithms 18(3) (2022), 1–28, https://doi.org/10.1145/3524060.
-
P. Boldi, S. Vigna. The WebGraph framework I: compression techniques. Proceedings of the 13th International World Wide Web Conference (WWW 2004), 595–602, 2004, https://doi.org/10.1145/988672.988752.
-
P. Boldi, M. Rosa, M. Santini, S. Vigna. Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks. Proceedings of the 20th International World Wide Web Conference (WWW 2011), 587–596, 2011, https://doi.org/10.1145/1963405.1963488.
-
J. Bonwick. The slab allocator: an object-caching kernel memory allocator. Proceedings of the USENIX Summer 1994 Technical Conference, 1994, https://www.usenix.org/legacy/publications/library/proceedings/bos94/bonwick.html.
-
P. Bose, K. Douïeb, S. Langerman. Dynamic optimality for skip lists and B-trees. Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), 2008, 1106–1114.
-
R. S. Boyer, J. S. Moore. A fast string searching algorithm. Communications of the ACM 20(10) (1977), 762–772, https://doi.org/10.1145/359842.359859.
-
N. Brackett-Rozinsky, D. Lemire. Batched ranged random integer generation. Software: Practice and Experience 55(1) (2025), 155–169, https://doi.org/10.1002/spe.3369.
-
B. Bramas. A novel hybrid quicksort algorithm vectorized using AVX-512 on Intel Skylake. International Journal of Advanced Computer Science and Applications 8(10) (2017), article 44, https://doi.org/10.14569/IJACSA.2017.081044.
-
U. Brandes. A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology 25(2) (2001), 163–177, https://doi.org/10.1080/0022250X.2001.9990249.
-
P. Brass. Advanced Data Structures. Cambridge University Press, 2008, https://doi.org/10.1017/CBO9780511800191.
-
D. Brélaz. New methods to color the vertices of a graph. Communications of the ACM 22(4) (1979), 251–256, https://doi.org/10.1145/359094.359101.
-
R. P. Brent. Reducing the retrieval time of scatter storage techniques. Communications of the ACM 16(2) (1973), 105–109, https://doi.org/10.1145/361952.361964.
-
R. P. Brent. The parallel evaluation of general arithmetic expressions. Journal of the ACM 21(2) (1974), 201–206, https://doi.org/10.1145/321812.321815.
-
R. P. Brent. An improved Monte Carlo factorization algorithm. BIT Numerical Mathematics 20(2) (1980), 176–184, https://doi.org/10.1007/BF01933190.
-
R. P. Brent, P. Zimmermann. Modern Computer Arithmetic. Cambridge University Press, 2010, https://doi.org/10.1017/CBO9780511921698.
-
T. M. Breyer, R. E. Korf. 1.6-bit pattern databases. Proceedings of the 24th AAAI Conference on Artificial Intelligence, 39–44, 2010, https://doi.org/10.1609/aaai.v24i1.7558.
-
P. Briggs, L. Torczon. An efficient representation for sparse sets. ACM Letters on Programming Languages and Systems 2(1–4) (1993), 59–69, https://doi.org/10.1145/176454.176484.
-
N. R. Brisaboa, A. Fariña, G. Navarro, J. R. Paramá. Lightweight natural language text compression. Information Retrieval 10(1) (2007), 1–33, https://doi.org/10.1007/s10791-006-9001-9.
-
N. R. Brisaboa, S. Ladra, G. Navarro. k2-trees for compact web graph representation. Proceedings of the 16th Symposium on String Processing and Information Retrieval (SPIRE 2009), LNCS 5721, 18–30, 2009, https://doi.org/10.1007/978-3-642-03784-9_3.
-
N. R. Brisaboa, S. Ladra, G. Navarro. DACs: bringing direct access to variable-length codes. Information Processing and Management 49(1) (2013), 392–404, https://doi.org/10.1016/j.ipm.2012.08.003.
-
N. R. Brisaboa, S. Ladra, G. Navarro. Compact representation of Web graphs with extended functionality. Information Systems 39 (2014), 152–174, https://doi.org/10.1016/j.is.2013.08.003.
-
G. S. Brodal, R. Fagerberg, K. Vinther. Engineering a cache-oblivious sorting algorithm. ACM Journal of Experimental Algorithmics 12 (2008), 1–23, https://doi.org/10.1145/1227161.1227164.
-
A. Z. Broder, M. Mitzenmacher. Network applications of Bloom filters: a survey. Internet Mathematics 1(4) (2004), 485–509, https://doi.org/10.1080/15427951.2004.10129096.
-
A. Brodnik, S. Carlsson, E. D. Demaine, J. I. Munro, R. Sedgewick. Resizable arrays in optimal time and space. Algorithms and Data Structures (WADS 1999), LNCS 1663 (1999), 37–48, https://doi.org/10.1007/3-540-48447-7_4.
-
F. Broquedis, J. Clet-Ortega, S. Moreaud, N. Furmento, B. Goglin, G. Mercier, S. Thibault, R. Namyst. hwloc: a generic framework for managing hardware affinities in HPC applications. 18th Euromicro Conference on Parallel, Distributed and Network-based Processing (PDP 2010), 180–186, https://doi.org/10.1109/PDP.2010.67.
-
M. R. Brown, R. E. Tarjan. A fast merging algorithm. Journal of the ACM 26(2) (1979), 211–226, https://doi.org/10.1145/322123.322127.
-
N. K. Brown, T. Gagie, M. Rossi. RLBWT tricks. 20th International Symposium on Experimental Algorithms (SEA 2022), LIPIcs 233 (2022), 16:1–16:16, https://doi.org/10.4230/LIPIcs.SEA.2022.16.
-
M. Budiu, T. Chajed, F. McSherry, L. Ryzhyk, V. Tannen. DBSP: automatic incremental view maintenance for rich query languages. Proceedings of the VLDB Endowment 16(7) (2023), 1601–1614, https://doi.org/10.14778/3587136.3587137.
-
R. W. Bulterman, F. W. van der Sommen, G. Zwaan, T. Verhoeff, A. J. M. van Gasteren, W. H. J. Feijen. On computing a longest path in a tree. Information Processing Letters 81(2) (2002), 93–96, https://doi.org/10.1016/S0020-0190(01)00198-3.
-
E. Burns, S. Lemons, W. Ruml, R. Zhou. Best-first heuristic search for multicore machines. Journal of Artificial Intelligence Research 39 (2010), 689–743, https://doi.org/10.1613/jair.3094.
-
E. Burns, M. Hatem, M. J. Leighton, W. Ruml. Implementing fast heuristic search code. Proceedings of the 5th Annual Symposium on Combinatorial Search (SoCS 2012), 2012, 25–32, https://doi.org/10.1609/socs.v3i1.18245.
-
M. Burrows, D. J. Wheeler. A block-sorting lossless data compression algorithm. Technical Report 124, Digital Systems Research Center, Palo Alto, 1994.
-
M. Cadoli, M. Lenzerini, P. Naggar, A. Schaerf. Fondamenti della progettazione dei programmi: principi, tecniche e loro applicazioni in C++. CittàStudi, 1997.
-
J. A. Cain, P. Sanders, N. Wormald. The random graph threshold for \(k\)-orientiability and a fast algorithm for optimal multiple-choice allocation. Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, 469–476, https://publikationen.bibliothek.kit.edu/1000009500.
-
L. Carter, R. Floyd, J. Gill, G. Markowsky, M. Wegman. Exact and approximate membership testers. In: Proceedings of the 10th ACM Symposium on Theory of Computing (STOC 1978), 1978, 59–65, https://doi.org/10.1145/800133.804332.
-
J. L. Carter, M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences 18(2) (1979), 143–154, https://doi.org/10.1016/0022-0000(79)90044-8.
-
I. Carvalho. Towards parallel learned sorting. arXiv:2208.06902 (2022), https://doi.org/10.48550/arXiv.2208.06902.
-
S. Chambi, D. Lemire, O. Kaser, R. Godin. Better bitmap performance with Roaring bitmaps. Software: Practice and Experience 46(5) (2016), 709–719, https://doi.org/10.1002/spe.2325.
-
C. Charras, T. Lecroq. Handbook of Exact String Matching Algorithms. King's College Publications, 2004.
-
D. Chase, Y. Lev. Dynamic circular work-stealing deque. Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2005, 21–28, https://doi.org/10.1145/1073970.1073974.
-
B. Chazelle, L. J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica 1(1–4) (1986), 133–162, https://doi.org/10.1007/BF01840440.
-
K. T. Chen, R. H. Fox, R. C. Lyndon. Free differential calculus, IV. The quotient groups of the lower central series. Annals of Mathematics 68(1) (1958), 81–95, https://doi.org/10.2307/1970044.
-
S. Chen, P. B. Gibbons, T. C. Mowry. Improving index performance through prefetching. Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data (SIGMOD 2001), 2001, 235–246, https://doi.org/10.1145/375663.375688.
-
S. Chen, A. Ailamaki, P. B. Gibbons, T. C. Mowry. Improving hash join performance through prefetching. Proceedings of the 20th International Conference on Data Engineering (ICDE 2004), 2004, 116–127, https://doi.org/10.1109/ICDE.2004.1319989.
-
M. Chen, R. A. Chowdhury, V. Ramachandran, D. Lan Roche, L. Tong. Priority queues and Dijkstra's algorithm. Technical Report TR-07-54, The University of Texas at Austin, 2007, https://www3.cs.stonybrook.edu/~rezaul/papers/TR-07-54.pdf.
-
G. Chen, S. J. Puglisi, W. F. Smyth. Lempel-Ziv factorization using less time & space. Mathematics in Computer Science 1(4) (2008), 605–623, https://doi.org/10.1007/s11786-007-0024-4.
-
G. Chen, Z. He, M. Li, S. Luo. Oasis: an optimal disjoint segmented learned range filter. Proceedings of the VLDB Endowment 17(8) (2024), 1911–1924, https://doi.org/10.14778/3659437.3659447.
-
J. Cheriyan, S. N. Maheshwari. Analysis of preflow push algorithms for maximum network flow. SIAM Journal on Computing 18(6) (1989), 1057–1086, https://doi.org/10.1137/0218072.
-
B. V. Cherkassky, A. V. Goldberg, T. Radzik. Shortest paths algorithms: theory and experimental evaluation. Mathematical Programming 73(2) (1996), 129–174, https://doi.org/10.1007/BF02592101.
-
B. V. Cherkassky, A. V. Goldberg. On implementing the push-relabel method for the maximum flow problem. Algorithmica 19(4) (1997), 390–410, https://doi.org/10.1007/PL00009180.
-
J. Chhugani, A. D. Nguyen, V. W. Lee, W. Macy, M. Hagog, Y.-K. Chen, A. Baransi, S. Kumar, P. Dubey. Efficient implementation of sorting on multi-core SIMD CPU architecture. Proceedings of the VLDB Endowment 1(2) (2008), 1313–1324, https://doi.org/10.14778/1454159.1454171.
-
Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, J. S. Vitter. External-memory graph algorithms. Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1995, 139–149.
-
N. Chiba, T. Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on Computing 14(1) (1985), 210–223, https://doi.org/10.1137/0214017.
-
F. Chin, D. Houck. Algorithms for updating minimal spanning trees. Journal of Computer and System Sciences 16(3) (1978), 333–344, https://doi.org/10.1016/0022-0000(78)90022-3.
-
K.-M. Chung, H.-I. Lu. An optimal algorithm for the maximum-density segment problem. SIAM Journal on Computing 34(2) (2005), 373–387, https://doi.org/10.1137/S0097539704440430.
-
V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4(3) (1979), 233–235, https://doi.org/10.1287/moor.4.3.233.
-
M. Ciura. Best increments for the average case of Shellsort. Proceedings of the 13th International Symposium on Fundamentals of Computation Theory (FCT 2001), LNCS 2138 (2001), 106–117, https://doi.org/10.1007/3-540-44669-9_12.
-
D. Clark. Compact Pat Trees. PhD thesis, University of Waterloo, 1996.
-
F. Claude, G. Navarro. Practical rank/select queries over arbitrary sequences. Proceedings of the 15th Symposium on String Processing and Information Retrieval (SPIRE 2008), LNCS 5280, 176–187, 2008, https://doi.org/10.1007/978-3-540-89097-3_18.
-
F. Claude, G. Navarro, A. Ordóñez. The wavelet matrix: an efficient wavelet tree for large alphabets. Information Systems 47 (2015), 15–32, https://doi.org/10.1016/j.is.2014.06.002.
-
J. G. Cleary, I. H. Witten. Data compression using adaptive coding and partial string matching. IEEE Transactions on Communications 32(4) (1984), 396–402, https://doi.org/10.1109/TCOM.1984.1096090.
-
J. G. Cleary, W. J. Teahan, I. H. Witten. Unbounded length contexts for PPM. Proceedings of the Data Compression Conference (DCC 1995), 52–61, 1995, https://doi.org/10.1109/DCC.1995.515495.
-
S. Cohen, Y. Matias. Spectral Bloom filters. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, 2003, 241–252, https://doi.org/10.1145/872757.872787.
-
R. Cole, U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control 70(1) (1986), 32–53, https://doi.org/10.1016/S0019-9958(86)80023-7.
-
Y. Collet. XXH3. In: xxHash, software, 2019, https://github.com/Cyan4973/xxHash.
-
Y. Collet. XXH3, the hash of the family xxHash for small and large inputs. Software, 2019, https://github.com/Cyan4973/xxHash.
-
Y. Collet, M. Kucherawy. Zstandard compression and the application/zstd media type. RFC 8878, 2021, https://doi.org/10.17487/RFC8878.
-
D. Comer. The ubiquitous B-tree. ACM Computing Surveys 11(2) (1979), 121–137, https://doi.org/10.1145/356770.356776.
-
S. A. Cook. The complexity of theorem-proving procedures. Proceedings of the 3rd ACM Symposium on Theory of Computing (1971), 151–158, https://doi.org/10.1145/800157.805047.
-
S. A. Cook, R. A. Reckhow. Time bounded random access machines. Journal of Computer and System Sciences 7(4) (1973), 354–375, https://doi.org/10.1016/S0022-0000(73)80029-7.
-
J. W. Cooley, J. W. Tukey. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation 19(90) (1965), 297–301, https://doi.org/10.1090/S0025-5718-1965-0178586-1.
-
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms. 3rd edition, MIT Press, 2009.
-
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms. 4th edition, MIT Press, 2022.
-
G. Cormode, K. Yi. Small Summaries for Big Data. Cambridge University Press, 2020, https://doi.org/10.1017/9781108769938.
-
M. Costa, P. Ferragina, G. Vinciguerra. Grafite: taming adversarial queries with optimal range filters. Proceedings of the ACM on Management of Data 2(1) (2024), 1–23, https://doi.org/10.1145/3639258.
-
Algorithms for Competitive Programming (cp-algorithms). https://cp-algorithms.com.
-
P. Crescenzi, R. Grossi, M. Habib, L. Lanzi, A. Marino. On computing the diameter of real-world undirected graphs. Theoretical Computer Science 514 (2013), 84–95, https://doi.org/10.1016/j.tcs.2012.09.018.
-
M. Crochemore. Transducers and repetitions. Theoretical Computer Science 45 (1986), 63–86, https://doi.org/10.1016/0304-3975(86)90041-1.
-
M. Crochemore, D. Perrin. Two-way string-matching. Journal of the ACM 38(3) (1991), 650–674, https://doi.org/10.1145/116825.116845.
-
M. Crochemore, C. S. Iliopoulos, Y. J. Pinzon, J. F. Reid. A fast and practical bit-vector algorithm for the longest common subsequence problem. Information Processing Letters 80(6) (2001), 279–285, https://doi.org/10.1016/S0020-0190(01)00182-X.
-
S. A. Crosby, D. S. Wallach. Denial of service via algorithmic complexity attacks. Proceedings of the 12th USENIX Security Symposium, 2003, 29–44.
-
D. F. Crouse. On implementing 2D rectangular assignment algorithms. IEEE Transactions on Aerospace and Electronic Systems 52(4) (2016), 1679–1696, https://doi.org/10.1109/TAES.2016.140952.
-
M. Curtiss et al.. Unicorn: a system for searching the social graph. Proceedings of the VLDB Endowment 6(11) (2013), 1150–1161, https://doi.org/10.14778/2536222.2536239.
-
E. Cuthill, J. McKee. Reducing the bandwidth of sparse symmetric matrices. Proceedings of the 24th ACM National Conference, 1969, 157–172, https://doi.org/10.1145/800195.805928.
-
Z. J. Czech, G. Havas, B. S. Majewski. An optimal algorithm for generating minimal perfect hash functions. Information Processing Letters 43(5) (1992), 257–264, https://doi.org/10.1016/0020-0190(92)90220-P.
-
S. Dahlgaard, M. B. T. Knudsen, E. Rotenberg, M. Thorup. The power of two choices with simple tabulation. Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), 2016, 1631–1642, https://doi.org/10.1137/1.9781611974331.ch111.
-
M. Danelutto, M. Torquati. Loop parallelism: a new skeleton perspective on data parallel patterns. Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP) (2014), 52–59, https://doi.org/10.1109/PDP.2014.13.
-
G. B. Dantzig. Discrete-variable extremum problems. Operations Research 5(2) (1957), 266–288, https://doi.org/10.1287/opre.5.2.266.
-
The Apache Software Foundation. Apache DataSketches. Software, https://datasketches.apache.org.
-
M. Davis, H. Putnam. A computing procedure for quantification theory. Journal of the ACM 7(3) (1960), 201–215, https://doi.org/10.1145/321033.321034.
-
M. Davis, G. Logemann, D. Loveland. A machine program for theorem-proving. Communications of the ACM 5(7) (1962), 394–397, https://doi.org/10.1145/368273.368557.
-
T. A. Davis. Direct Methods for Sparse Linear Systems. SIAM, 2006, https://doi.org/10.1137/1.9780898718881.
-
T. A. Davis. Algorithm 1000: SuiteSparse:GraphBLAS: graph algorithms in the language of sparse linear algebra. ACM Transactions on Mathematical Software 45(4) (2019), 1–25, https://doi.org/10.1145/3322125.
-
T. A. Davis. Algorithm 1037: SuiteSparse:GraphBLAS: parallel graph algorithms in the language of sparse linear algebra. ACM Transactions on Mathematical Software 49(3) (2023), 1–30, https://doi.org/10.1145/3577195.
-
N. Dayan, M. Athanassoulis, S. Idreos. Monkey: optimal navigable key-value store. Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD 2017), 2017, 79–94, https://doi.org/10.1145/3035918.3064054.
-
E. D. Demaine, A. López-Ortiz, J. I. Munro. Adaptive set intersections, unions, and differences. In: Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), 2000, 743–752.
-
E. D. Demaine, T. Jones, M. Pătrașcu. Interpolation search for non-independent data. Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004, 529–530.
-
Q. De Man, L. Dhulipala. Fast and theoretically efficient batch-parallel link-cut trees, Euler tour trees, and treaps. Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2026, 234–246, https://doi.org/10.1145/3816782.3819216.
-
R. Dementiev, L. Kettner, P. Sanders. STXXL: standard template library for XXL data sets. Software: Practice and Experience 38(6) (2008), 589–637, https://doi.org/10.1002/spe.844.
-
C. Demetrescu, I. Finocchi, G. F. Italiano. Algoritmi e strutture dati. 2nd edition, McGraw-Hill, 2008.
-
L. Devroye, G. T. Toussaint. A note on linear expected time algorithms for finding convex hulls. Computing 26(4) (1981), 361–366, https://doi.org/10.1007/BF02237955.
-
L. Devroye. Applications of the theory of records in the study of random trees. Acta Informatica 26(1–2) (1988), 123–130, https://doi.org/10.1007/BF02915448.
-
B. Dezső, A. Jüttner, P. Kovács. LEMON - an open source C++ graph template library. Electronic Notes in Theoretical Computer Science 264(5) (2011), 23–45, https://doi.org/10.1016/j.entcs.2011.06.003.
-
L. Dhulipala, G. E. Blelloch, J. Shun. Julienne: a framework for parallel graph algorithms using work-efficient bucketing. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2017), 293–304, https://doi.org/10.1145/3087556.3087580.
-
L. Dhulipala, G. E. Blelloch, J. Shun. Theoretically efficient parallel graph algorithms can be fast and scalable. ACM Transactions on Parallel Computing 8(1) (2021), 1–70, https://doi.org/10.1145/3434393.
-
L. Dhulipala, G. E. Blelloch, Y. Gu, Y. Sun. PaC-trees: supporting parallel and compressed purely-functional collections. Proceedings of the 43rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2022, 108–121, https://doi.org/10.1145/3519939.3523733.
-
R. B. Dial. Algorithm 360: shortest-path forest with topological ordering. Communications of the ACM 12(11) (1969), 632–633, https://doi.org/10.1145/363269.363610.
-
P. Dietz, D. Sleator. Two algorithms for maintaining order in a list. Proceedings of the 19th ACM Symposium on Theory of Computing (STOC), 1987, 365–372, https://doi.org/10.1145/28395.28434.
-
P. F. Dietz, J. Zhang. Lower bounds for monotonic list labeling. Algorithm Theory (SWAT 90), LNCS 447 (1990), 173–180, https://doi.org/10.1007/3-540-52846-6_87.
-
M. Dietzfelbinger, J. Gil, Y. Matias, N. Pippenger. Polynomial hash functions are reliable. In: Automata, Languages and Programming (ICALP 1992), Lecture Notes in Computer Science 623, 1992, 235–246, https://doi.org/10.1007/3-540-55719-9_77.
-
M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, R. E. Tarjan. Dynamic perfect hashing: upper and lower bounds. SIAM Journal on Computing 23(4) (1994), 738–761, https://doi.org/10.1137/S0097539791194094.
-
M. Dietzfelbinger. Universal hashing and k-wise independent random variables via integer arithmetic without primes. In: STACS 96, Lecture Notes in Computer Science 1046, Springer, 1996, 567–580, https://doi.org/10.1007/3-540-60922-9_46.
-
M. Dietzfelbinger, T. Hagerup, J. Katajainen, M. Penttonen. A reliable randomized algorithm for the closest-pair problem. Journal of Algorithms 25(1) (1997), 19–51, https://doi.org/10.1006/jagm.1997.0873.
-
M. Dietzfelbinger, C. Weidling. Balanced allocation and dictionaries with tightly packed constant size bins. Theoretical Computer Science 380(1–2) (2007), 47–68, https://doi.org/10.1016/j.tcs.2007.02.054.
-
M. Dietzfelbinger, M. Mitzenmacher, M. Rink. Cuckoo hashing with pages. Algorithms, ESA 2011, LNCS 6942 (2011), 615–627, https://doi.org/10.1007/978-3-642-23719-5_52.
-
M. Dietzfelbinger, S. Walzer. Dense peelable random uniform hypergraphs. In: 27th Annual European Symposium on Algorithms (ESA 2019), LIPIcs 144, 2019, 38:1–38:16, https://doi.org/10.4230/LIPIcs.ESA.2019.38.
-
M. Dietzfelbinger, S. Walzer. Efficient Gauss elimination for near-quadratic matrices with one short random block per row, with applications. In: 27th Annual European Symposium on Algorithms (ESA 2019), LIPIcs 144, 2019, 39:1–39:18, https://doi.org/10.4230/LIPIcs.ESA.2019.39.
-
E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik 1(1) (1959), 269–271, https://doi.org/10.1007/BF01386390.
-
E. W. Dijkstra. Algol 60 translation. Report MR 34/61, Mathematisch Centrum, Amsterdam, 1961.
-
E. W. Dijkstra. Solution of a problem in concurrent programming control. Communications of the ACM 8(9) (1965), 569, https://doi.org/10.1145/365559.365617.
-
E. W. Dijkstra. A Discipline of Programming. Prentice-Hall, 1976.
-
E. W. Dijkstra, C. S. Scholten. Termination detection for diffusing computations. Information Processing Letters 11(1) (1980), 1–4, https://doi.org/10.1016/0020-0190(80)90021-6.
-
P. C. Dillinger, S. Walzer. Ribbon filter: practically smaller than Bloom and Xor. arXiv:2103.02515, 2021, https://arxiv.org/abs/2103.02515.
-
B. Ding, A. C. König. Fast set intersection in memory. Proceedings of the VLDB Endowment 4(4) (2011), 255–266, https://doi.org/10.14778/1938545.1938550.
-
E. A. Dinic. Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Mathematics Doklady 11 (1970), 1277–1280.
-
P. Dinklage, J. Ellert, J. Fischer, F. Kurpicz, M. Löbel. Practical wavelet tree construction. ACM Journal of Experimental Algorithmics 26 (2021), 1–67, https://doi.org/10.1145/3457197.
-
P. Dinklage, J. Fischer, F. Kurpicz, J.-P. Tarnowski. Bit-parallel (compressed) wavelet tree construction. Proceedings of the 33rd Data Compression Conference (DCC 2023), 81–90, 2023, https://doi.org/10.1109/DCC55655.2023.00016.
-
W. Dobosiewicz. An efficient variation of bubble sort. Information Processing Letters 11(1) (1980), 5–6, https://doi.org/10.1016/0020-0190(80)90022-8.
-
M. Dominiak, G. Evtushenko, L. Baker, L. R. Teodorescu, L. Howes, K. Shoop, M. Garland, E. Niebler, B. A. Lelbach. std::execution. ISO/IEC JTC1 SC22 WG21 P2300R10, 2024, https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p2300r10.html.
-
X. Dong, Y. Gu, Y. Sun, Y. Zhang. Efficient stepping algorithms and implementations for parallel shortest paths. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2021), 184–197, https://doi.org/10.1145/3409964.3461782.
-
U. Drepper. What every programmer should know about memory. Red Hat, Inc., 2007.
-
D. Dube, H. Yokoo. Fast construction of almost optimal symbol distributions for asymmetric numeral systems. Proceedings of the IEEE International Symposium on Information Theory (ISIT 2019), 1682–1686, 2019, https://doi.org/10.1109/ISIT.2019.8849430.
-
J. Duda. Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding. arXiv:1311.2540, 2013, https://arxiv.org/abs/1311.2540.
-
J. Duda, K. Tahboub, N. J. Gadgil, E. J. Delp. The use of asymmetric numeral systems as an accurate replacement for Huffman coding. Proceedings of the 31st Picture Coding Symposium (PCS 2015), 65–69, 2015, https://doi.org/10.1109/PCS.2015.7170048.
-
R. Durstenfeld. Algorithm 235: random permutation. Communications of the ACM 7(7) (1964), 420, https://doi.org/10.1145/364520.364540.
-
J.-P. Duval. Factorizing words over an ordered alphabet. Journal of Algorithms 4(4) (1983), 363–381, https://doi.org/10.1016/0196-6774(83)90017-2.
-
S. Edelkamp, A. Weiß. BlockQuicksort: avoiding branch mispredictions in quicksort. 24th Annual European Symposium on Algorithms (ESA 2016), LIPIcs 57, 2016, 38:1–38:16, https://doi.org/10.4230/LIPIcs.ESA.2016.38.
-
S. Edelkamp, A. Weiß. BlockQuicksort: avoiding branch mispredictions in quicksort. ACM Journal of Experimental Algorithmics 24 (2019), article 1.4, https://doi.org/10.1145/3274660.
-
H. Edelsbrunner. Dynamic data structures for orthogonal intersection queries. Report F59, Institut für Informationsverarbeitung, Technische Universität Graz, 1980.
-
J. Edmonds. Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards 69B (1965), 125–130, https://doi.org/10.6028/jres.069B.013.
-
J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics 17 (1965), 449–467, https://doi.org/10.4153/CJM-1965-045-4.
-
J. Edmonds, R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM 19(2) (1972), 248–264, https://doi.org/10.1145/321694.321699.
-
P. S. Efraimidis, P. G. Spirakis. Weighted random sampling with a reservoir. Information Processing Letters 97(5) (2006), 181–185, https://doi.org/10.1016/j.ipl.2005.11.003.
-
P. Elias. Efficient storage and retrieval by content and address of static files. Journal of the ACM 21(2) (1974), 246–260, https://doi.org/10.1145/321812.321820.
-
P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory 21(2) (1975), 194–203, https://doi.org/10.1109/TIT.1975.1055349.
-
A. Elmasry. Pairing heaps with \(O( \log \log n )\) decrease cost. Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009, 471–476, https://doi.org/10.1137/1.9781611973068.52.
-
D. Eppstein. Offline algorithms for dynamic minimum spanning tree problems. Journal of Algorithms 17(2) (1994), 237–250, https://doi.org/10.1006/jagm.1994.1033.
-
F. Ergun, S. C. Sahinalp, J. Sharp, R. Sinha. Biased dictionaries with fast insert/deletes. Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC 2001), 2001, 483–491, https://doi.org/10.1145/380752.380843.
-
N. Eslami, N. Dayan. Memento filter: a fast, dynamic, and robust range filter. Proceedings of the ACM on Management of Data 2(6) (2024), 244:1–244:27, https://doi.org/10.1145/3698820.
-
N. Eslami, I. O. Bercea, N. Dayan. Diva: dynamic range filter for var-length keys and queries. Proceedings of the VLDB Endowment 18(11) (2025), 3923–3936, https://doi.org/10.14778/3749646.3749664.
-
E. Esposito, T. M. Graf, S. Vigna. RecSplit: minimal perfect hashing via recursive splitting. Proceedings of the 22nd Workshop on Algorithm Engineering and Experiments (ALENEX 2020), 2020, 175–185, https://doi.org/10.1137/1.9781611976007.14.
-
S. Even, R. E. Tarjan. Network flow and testing graph connectivity. SIAM Journal on Computing 4(4) (1975), 507–518, https://doi.org/10.1137/0204043.
-
T. Even, G. Even, A. Morrison. Prefix filter: practically and theoretically better than Bloom. Proceedings of the VLDB Endowment 15(7) (2022), 1311–1323, https://doi.org/10.14778/3523210.3523211.
-
M. Eytzinger. Thesaurus principum hac aetate in Europa viventium. Cologne, 1590.
-
L. Fan, P. Cao, J. Almeida, A. Z. Broder. Summary cache: a scalable wide-area web cache sharing protocol. IEEE/ACM Transactions on Networking 8(3) (2000), 281–293, https://doi.org/10.1109/90.851975.
-
B. Fan, D. G. Andersen, M. Kaminsky. MemC3: compact and concurrent MemCache with dumber caching and smarter hashing. Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2013, 371–384.
-
B. Fan, D. G. Andersen, M. Kaminsky, M. D. Mitzenmacher. Cuckoo filter: practically better than Bloom. In: Proceedings of the 10th ACM International Conference on Emerging Networking Experiments and Technologies (CoNEXT 2014), 2014, 75–88, https://doi.org/10.1145/2674005.2674994.
-
R. M. Fano. On the number of bits required to implement an associative memory. Memorandum 61, Computation Structures Group, Project MAC, MIT, 1971.
-
M. Farach. Optimal suffix tree construction with large alphabets. Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), 1997, 137–143, https://doi.org/10.1109/SFCS.1997.646102.
-
S. Faro, M. O. Kulekci. Fast packed string matching for short patterns. Proceedings of the 15th Workshop on Algorithm Engineering and Experiments (ALENEX), 2013, 113–121, https://doi.org/10.1137/1.9781611972931.10.
-
S. Faro, T. Lecroq. The exact online string matching problem: a review of the most recent results. ACM Computing Surveys 45(2) (2013), 13:1–13:42, https://doi.org/10.1145/2431211.2431212.
-
A. Felner, R. E. Korf, S. Hanan. Additive pattern database heuristics. Journal of Artificial Intelligence Research 22 (2004), 279–318, https://doi.org/10.1613/jair.1480.
-
P. M. Fenwick. A new data structure for cumulative frequency tables. Software: Practice and Experience 24(3) (1994), 327–336, https://doi.org/10.1002/spe.4380240306.
-
D. E. Ferguson. Fibonaccian searching. Communications of the ACM 3(12) (1960), 648, https://doi.org/10.1145/367487.367496.
-
P. Ferragina, R. Grossi. The string B-tree: a new data structure for string search in external memory and its applications. Journal of the ACM 46(2) (1999), 236–280, https://doi.org/10.1145/301970.301973.
-
P. Ferragina, G. Manzini. Opportunistic data structures with applications. Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS 2000), 390–398, 2000, https://doi.org/10.1109/SFCS.2000.892127.
-
P. Ferragina, G. Manzini. Indexing compressed text. Journal of the ACM 52(4) (2005), 552–581, https://doi.org/10.1145/1082036.1082039.
-
P. Ferragina, R. Giancarlo, G. Manzini, M. Sciortino. Boosting textual compression in optimal linear time. Journal of the ACM 52(4) (2005), 688–713, https://doi.org/10.1145/1082036.1082043.
-
P. Ferragina, G. Manzini, V. Mäkinen, G. Navarro. Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms 3(2) (2007), 20, https://doi.org/10.1145/1240233.1240243.
-
P. Ferragina, R. Grossi, A. Gupta, R. Shah, J. S. Vitter. On searching compressed string collections cache-obliviously. Proceedings of the 27th ACM Symposium on Principles of Database Systems (PODS), 2008, 181–190, https://doi.org/10.1145/1376916.1376943.
-
P. Ferragina, I. Nitto, R. Venturini. On the bit-complexity of Lempel-Ziv compression. SIAM Journal on Computing 42(4) (2013), 1521–1541, https://doi.org/10.1137/120869511.
-
P. Ferragina, G. Vinciguerra. The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds. Proceedings of the VLDB Endowment 13(8) (2020), 1162–1175, https://doi.org/10.14778/3389133.3389135.
-
P. Ferragina. Pearls of Algorithm Engineering. Cambridge University Press, 2023, https://doi.org/10.1017/9781009128933.
-
P. Ferragina, M. Odorisio. Fast, robust, and learned distribution-based sorting. IEEE Access 13 (2025), 45198–45214, https://doi.org/10.1109/ACCESS.2025.3549626.
-
G. Fici, T. Gagie, J. Kärkkäinen, D. Kempa. A subquadratic algorithm for minimum palindromic factorization. Journal of Discrete Algorithms 28 (2014), 41–48, https://doi.org/10.1016/j.jda.2014.08.001.
-
J. Fischer, V. Heun. Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM Journal on Computing 40(2) (2011), 465–492, https://doi.org/10.1137/090779759.
-
J. Fischer, F. Kurpicz. Dismantling DivSufSort. Proceedings of the Prague Stringology Conference (PSC), 2017, 62–76, https://arxiv.org/abs/1710.01896.
-
M. Fischer, A. Noever. Tight analysis of parallel randomized greedy MIS. ACM-SIAM Symposium on Discrete Algorithms (SODA) (2018), 2152–2160, https://doi.org/10.1137/1.9781611975031.140.
-
R. A. Fisher, F. Yates. Statistical Tables for Biological, Agricultural and Medical Research. Oliver and Boyd, 1938.
-
R. W. Floyd. Algorithm 97: Shortest path. Communications of the ACM 5(6) (1962), 345, https://doi.org/10.1145/367766.368168.
-
R. W. Floyd. Algorithm 245: Treesort 3. Communications of the ACM 7(12) (1964), 701, https://doi.org/10.1145/355588.365103.
-
R. W. Floyd, R. L. Rivest. Expected time bounds for selection. Communications of the ACM 18(3) (1975), 165–172, https://doi.org/10.1145/360680.360691.
-
R. W. Floyd, R. L. Rivest. Algorithm 489: the algorithm SELECT, for finding the ith smallest of n elements. Communications of the ACM 18(3) (1975), 173, https://doi.org/10.1145/360680.360694.
-
L. R. Ford, D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics 8 (1956), 399–404, https://doi.org/10.4153/CJM-1956-045-5.
-
L. R. Ford Jr. Network flow theory. Paper P-923, RAND Corporation, Santa Monica, 1956.
-
L. R. Ford, S. M. Johnson. A tournament problem. The American Mathematical Monthly 66(5) (1959), 387–389, https://doi.org/10.2307/2308750.
-
M. Forišek, J. Jančina. Fast primality testing for integers that fit into a machine word. SOFSEM 2015 Student Research Forum, CEUR Workshop Proceedings 1326 (2015), 20–30, https://ceur-ws.org/Vol-1326/020-Forisek.pdf.
-
D. Fotakis, R. Pagh, P. Sanders, P. Spirakis. Space efficient hash tables with worst case constant access time. Theory of Computing Systems 38(2) (2005), 229–248, https://doi.org/10.1007/s00224-004-1195-x.
-
E. Fouh, V. Karavirta, D. A. Breakiron, S. Hamouda, S. Hall, T. L. Naps, C. A. Shaffer. Design and architecture of an interactive eTextbook – the OpenDSA system. Science of Computer Programming 88 (2014), 22–40, https://doi.org/10.1016/j.scico.2013.11.040.
-
E. A. Fox, Q. F. Chen, L. S. Heath. A faster algorithm for constructing minimal perfect hash functions. Proceedings of the 15th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 1992), 1992, 266–273, https://doi.org/10.1145/133160.133209.
-
A. Frangioni, A. Manca. A computational study of cost reoptimization for min-cost flow problems. INFORMS Journal on Computing 18(1) (2006), 61–70, https://doi.org/10.1287/ijoc.1040.0081.
-
K. Fraser. Practical lock-freedom. PhD thesis, Technical Report UCAM-CL-TR-579, University of Cambridge, 2004, https://doi.org/10.48456/tr-579.
-
W. D. Frazer, A. C. McKellar. Samplesort: a sampling approach to minimal storage tree sorting. Journal of the ACM 17(3) (1970), 496–507, https://doi.org/10.1145/321592.321600.
-
G. N. Frederickson, D. B. Johnson. The complexity of selection and ranking in X + Y and matrices with sorted columns. Journal of Computer and System Sciences 24(2) (1982), 197–208, https://doi.org/10.1016/0022-0000(82)90048-4.
-
G. N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM Journal on Computing 14(4) (1985), 781–798, https://doi.org/10.1137/0214055.
-
G. N. Frederickson. Optimal algorithms for tree partitioning. Proceedings of the 2nd ACM-SIAM Symposium on Discrete Algorithms (1991), 168–177.
-
E. Fredkin. Trie memory. Communications of the ACM 3(9) (1960), 490–499, https://doi.org/10.1145/367390.367400.
-
M. L. Fredman. On computing the length of longest increasing subsequences. Discrete Mathematics 11(1) (1975), 29–35, https://doi.org/10.1016/0012-365X(75)90103-X.
-
M. L. Fredman, J. Komlós, E. Szemerédi. Storing a sparse table with O(1) worst case access time. Journal of the ACM 31(3) (1984), 538–544, https://doi.org/10.1145/828.1884.
-
M. L. Fredman, R. Sedgewick, D. D. Sleator, R. E. Tarjan. The pairing heap: a new form of self-adjusting heap. Algorithmica 1(1-4) (1986), 111–129, https://doi.org/10.1007/BF01840439.
-
M. L. Fredman, R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34(3) (1987), 596–615, https://doi.org/10.1145/28869.28874.
-
M. L. Fredman, D. E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences 47(3) (1993), 424–436, https://doi.org/10.1016/0022-0000(93)90040-4.
-
M. L. Fredman. On the efficiency of pairing heaps and related data structures. Journal of the ACM 46(4) (1999), 473–501, https://doi.org/10.1145/320211.320214.
-
R. Freivalds. Probabilistic machines can use less running time. Proceedings of the IFIP Congress 1977, 839–842.
-
D. Frigioni, A. Marchetti-Spaccamela, U. Nanni. Fully dynamic algorithms for maintaining shortest paths trees. Journal of Algorithms 34(2) (2000), 251–281, https://doi.org/10.1006/jagm.1999.1048.
-
M. Frigo, C. E. Leiserson, K. H. Randall. The implementation of the Cilk-5 multithreaded language. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) (1998), 212–223, https://doi.org/10.1145/277650.277725.
-
M. Frigo, C. E. Leiserson, H. Prokop, S. Ramachandran. Cache-oblivious algorithms. ACM Transactions on Algorithms 8(1) (2012), 4:1–4:22, https://doi.org/10.1145/2071379.2071383.
-
L. Fuentes-Sepúlveda, E. Elejalde, L. Ferres, D. Seco. Parallel construction of wavelet trees on multicore architectures. Knowledge and Information Systems 51(3) (2017), 1043–1066, https://doi.org/10.1007/s10115-016-1000-6.
-
H. N. Gabow. Implementation of algorithms for maximum matching on nonbipartite graphs. PhD thesis, Stanford University, 1973.
-
H. N. Gabow. An efficient implementation of Edmonds' algorithm for maximum matching on graphs. Journal of the ACM 23(2) (1976), 221–234, https://doi.org/10.1145/321941.321942.
-
H. N. Gabow. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. Proceedings of the 15th ACM Symposium on Theory of Computing, 1983, 448–456, https://doi.org/10.1145/800061.808776.
-
H. N. Gabow, R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences 30(2) (1985), 209–221, https://doi.org/10.1016/0022-0000(85)90014-5.
-
H. N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1990, 434–443.
-
T. Gagie, G. Navarro, N. Prezza. Optimal-time text indexing in BWT-runs bounded space. Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 1459–1477, 2018, https://doi.org/10.1137/1.9781611975031.96.
-
T. Gagie, G. Navarro, N. Prezza. Fully functional suffix trees and optimal text searching in BWT-runs bounded space. Journal of the ACM 67(1) (2020), 2, https://doi.org/10.1145/3375890.
-
H. Gajewska, R. E. Tarjan. Deques with heap order. Information Processing Letters 22(4) (1986), 197–200, https://doi.org/10.1016/0020-0190(86)90028-1.
-
Z. Galil. Efficient algorithms for finding maximum matching in graphs. ACM Computing Surveys 18(1) (1986), 23–38, https://doi.org/10.1145/6462.6502.
-
R. G. Gallager, D. C. van Voorhis. Optimal source codes for geometrically distributed integer alphabets. IEEE Transactions on Information Theory 21(2) (1975), 228–230, https://doi.org/10.1109/TIT.1975.1055357.
-
B. A. Galler, M. J. Fischer. An improved equivalence algorithm. Communications of the ACM 7(5) (1964), 301–303, https://doi.org/10.1145/364099.364331.
-
I. Galperin, R. L. Rivest. Scapegoat trees. Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1993, 165–174.
-
A. Gambin, A. Malinowski. Randomized meldable priority queues. Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM'98), LNCS 1521 (1998), 344–349, https://doi.org/10.1007/3-540-49477-4_26.
-
E. Gamma, R. Helm, R. Johnson, J. Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, 1994.
-
M. R. Garey, D. S. Johnson. "Strong" NP-completeness results: motivation, examples, and implications. Journal of the ACM 25(3) (1978), 499–508, https://doi.org/10.1145/322077.322090.
-
M. R. Garey, D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
-
A. M. Garsia, M. L. Wachs. A new algorithm for minimum cost binary trees. SIAM Journal on Computing 6(4) (1977), 622–642, https://doi.org/10.1137/0206045.
-
F. Giesen. Interleaved entropy coders. arXiv:1402.3392, 2014, https://arxiv.org/abs/1402.3392.
-
R. L. Gilstad. Polyphase merge sorting: an advanced technique. Proceedings of the Eastern Joint IRE-AIEE-ACM Computer Conference 18, 1960, 143–148, https://doi.org/10.1145/1460512.1460524.
-
A. Goel, S. Khanna, D. H. Larkin, R. E. Tarjan. Disjoint set union with randomized linking. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 2014, 1005–1017, https://doi.org/10.1137/1.9781611973402.75.
-
S. Gog, M. Petri. Optimized succinct data structures for massive data. Software: Practice and Experience 44(11) (2014), 1287–1314, https://doi.org/10.1002/spe.2198.
-
S. Gog, T. Beller, A. Moffat, M. Petri. From theory to practice: plug and play with succinct data structures. Proceedings of the 13th Symposium on Experimental Algorithms (SEA 2014), LNCS 8504, 326–337, 2014, https://doi.org/10.1007/978-3-319-07959-2_28.
-
A. V. Goldberg, R. E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM 35(4) (1988), 921–940, https://doi.org/10.1145/48014.61051.
-
A. V. Goldberg, S. Hed, H. Kaplan, P. Kohli, R. E. Tarjan, R. F. Werneck. Faster and more dynamic maximum flow by incremental breadth-first search. Proceedings of the 23rd European Symposium on Algorithms (ESA 2015), LNCS 9294 (2015), 619–630, https://doi.org/10.1007/978-3-662-48350-3_52.
-
M. H. Goldwasser, M.-Y. Kao, H.-I. Lu. Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications. Journal of Computer and System Sciences 70(2) (2005), 128–144, https://doi.org/10.1016/j.jcss.2004.08.001.
-
M. Golin, R. Raman, C. Schwarz, M. Smid. Simple randomized algorithms for closest pair problems. Nordic Journal of Computing 2(1) (1995), 3–27.
-
S. W. Golomb. Run-length encodings. IEEE Transactions on Information Theory 12(3) (1966), 399–401, https://doi.org/10.1109/TIT.1966.1053907.
-
G. H. Gonnet, R. A. Baeza-Yates, T. Snider. New indices for text: PAT trees and PAT arrays. In W. B. Frakes, R. A. Baeza-Yates (eds.), Information Retrieval: Data Structures and Algorithms, Prentice-Hall, 1992, 66–82.
-
M. T. Goodrich, J. G. Kloss. Tiered vectors: efficient dynamic arrays for rank-based sequences. Algorithms and Data Structures (WADS 1999), LNCS 1663 (1999), 205–216, https://doi.org/10.1007/3-540-48447-7_21.
-
M. Goswami, A. Grønlund, K. G. Larsen, R. Pagh. Approximate range emptiness in constant time and optimal space. In: Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 2015, 769–775, https://doi.org/10.1137/1.9781611973730.52.
-
G. Graefe. Modern B-tree techniques. Foundations and Trends in Databases 3(4) (2011), 203–402, https://doi.org/10.1561/1900000028.
-
T. M. Graf, D. Lemire. Xor filters: faster and smaller than Bloom and cuckoo filters. ACM Journal of Experimental Algorithmics 25 (2020), 1.5, https://doi.org/10.1145/3376122.
-
T. M. Graf, D. Lemire. Binary fuse filters: fast and smaller than xor filters. ACM Journal of Experimental Algorithmics 27 (2022), 1.5, https://doi.org/10.1145/3510449.
-
R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics 17(2) (1969), 416–429, https://doi.org/10.1137/0117039.
-
R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters 1(4) (1972), 132–133, https://doi.org/10.1016/0020-0190(72)90045-2.
-
R. L. Graham, D. E. Knuth, O. Patashnik. Concrete Mathematics: A Foundation for Computer Science. 2nd edition, Addison-Wesley, 1994.
-
F. Grandi. On the analysis of Bloom filters. Information Processing Letters 129 (2018), 35–39, https://doi.org/10.1016/j.ipl.2017.09.004.
-
T. Granlund, P. L. Montgomery. Division by invariant integers using multiplication. Proceedings of the ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation (PLDI), 1994, 61–72, https://doi.org/10.1145/178243.178249.
-
T. Granlund and the GMP development team. GNU MP: The GNU Multiple Precision Arithmetic Library. Version 6.3.0, 2023, https://gmplib.org/gmp-man-6.3.0.pdf.
-
F. Gray. Pulse code communication. U.S. Patent 2,632,058, 1953.
-
D. Gregor, M. Troyer. Boost.MPI. Part of the Boost C++ libraries, https://www.boost.org/libs/mpi.
-
D. Gregor, A. Lumsdaine. Lifting sequential graph algorithms for distributed-memory parallel computation. Proceedings of the 20th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2005), 423–437, 2005, https://doi.org/10.1145/1094811.1094844.
-
R. Grossi, A. Gupta, J. S. Vitter. High-order entropy-compressed text indexes. Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), 841–850, 2003.
-
R. Grossi, G. Ottaviano. Design of practical succinct data structures for large data collections. Proceedings of the 12th Symposium on Experimental Algorithms (SEA 2013), LNCS 7933, 5–17, 2013, https://doi.org/10.1007/978-3-642-38527-8_3.
-
R. Grossi, G. Ottaviano. Fast compressed tries through path decompositions. ACM Journal of Experimental Algorithmics 19 (2015), https://doi.org/10.1145/2656332.
-
G. Guennebaud, B. Jacob, et al. Eigen v3. Software, 2010, https://eigen.tuxfamily.org.
-
S. Gueron, V. Krasnov. Fast quicksort implementation using AVX instructions. The Computer Journal 59(1) (2016), 83–90, https://doi.org/10.1093/comjnl/bxv063.
-
L. J. Guibas, R. Sedgewick. A dichromatic framework for balanced trees. Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS 1978), 1978, 8–21, https://doi.org/10.1109/SFCS.1978.3.
-
D. Gusfield. Efficient methods for multiple sequence alignment with guaranteed error bounds. Bulletin of Mathematical Biology 55(1) (1993), 141–154, https://doi.org/10.1007/BF02460299.
-
D. Gusfield. Algorithms on Strings, Trees and Sequences. Cambridge University Press, 1997, https://doi.org/10.1017/CBO9780511574931.
-
F. G. Gustavson. Two fast algorithms for sparse matrices: multiplication and permuted transposition. ACM Transactions on Mathematical Software 4(3) (1978), 250–269, https://doi.org/10.1145/355791.355796.
-
J. V. Guttag, J. J. Horning. The algebraic specification of abstract data types. Acta Informatica 10(1) (1978), 27–52, https://doi.org/10.1007/BF00260922.
-
A. N. Habermann. Parallel neighbor-sort (or the glory of the induction principle). Technical Report AD-759 248, Carnegie Mellon University, 1972.
-
A. A. Hagberg, D. A. Schult, P. J. Swart. Exploring network structure, dynamics, and function using NetworkX. Proceedings of the 7th Python in Science Conference (SciPy 2008), 2008, 11–15, https://doi.org/10.25080/TCWV9851.
-
T. Hagerup. Sorting and searching on the word RAM. In: 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science 1373, Springer, 1998, 366–398, https://doi.org/10.1007/BFb0028575.
-
S. Halim, F. Halim, S. Effendy. Competitive Programming 4. Books 1 and 2, 2020, https://cpbook.net.
-
P. Halpern. Polymorphic memory resources. ISO/IEC JTC1 SC22 WG21 N3916, 2014, https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3916.pdf.
-
M. A. Hammer, K. Y. Phang, M. Hicks, J. S. Foster. Adapton: composable, demand-driven incremental computation. Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2014), 156–166, 2014, https://doi.org/10.1145/2594291.2594324.
-
K. Hanauer, M. Henzinger, C. Schulz. Recent advances in fully dynamic graph algorithms - a quick reference guide. ACM Journal of Experimental Algorithmics 27 (2022), 1–45, https://doi.org/10.1145/3555806.
-
D. R. Hanson. Fast allocation and deallocation of memory based on object lifetimes. Software: Practice and Experience 20(1) (1990), 5–12, https://doi.org/10.1002/spe.4380200104.
-
D. Harabor, A. Grastien. Online graph pruning for pathfinding on grid maps. Proceedings of the AAAI Conference on Artificial Intelligence 25(1) (2011), 1114–1119, https://doi.org/10.1609/aaai.v25i1.7994.
-
D. Harabor, A. Grastien. Improving jump point search. Proceedings of the International Conference on Automated Planning and Scheduling 24 (2014), 128–135, https://doi.org/10.1609/icaps.v24i1.13633.
-
D. Harel, R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing 13(2) (1984), 338–355, https://doi.org/10.1137/0213024.
-
T. L. Harris. A pragmatic implementation of non-blocking linked-lists. Distributed Computing (DISC 2001), LNCS 2180, Springer, 2001, 300–314, https://doi.org/10.1007/3-540-45414-4_21.
-
P. E. Hart, N. J. Nilsson, B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4(2) (1968), 100–107, https://doi.org/10.1109/TSSC.1968.300136.
-
T. E. Hart, P. E. McKenney, A. D. Brown, J. Walpole. Performance of memory reclamation for lockless synchronization. Journal of Parallel and Distributed Computing 67(12) (2007), 1270–1285, https://doi.org/10.1016/j.jpdc.2007.04.010.
-
R. Hayward, C. McDiarmid. Average case analysis of heap building by repeated insertion. Journal of Algorithms 12(1) (1991), 126–153, https://doi.org/10.1016/0196-6774(91)90027-V.
-
B. R. Heap. Permutations by interchanges. The Computer Journal 6(3) (1963), 293–298, https://doi.org/10.1093/comjnl/6.3.293.
-
M. Held, R. M. Karp. The traveling-salesman problem and minimum spanning trees: part II. Mathematical Programming 1 (1971), 6–25, https://doi.org/10.1007/BF01584070.
-
M. Helmert. The Fast Downward planning system. Journal of Artificial Intelligence Research 26 (2006), 191–246, https://doi.org/10.1613/jair.1705.
-
D. Hendler, N. Shavit. Non-blocking steal-half work queues. Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC), 2002, 280–289, https://doi.org/10.1145/571825.571876.
-
M. Herf. Radix tricks. 2001, http://stereopsis.com/radix.html.
-
M. P. Herlihy, J. M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems 12(3) (1990), 463–492, https://doi.org/10.1145/78969.78972.
-
M. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems 13(1) (1991), 124–149, https://doi.org/10.1145/114005.102808.
-
M. Herlihy, N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008.
-
S. Hermann, H.-P. Lehmann, G. E. Pibiri, P. Sanders, S. Walzer. PHOBIC: perfect hashing with optimized bucket sizes and interleaved coding. 32nd Annual European Symposium on Algorithms (ESA 2024), LIPIcs 308 (2024), 69:1–69:17, https://doi.org/10.4230/LIPIcs.ESA.2024.69.
-
R. Hettinger. More compact dictionaries with faster iteration. Message to the python-dev mailing list, 2012, https://mail.python.org/pipermail/python-dev/2012-December/123028.html.
-
T. N. Hibbard. An empirical study of minimal storage sorting. Communications of the ACM 6(5) (1963), 206–213, https://doi.org/10.1145/366552.366557.
-
C. Hierholzer, C. Wiener. Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen 6(1) (1873), 30–32, https://doi.org/10.1007/BF01442866.
-
N. J. Higham. Exploiting fast matrix multiplication within the level 3 BLAS. ACM Transactions on Mathematical Software 16(4) (1990), 352–368, https://doi.org/10.1145/98267.98290.
-
N. J. Higham. Accuracy and Stability of Numerical Algorithms. 2nd edition, SIAM, 2002, https://doi.org/10.1137/1.9780898718027.
-
P. Hildebrandt, H. Isbitz. Radix exchange: an internal sorting method for digital computers. Journal of the ACM 6(2) (1959), 156–163, https://doi.org/10.1145/320964.320972.
-
H. Hinnant. Combinations and permutations. https://howardhinnant.github.io/combinations.html.
-
K. Hinrichs, J. Nievergelt, P. Schorn. Plane-sweep solves the closest pair problem elegantly. Information Processing Letters 26(5) (1988), 255–261, https://doi.org/10.1016/0020-0190(88)90150-0.
-
Y. Hirai, K. Yamamoto. Balancing weight-balanced trees. Journal of Functional Programming 21(3) (2011), 287–307, https://doi.org/10.1017/S0956796811000104.
-
C. A. R. Hoare. Algorithm 65: Find. Communications of the ACM 4(7) (1961), 321–322, https://doi.org/10.1145/366622.366647.
-
C. A. R. Hoare. Quicksort. The Computer Journal 5(1) (1962), 10–16, https://doi.org/10.1093/comjnl/5.1.10.
-
C. A. R. Hoare. An axiomatic basis for computer programming. Communications of the ACM 12(10) (1969), 576–580, https://doi.org/10.1145/363235.363259.
-
W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58(301) (1963), 13–30, https://doi.org/10.1080/01621459.1963.10500830.
-
T. Hoefler, A. Lumsdaine, W. Rehm. Implementation and performance analysis of non-blocking collective operations for MPI. ACM/IEEE Conference on Supercomputing (SC), 2007, 1–10, https://doi.org/10.1145/1362622.1362692.
-
T. Hoefler, C. Siebert, A. Lumsdaine. Scalable communication protocols for dynamic sparse data exchange. ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2010, 159–168, https://doi.org/10.1145/1693453.1693476.
-
J. Holm, K. de Lichtenberg, M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM 48(4) (2001), 723–760, https://doi.org/10.1145/502090.502095.
-
R. Hood, R. Melville. Real-time queue operations in pure LISP. Information Processing Letters 13(2) (1981), 50–54, https://doi.org/10.1016/0020-0190(81)90030-2.
-
J. E. Hopcroft, J. D. Ullman. Set merging algorithms. SIAM Journal on Computing 2(4) (1973), 294–303, https://doi.org/10.1137/0202024.
-
J. E. Hopcroft, R. M. Karp. An \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing 2(4) (1973), 225–231, https://doi.org/10.1137/0202019.
-
J. E. Hopcroft, R. E. Tarjan. Efficient algorithms for graph manipulation. Communications of the ACM 16(6) (1973), 372–378, https://doi.org/10.1145/362248.362272.
-
J. E. Hopcroft, R. M. Karp. An \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing 2(4) (1973), 225–231, https://doi.org/10.1137/0202019.
-
J. E. Hopcroft, R. E. Tarjan. Efficient planarity testing. Journal of the ACM 21(4) (1974), 549–568, https://doi.org/10.1145/321850.321852.
-
R. N. Horspool. Practical fast searching in strings. Software: Practice and Experience 10(6) (1980), 501–506, https://doi.org/10.1002/spe.4380100608.
-
P. G. Howard, J. S. Vitter. Arithmetic coding for data compression. Proceedings of the IEEE 82(6) (1994), 857–865, https://doi.org/10.1109/5.286189.
-
T. C. Hu, A. C. Tucker. Optimal computer search trees and variable-length alphabetical codes. SIAM Journal on Applied Mathematics 21(4) (1971), 514–532, https://doi.org/10.1137/0121057.
-
T. C. Hu, M. T. Shing. Computation of matrix chain products, part I. SIAM Journal on Computing 11(2) (1982), 362–373, https://doi.org/10.1137/0211028.
-
J. Huang, T. M. Smith, G. M. Henry, R. A. van de Geijn. Strassen's algorithm reloaded. SC16: International Conference for High Performance Computing, Networking, Storage and Analysis, 2016, 690–701, https://doi.org/10.1109/SC.2016.58.
-
T.-W. Huang, D.-L. Lin, C.-X. Lin, Y. Lin. Taskflow: a lightweight parallel and heterogeneous task graph computing system. IEEE Transactions on Parallel and Distributed Systems 33(6) (2022), 1303–1320, https://doi.org/10.1109/TPDS.2021.3104255.
-
S. Huddleston, K. Mehlhorn. A new data structure for representing sorted lists. Acta Informatica 17(2) (1982), 157–184, https://doi.org/10.1007/BF00288968.
-
D. A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE 40(9) (1952), 1098–1101, https://doi.org/10.1109/JRPROC.1952.273898.
-
L. C. K. Hui. Color set size problem with applications to string matching. Proceedings of the 3rd Symposium on Combinatorial Pattern Matching (CPM), LNCS 644, 1992, 230–243, https://doi.org/10.1007/3-540-56024-6_19.
-
T. E. Hull, A. R. Dobell. Random number generators. SIAM Review 4(3) (1962), 230–254, https://doi.org/10.1137/1004061.
-
J. W. Hunt, M. D. McIlroy. An algorithm for differential file comparison. Computing Science Technical Report 41, Bell Laboratories, 1976.
-
F. K. Hwang, S. Lin. A simple algorithm for merging two disjoint linearly ordered sets. SIAM Journal on Computing 1(1) (1972), 31–39, https://doi.org/10.1137/0201004.
-
H. Hyyrö. A bit-vector algorithm for computing Levenshtein and Damerau edit distances. Nordic Journal of Computing 10(1) (2003), 29–39.
-
J. Iacono. Improved upper bounds for pairing heaps. Algorithm Theory - SWAT 2000, LNCS 1851 (2000), 32–45, https://doi.org/10.1007/3-540-44985-X_5.
-
O. H. Ibarra, C. E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM 22(4) (1975), 463–468, https://doi.org/10.1145/321906.321909.
-
IEEE Computer Society. IEEE Standard for Floating-Point Arithmetic. IEEE Std 754-2019, 2019, https://doi.org/10.1109/IEEESTD.2019.8766229.
-
L. Ilie, G. Navarro, L. Tinta. The longest common extension problem revisited and applications to approximate string searching. Journal of Discrete Algorithms 8(4) (2010), 418–428, https://doi.org/10.1016/j.jda.2010.08.004.
-
H. Inoue, K. Taura. SIMD- and cache-friendly algorithm for sorting an array of structures. Proceedings of the VLDB Endowment 8(11) (2015), 1274–1285, https://doi.org/10.14778/2809974.2809988.
-
Intel Corporation. Intel 64 and IA-32 Architectures Optimization Reference Manual. Order number 248966.
-
Intel Corporation. Intel 64 and IA-32 Architectures Optimization Reference Manual. Order number 248966, https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html.
-
E. J. Isaac, R. C. Singleton. Sorting by address calculation. Journal of the ACM 3(3) (1956), 169–174, https://doi.org/10.1145/320831.320834.
-
ISO/IEC. Programming languages, C++. International Standard ISO/IEC 14882:2020, 2020.
-
A. Itai, M. Rodeh. Finding a minimum circuit in a graph. SIAM Journal on Computing 7(4) (1978), 413–423, https://doi.org/10.1137/0207033.
-
H. Itoh, H. Tanaka. An efficient method for in memory construction of suffix arrays. Proceedings of the 6th Symposium on String Processing and Information Retrieval (SPIRE), 1999, 81–88, https://doi.org/10.1109/SPIRE.1999.796581.
-
G. Jacobson. Space-efficient static trees and graphs. Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS 1989), 549–554, 1989, https://doi.org/10.1109/SFCS.1989.63533.
-
G. Jacobson, K.-P. Vo. Heaviest increasing/common subsequence problems. Proceedings of the 3rd Symposium on Combinatorial Pattern Matching, LNCS 644 (1992), 52–66, https://doi.org/10.1007/3-540-56024-6_5.
-
G. Jaeschke. On strong pseudoprimes to several bases. Mathematics of Computation 61(204) (1993), 915–926, https://doi.org/10.1090/S0025-5718-1993-1192971-8.
-
S. V. Jayanti, R. E. Tarjan. Concurrent disjoint set union. Distributed Computing 34(6) (2021), 413–436, https://doi.org/10.1007/s00446-020-00388-x.
-
M. S. Jensen, R. Pagh. Optimality in external memory hashing. Algorithmica 52(3) (2008), 403–411, https://doi.org/10.1007/s00453-007-9155-x.
-
W. W. Johnson, W. E. Story. Notes on the "15" puzzle. American Journal of Mathematics 2(4) (1879), 397–404, https://doi.org/10.2307/2369492.
-
S. M. Johnson. Generation of permutations by adjacent transposition. Mathematics of Computation 17(83) (1963), 282–285, https://doi.org/10.1090/S0025-5718-1963-0159764-2.
-
D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, R. L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing 3(4) (1974), 299–325, https://doi.org/10.1137/0203025.
-
D. B. Johnson. Finding all the elementary circuits of a directed graph. SIAM Journal on Computing 4(1) (1975), 77–84, https://doi.org/10.1137/0204007.
-
D. B. Johnson. Priority queues with update and finding minimum spanning trees. Information Processing Letters 4(3) (1975), 53–57, https://doi.org/10.1016/0020-0190(75)90001-0.
-
D. B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM 24(1) (1977), 1–13, https://doi.org/10.1145/321992.321993.
-
R. Jonker, A. Volgenant. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38(4) (1987), 325–340, https://doi.org/10.1007/BF02278710.
-
KTH. KACTL: KTH Algorithm Competition Template Library. Software, https://github.com/kth-competitive-programming/kactl.
-
A. B. Kahn. Topological sorting of large networks. Communications of the ACM 5(11) (1962), 558–562, https://doi.org/10.1145/368996.369025.
-
H. Kaplan, R. E. Tarjan. Purely functional, real-time deques with catenation. Journal of the ACM 46(5) (1999), 577–603, https://doi.org/10.1145/324133.324139.
-
A. Karatsuba, Yu. Ofman. Multiplication of multidigit numbers on automata. Soviet Physics Doklady 7 (1963), 595–596.
-
J. Kärkkäinen, P. Sanders, S. Burkhardt. Linear work suffix array construction. Journal of the ACM 53(6) (2006), 918–936, https://doi.org/10.1145/1217856.1217858.
-
J. Kärkkäinen, T. Rantala. Engineering radix sort for strings. Proceedings of the 15th International Symposium on String Processing and Information Retrieval (SPIRE), LNCS 5280 (2008), 3–14, https://doi.org/10.1007/978-3-540-89097-3_3.
-
J. Kärkkäinen, G. Manzini, S. J. Puglisi. Permuted longest-common-prefix array. Proceedings of the 20th Symposium on Combinatorial Pattern Matching (CPM), LNCS 5577, 2009, 181–192, https://doi.org/10.1007/978-3-642-02441-2_17.
-
J. Kärkkäinen, D. Kempa, S. J. Puglisi. Linear time Lempel-Ziv factorization: simple, fast, small. Proceedings of the 24th Symposium on Combinatorial Pattern Matching (CPM 2013), LNCS 7922, 189–200, 2013, https://doi.org/10.1007/978-3-642-38905-4_19.
-
N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica 4(4) (1984), 373–395, https://doi.org/10.1007/BF02579150.
-
R. M. Karp. Reducibility among combinatorial problems. In: Complexity of Computer Computations, Plenum Press (1972), 85–103, https://doi.org/10.1007/978-1-4684-2001-2_9.
-
R. M. Karp, Y. Zhang. Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the ACM 40(3) (1993), 765–789, https://doi.org/10.1145/174130.174145.
-
G. Karypis, V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing 20(1) (1998), 359–392, https://doi.org/10.1137/S1064827595287997.
-
A. V. Karzanov. Determining the maximal flow in a network by the method of preflows. Soviet Mathematics Doklady 15 (1974), 434–437.
-
T. Kasai, G. Lee, H. Arimura, S. Arikawa, K. Park. Linear-time longest-common-prefix computation in suffix arrays and its applications. Proceedings of the 12th Symposium on Combinatorial Pattern Matching (CPM), LNCS 2089, 2001, 181–192, https://doi.org/10.1007/3-540-48194-X_17.
-
J. E. Kelley, M. R. Walker. Critical-path planning and scheduling. Proceedings of the Eastern Joint Computer Conference, 1959, 160–173, https://doi.org/10.1145/1460299.1460318.
-
B. W. Kernighan, S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal 49(2) (1970), 291–307, https://doi.org/10.1002/j.1538-7305.1970.tb01770.x.
-
S. Khuller, Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Information and Computation 118(1) (1995), 34–37, https://doi.org/10.1006/inco.1995.1049.
-
P.-V. Khuong, P. Morin. Array layouts for comparison-based searching. ACM Journal of Experimental Algorithmics 22 (2017), 1.3:1–1.3:39, https://doi.org/10.1145/3053370.
-
A. Kiely. Selecting the Golomb parameter in Rice coding. IPN Progress Report 42-159, Jet Propulsion Laboratory, 2004, 1–18, https://ipnpr.jpl.nasa.gov/progress_report/42-159/159E.pdf.
-
C. Kim, J. Chhugani, N. Satish, E. Sedlar, A. D. Nguyen, T. Kaldewey, V. W. Lee, S. A. Brandt, P. Dubey. FAST: fast architecture sensitive tree search on modern CPUs and GPUs. Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, 2010, 339–350, https://doi.org/10.1145/1807167.1807206.
-
K. N. King, B. Smith-Thomas. An optimal algorithm for sink-finding. Information Processing Letters 14(3) (1982), 109–111, https://doi.org/10.1016/0020-0190(82)90064-3.
-
A. Kirsch, M. Mitzenmacher. Less hashing, same performance: building a better Bloom filter. In: Algorithms (ESA 2006), Lecture Notes in Computer Science 4168, Springer, 2006, 456–467, https://doi.org/10.1007/11841036_42.
-
A. Kirsch, M. Mitzenmacher, U. Wieder. More robust hashing: cuckoo hashing with a stash. SIAM Journal on Computing 39(4) (2009), 1543–1561, https://doi.org/10.1137/080728743.
-
P. Kirschenhofer, H. Prodinger. The path length of random skip lists. Acta Informatica 31(8) (1994), 775–792, https://doi.org/10.1007/BF01178735.
-
P. Kirschenhofer, C. Martínez, H. Prodinger. Analysis of an optimized search algorithm for skip lists. Theoretical Computer Science 144(1–2) (1995), 199–220, https://doi.org/10.1016/0304-3975(94)00296-U.
-
K. C. Kiwiel. On Floyd and Rivest's SELECT algorithm. Theoretical Computer Science 347(1–2) (2005), 214–238, https://doi.org/10.1016/j.tcs.2005.06.032.
-
J. Kleinberg, É. Tardos. Algorithm Design. Addison-Wesley, 2005.
-
E. R. Knorr, B. Lemaire, A. Lim, S. Luo, H. Zhang, S. Idreos, M. Mitzenmacher. Proteus: a self-designing range filter. In: Proceedings of the 2022 ACM SIGMOD International Conference on Management of Data, 2022, 1670–1684, https://doi.org/10.1145/3514221.3526167.
-
K. C. Knowlton. A fast storage allocator. Communications of the ACM 8(10) (1965), 623–624, https://doi.org/10.1145/365628.365655.
-
D. E. Knuth. Programs to read (among them DLX1, DLX2 and SSXCC). https://cs.stanford.edu/~knuth/programs.html.
-
D. E. Knuth. Optimum binary search trees. Acta Informatica 1(1) (1971), 14–25, https://doi.org/10.1007/BF00264289.
-
D. E. Knuth. Big Omicron and big Omega and big Theta. ACM SIGACT News 8(2) (1976), 18–24, https://doi.org/10.1145/1008328.1008329.
-
D. E. Knuth, J. H. Morris, V. R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing 6(2) (1977), 323–350, https://doi.org/10.1137/0206024.
-
D. E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms. 3rd edition, Addison-Wesley, 1997.
-
D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. 3rd edition, Addison-Wesley, 1998.
-
D. E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching. 2nd edition, Addison-Wesley, 1998.
-
D. E. Knuth. Dancing links. In: Millennial Perspectives in Computer Science, Palgrave, 2000, 187–214, https://arxiv.org/abs/cs/0011047.
-
D. E. Knuth. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley, 2011.
-
D. E. Knuth. The Art of Computer Programming, Volume 4B: Combinatorial Algorithms, Part 2. Addison-Wesley, 2022.
-
D. E. Knuth. SSXCC: the exact covering with colors on sparse sets. Program, 2023, https://cs.stanford.edu/~knuth/programs.html.
-
S. Koenig, M. Likhachev, D. Furcy. Lifelong Planning A*. Artificial Intelligence 155(1–2) (2004), 93–146, https://doi.org/10.1016/j.artint.2003.12.001.
-
P. Kohli, P. H. S. Torr. Dynamic graph cuts for efficient inference in Markov random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence 29(12) (2007), 2079–2088, https://doi.org/10.1109/TPAMI.2007.1128.
-
D. Kőnig. Gráfok és mátrixok. Matematikai és Fizikai Lapok 38 (1931), 116–119.
-
R. E. Korf. Linear-time disk-based implicit graph search. Journal of the ACM 55(6) (2008), 26:1–26:40, https://doi.org/10.1145/1455248.1455250.
-
S. R. Kosaraju, G. Manzini. Compression of low entropy strings with Lempel-Ziv algorithms. SIAM Journal on Computing 29(3) (2000), 893–911, https://doi.org/10.1137/S0097539797331105.
-
M. Kreutzer, G. Hager, G. Wellein, H. Fehske, A. R. Bishop. A unified sparse matrix data format for efficient general sparse matrix-vector multiplication on modern processors with wide SIMD units. SIAM Journal on Scientific Computing 36(5) (2014), C401–C423, https://doi.org/10.1137/130930352.
-
A. Kristo, K. Vaidya, U. Çetintemel, S. Misra, T. Kraska. The case for a learned sorting algorithm. ACM SIGMOD International Conference on Management of Data (2020), 1001–1016, https://doi.org/10.1145/3318464.3389752.
-
A. Kristo, K. Vaidya, T. Kraska. Defeating duplicates: a re-design of the LearnedSort algorithm. arXiv:2107.03290 (2021), https://doi.org/10.48550/arXiv.2107.03290.
-
J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7(1) (1956), 48–50, https://doi.org/10.1090/S0002-9939-1956-0078686-7.
-
H. W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2(1–2) (1955), 83–97, https://doi.org/10.1002/nav.3800020109.
-
M. Kulukundis. Designing a fast, efficient, cache-friendly hash table, step by step. Talk at CppCon 2017, 2017.
-
S. Kumar, P. Gupta. An incremental algorithm for the maximum flow problem. Journal of Mathematical Modelling and Algorithms 2(1) (2003), 1–16, https://doi.org/10.1023/A:1023607406540.
-
F. Kurpicz. Engineering compact data structures for rank and select queries on bit vectors. Proceedings of the 29th Symposium on String Processing and Information Retrieval (SPIRE 2022), LNCS 13617, 257–272, 2022, https://doi.org/10.1007/978-3-031-20643-6_19.
-
J. Labeit, J. Shun, G. E. Blelloch. Parallel lightweight wavelet tree, suffix array and FM-index construction. Journal of Discrete Algorithms 43 (2017), 2–17, https://doi.org/10.1016/j.jda.2017.04.001.
-
E. Ladan-Mozes, I.-T. A. Lee, D. Vyukov. Location-based memory fences. Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2011, 75–84, https://doi.org/10.1145/1989493.1989503.
-
A. LaMarca, R. Ladner. The influence of caches on the performance of heaps. ACM Journal of Experimental Algorithmics 1 (1996), article 4, https://doi.org/10.1145/235141.235145.
-
L. Lamport. Specifying concurrent program modules. ACM Transactions on Programming Languages and Systems 5(2) (1983), 190–222, https://doi.org/10.1145/69624.357207.
-
G. M. Landau, U. Vishkin. Efficient string matching with k mismatches. Theoretical Computer Science 43 (1986), 239–249, https://doi.org/10.1016/0304-3975(86)90178-7.
-
G. M. Landau, U. Vishkin. Fast parallel and serial approximate string matching. Journal of Algorithms 10(2) (1989), 157–169, https://doi.org/10.1016/0196-6774(89)90010-2.
-
D. H. Larkin, S. Sen, R. E. Tarjan. A back-to-basics empirical study of priority queues. Proceedings of the 16th Workshop on Algorithm Engineering and Experiments (ALENEX), 2014, 61–72, https://doi.org/10.1137/1.9781611973198.7.
-
L. L. Larmore, D. S. Hirschberg. A fast algorithm for optimal length-limited Huffman codes. Journal of the ACM 37(3) (1990), 464–473, https://doi.org/10.1145/79147.79150.
-
N. J. Larsson, K. Sadakane. Faster suffix sorting. Theoretical Computer Science 387(3) (2007), 258–272, https://doi.org/10.1016/j.tcs.2007.07.017.
-
E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.
-
E. L. Lawler. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Annals of Discrete Mathematics 2 (1978), 75–90, https://doi.org/10.1016/S0167-5060(08)70323-6.
-
M. D. Laws, J. Bliven, K. Conklin, E. Laalai, S. McCauley, Z. S. Sturdevant. SPIDER: improved succinct rank and select performance. Proceedings of the 22nd Symposium on Experimental Algorithms (SEA 2024), LIPIcs 301, article 21, 2024, https://doi.org/10.4230/LIPIcs.SEA.2024.21.
-
N. M. Lê, A. Pop, A. Cohen, F. Zappa Nardelli. Correct and efficient work-stealing for weak memory models. Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2013, 69–80, https://doi.org/10.1145/2442516.2442524.
-
T. Lecroq. Fast exact string matching algorithms. Information Processing Letters 102(6) (2007), 229–235, https://doi.org/10.1016/j.ipl.2007.01.002.
-
C. Y. Lee. An algorithm for path connections and its applications. IRE Transactions on Electronic Computers EC-10(3) (1961), 346–365, https://doi.org/10.1109/TEC.1961.5219222.
-
P. P. C. Lee, T. Bu, G. Chandranmenon. A lock-free, cache-efficient multi-core synchronization mechanism for line-rate network traffic monitoring. IEEE International Symposium on Parallel and Distributed Processing (IPDPS), 2010, 1–12, https://doi.org/10.1109/IPDPS.2010.5470368.
-
E. Lehman, F. T. Leighton, A. R. Meyer. Mathematics for Computer Science. Massachusetts Institute of Technology, revised 2018, https://courses.csail.mit.edu/6.042/spring18/mcs.pdf.
-
H.-P. Lehmann, P. Sanders, S. Walzer, J. Ziegler. Combined search and encoding for seeds, with an application to minimal perfect hashing. 33rd Annual European Symposium on Algorithms (ESA 2025), LIPIcs 351 (2025), 109:1–109:18, https://doi.org/10.4230/LIPIcs.ESA.2025.109.
-
D. H. Lehmer. Euclid's algorithm for large numbers. The American Mathematical Monthly 45(4) (1938), 227–233, https://doi.org/10.1080/00029890.1938.11990797.
-
T. Leighton. Notes on better master theorems for divide-and-conquer recurrences. Lecture notes, MIT, 1996.
-
D. Leijen, B. Zorn, L. de Moura. Mimalloc: free list sharding in action. Programming Languages and Systems (APLAS 2019), Lecture Notes in Computer Science 11893, Springer, 2019, 244–265, https://doi.org/10.1007/978-3-030-34175-6_13.
-
V. Leis, A. Kemper, T. Neumann. The adaptive radix tree: ARTful indexing for main-memory databases. Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE 2013), 2013, 38–49, https://doi.org/10.1109/ICDE.2013.6544812.
-
D. Lemire, L. Boytsov. Decoding billions of integers per second through vectorization. Software: Practice and Experience 45(1) (2015), 1–29, https://doi.org/10.1002/spe.2203.
-
D. Lemire, L. Boytsov, N. Kurz. SIMD compression and the intersection of sorted integers. Software: Practice and Experience 46(6) (2016), 723–749, https://doi.org/10.1002/spe.2326.
-
D. Lemire, O. Kaser, N. Kurz, L. Deri, C. O'Hara, F. Saint-Jacques, G. Ssi-Yan-Kai. Roaring bitmaps: implementation of an optimized software library. Software: Practice and Experience 48(4) (2018), 867–895, https://doi.org/10.1002/spe.2560.
-
D. Lemire, N. Kurz, C. Rupp. Stream VByte: faster byte-oriented integer compression. Information Processing Letters 130 (2018), 1–6, https://doi.org/10.1016/j.ipl.2017.09.011.
-
D. Lemire. Fast random integer generation in an interval. ACM Transactions on Modeling and Computer Simulation 29(1) (2019), 3:1–3:12, https://doi.org/10.1145/3230636.
-
P. H. W. Leong, G. Zhang, D.-U. Lee, W. Luk, J. D. Villasenor. A comment on the implementation of the ziggurat method. Journal of Statistical Software 12(7) (2005), https://doi.org/10.18637/jss.v012.i07.
-
V. I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady 10(8) (1966), 707–710.
-
L. A. Levin. Universal sequential search problems. Problems of Information Transmission 9(3) (1973), 265–266.
-
K.-H. Li. Reservoir-sampling algorithms of time complexity \(O( n ( 1 + \log( N / n ) ) )\). ACM Transactions on Mathematical Software 20(4) (1994), 481–493, https://doi.org/10.1145/198429.198435.
-
X. Li, D. G. Andersen, M. Kaminsky, M. J. Freedman. Algorithmic improvements for fast concurrent cuckoo hashing. Proceedings of the 9th European Conference on Computer Systems (EuroSys), 2014, article 27, https://doi.org/10.1145/2592798.2592820.
-
P. Lietar, T. Butler, S. Clebsch, S. Drossopoulou, J. Franco, M. J. Parkinson, A. Shamis, C. M. Wintersteiger, D. Chisnall. snmalloc: a message passing allocator. Proceedings of the 2019 ACM SIGPLAN International Symposium on Memory Management (ISMM 2019), 2019, 122–135, https://doi.org/10.1145/3315573.3329980.
-
A. Limasset, G. Rizk, R. Chikhi, P. Peterlongo. Fast and scalable minimal perfect hashing for massive key sets. 16th International Symposium on Experimental Algorithms (SEA 2017), LIPIcs 75 (2017), 25:1–25:16, https://doi.org/10.4230/LIPIcs.SEA.2017.25.
-
S. Lin. Computer solutions of the traveling salesman problem. Bell System Technical Journal 44(10) (1965), 2245–2269, https://doi.org/10.1002/j.1538-7305.1965.tb04146.x.
-
Y.-L. Lin, T. Jiang, K.-M. Chao. Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. Journal of Computer and System Sciences 65(3) (2002), 570–586, https://doi.org/10.1016/S0022-0000(02)00010-7.
-
J. Lindén, B. Jonsson. A skiplist-based concurrent priority queue with minimal memory contention. Principles of Distributed Systems (OPODIS 2013), LNCS 8304, Springer, 2013, 206–220, https://doi.org/10.1007/978-3-319-03850-6_15.
-
B. Liskov, S. Zilles. Programming with abstract data types. ACM SIGPLAN Notices 9(4) (1974), 50–59, https://doi.org/10.1145/942572.807045.
-
J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel. An algorithm for the traveling salesman problem. Operations Research 11(6) (1963), 972–989, https://doi.org/10.1287/opre.11.6.972.
-
J. M. López Muñoz. Inside boost::unordered_flat_map. 2022, https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html.
-
I. Lotan, N. Shavit. Skiplist-based concurrent priority queues. Proceedings of the 14th International Parallel and Distributed Processing Symposium (IPDPS 2000), 263–268, https://doi.org/10.1109/IPDPS.2000.845994.
-
M. Luby, A. Sinclair, D. Zuckerman. Optimal speedup of Las Vegas algorithms. Information Processing Letters 47(4) (1993), 173–180, https://doi.org/10.1016/0020-0190(93)90029-9.
-
G. S. Lueker. A data structure for orthogonal range queries. Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS), 1978, 28–34, https://doi.org/10.1109/SFCS.1978.1.
-
J. Łukasiewicz. Elementy logiki matematycznej. Wydawnictwo Koła Matematyczno-Fizycznego Słuchaczy Uniwersytetu Warszawskiego, Warszawa, 1929.
-
S. Luo, S. Chatterjee, R. Ketsetsidis, N. Dayan, W. Qin, S. Idreos. Rosetta: a robust space-time optimized range filter for key-value stores. In: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, 2020, 2071–2086, https://doi.org/10.1145/3318464.3389731.
-
D. Maier. The complexity of some problems on subsequences and supersequences. Journal of the ACM 25(2) (1978), 322–336, https://doi.org/10.1145/322063.322075.
-
T. Maier, P. Sanders, R. Dementiev. Concurrent hash tables: fast and general(?)! ACM Transactions on Parallel Computing 5(4) (2019), article 16, https://doi.org/10.1145/3309206.
-
B. S. Majewski, N. C. Wormald, G. Havas, Z. J. Czech. A family of perfect hashing methods. The Computer Journal 39(6) (1996), 547–554, https://doi.org/10.1093/comjnl/39.6.547.
-
V. Mäkinen, G. Navarro. Succinct suffix arrays based on run-length encoding. Proceedings of the 16th Symposium on Combinatorial Pattern Matching (CPM 2005), LNCS 3537, 45–56, 2005, https://doi.org/10.1007/11496656_5.
-
V. M. Malhotra, M. P. Kumar, S. N. Maheshwari. An \(O( |V|^3 )\) algorithm for finding maximum flows in networks. Information Processing Letters 7(6) (1978), 277–278, https://doi.org/10.1016/0020-0190(78)90016-9.
-
G. Manacher. A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string. Journal of the ACM 22(3) (1975), 346–351, https://doi.org/10.1145/321892.321896.
-
U. Manber, G. Myers. Suffix arrays: a new method for on-line string searches. SIAM Journal on Computing 22(5) (1993), 935–948, https://doi.org/10.1137/0222058.
-
H. Mannila, E. Ukkonen. The set union problem with backtracking. Automata, Languages and Programming (ICALP 1986), Lecture Notes in Computer Science 226, Springer, 1986, 236–243, https://doi.org/10.1007/3-540-16761-7_73.
-
A. Mansfield. On the computational complexity of a merge recognition problem. Discrete Applied Mathematics 5(1) (1983), 119–122, https://doi.org/10.1016/0166-218X(83)90021-5.
-
G. Manzini. An analysis of the Burrows-Wheeler transform. Journal of the ACM 48(3) (2001), 407–430, https://doi.org/10.1145/382780.382782.
-
S. Marco-Sola, J. C. Moure, M. Moreto, A. Espinosa. Fast gap-affine pairwise alignment using the wavefront algorithm. Bioinformatics 37(4) (2021), 456–463, https://doi.org/10.1093/bioinformatics/btaa777.
-
J. P. Marques-Silva, K. A. Sakallah. GRASP: a search algorithm for propositional satisfiability. IEEE Transactions on Computers 48(5) (1999), 506–521, https://doi.org/10.1109/12.769433.
-
G. Marsaglia, W. W. Tsang. The ziggurat method for generating random variables. Journal of Statistical Software 5(8) (2000), https://doi.org/10.18637/jss.v005.i08.
-
S. Martello, P. Toth. Knapsack Problems: Algorithms and Computer Implementations. Wiley, 1990.
-
G. N. N. Martin. Range encoding: an algorithm for removing redundancy from a digitised message. Video & Data Recording Conference, Southampton, 1979.
-
C. Martínez, S. Roura. Randomized binary search trees. Journal of the ACM 45(2) (1998), 288–323, https://doi.org/10.1145/274787.274812.
-
M. A. Martínez-Prieto, N. R. Brisaboa, R. Cánovas, F. Claude, G. Navarro. Practical compressed string dictionaries. Information Systems 56 (2016), 73–108, https://doi.org/10.1016/j.is.2015.08.008.
-
M. Masmano, I. Ripoll, A. Crespo, J. Real. TLSF: a new dynamic memory allocator for real-time systems. Proceedings of the 16th Euromicro Conference on Real-Time Systems (ECRTS 2004), 2004, 79–88, https://doi.org/10.1109/EMRTS.2004.1311009.
-
P. Massart. The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality. The Annals of Probability 18(3) (1990), 1269–1283, https://doi.org/10.1214/aop/1176990746.
-
F. Mattern. Algorithms for distributed termination detection. Distributed Computing 2(3) (1987), 161–175, https://doi.org/10.1007/BF01782776.
-
F. Mattern. Global quiescence detection based on credit distribution and recovery. Information Processing Letters 30(4) (1989), 195–200, https://doi.org/10.1016/0020-0190(89)90212-3.
-
E. M. McCreight. A space-economical suffix tree construction algorithm. Journal of the ACM 23(2) (1976), 262–272, https://doi.org/10.1145/321941.321946.
-
E. M. McCreight. Priority search trees. SIAM Journal on Computing 14(2) (1985), 257–276, https://doi.org/10.1137/0214021.
-
P. M. McIlroy. Optimistic sorting and information theoretic complexity. Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1993, 467–474.
-
P. M. McIlroy, K. Bostic, M. D. McIlroy. Engineering radix sort. Computing Systems 6(1) (1993), 5–27.
-
P. M. McIlroy. Optimistic sorting and information theoretic complexity. Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1993, 467–474.
-
P. M. McIlroy, K. Bostic, M. D. McIlroy. Engineering radix sort. Computing Systems 6(1) (1993), 5–27.
-
M. D. McIlroy. A killer adversary for quicksort. Software: Practice and Experience 29(4) (1999), 341–344, https://doi.org/10.1002/(SICI)1097-024X(19990410)29:4%3C341::AID-SPE237%3E3.0.CO;2-R.
-
R. McNaughton. Scheduling with deadlines and loss functions. Management Science 6(1) (1959), 1–12, https://doi.org/10.1287/mnsc.6.1.1.
-
K. Mehlhorn. Nearly optimal binary search trees. Acta Informatica 5(4) (1975), 287–295, https://doi.org/10.1007/BF00264563.
-
K. Mehlhorn, S. Näher. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, 1999.
-
J. M. Mellor-Crummey, M. L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems 9(1) (1991), 21–65, https://doi.org/10.1145/103727.103729.
-
K. Menger. Zur allgemeinen Kurventheorie. Fundamenta Mathematicae 10 (1927), 96–115, https://doi.org/10.4064/fm-10-1-96-115.
-
D. Merrill, M. Garland. Single-pass parallel prefix scan with decoupled look-back. Technical Report NVR-2016-002, NVIDIA, 2016.
-
D. Merrill, M. Garland. Merge-based parallel sparse matrix-vector multiplication. International Conference for High Performance Computing, Networking, Storage and Analysis (SC) (2016), 678–689, https://doi.org/10.1109/SC.2016.57.
-
B. Meyer. Applying "design by contract". Computer 25(10) (1992), 40–51, https://doi.org/10.1109/2.161279.
-
B. Meyer. Object-Oriented Software Construction. 2nd edition, Prentice Hall, 1997.
-
U. Meyer, P. Sanders. \(\Delta\)-stepping: a parallelizable shortest path algorithm. Journal of Algorithms 49(1) (2003), 114–152, https://doi.org/10.1016/S0196-6774(03)00076-2.
-
S. Micali, V. V. Vazirani. An \(O( \sqrt{\lvert V \rvert} \, \lvert E \rvert )\) algorithm for finding maximum matching in general graphs. Proceedings of the 21st Annual Symposium on Foundations of Computer Science (FOCS), 1980, 17–27, https://doi.org/10.1109/SFCS.1980.12.
-
G. L. Miller. Riemann's hypothesis and tests for primality. Journal of Computer and System Sciences 13(3) (1976), 300–317, https://doi.org/10.1016/S0022-0000(76)80043-8.
-
G. A. Mills-Tettey, A. Stentz, M. B. Dias. The dynamic Hungarian algorithm for the assignment problem with changing costs. Technical Report CMU-RI-TR-07-27, Robotics Institute, Carnegie Mellon University, 2007.
-
L. Mirsky. A dual of Dilworth's decomposition theorem. The American Mathematical Monthly 78(8) (1971), 876–877, https://doi.org/10.2307/2316481.
-
M. Mitzenmacher. Compressed Bloom filters. IEEE/ACM Transactions on Networking 10(5) (2002), 604–612, https://doi.org/10.1109/TNET.2002.803864.
-
A. Moffat. Implementing the PPM data compression scheme. IEEE Transactions on Communications 38(11) (1990), 1917–1921, https://doi.org/10.1109/26.61469.
-
A. Moffat, A. Turpin. On the implementation of minimum redundancy prefix codes. IEEE Transactions on Communications 45(10) (1997), 1200–1207, https://doi.org/10.1109/26.634683.
-
A. Moffat, L. Stuiver. Binary interpolative coding for effective index compression. Information Retrieval 3(1) (2000), 25–47, https://doi.org/10.1023/A:1013002601898.
-
P. L. Montgomery. Modular multiplication without trial division. Mathematics of Computation 44(170) (1985), 519–521, https://doi.org/10.1090/S0025-5718-1985-0777282-X.
-
A. Montresor. Algoritmi e Strutture Dati. 2025, CC BY-NC 4.0, https://algoritmicamente.it/materiali/libro/book.pdf.
-
E. F. Moore. The shortest path through a maze. Proceedings of an International Symposium on the Theory of Switching, Part II, Harvard University Press, 1959, 285–292.
-
P. Morin. Open Data Structures (in C++). Edition 0.1Gβ, https://opendatastructures.org/ods-cpp.pdf.
-
P. Morin. Open Data Structures: An Introduction. Athabasca University Press, 2013, https://doi.org/10.15215/aupress/9781927356388.01.
-
R. Morris. Scatter storage techniques. Communications of the ACM 11(1) (1968), 38–44, https://doi.org/10.1145/362851.362882.
-
D. R. Morrison. PATRICIA: practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM 15(4) (1968), 514–534, https://doi.org/10.1145/321479.321481.
-
G. M. Morton. A computer oriented geodetic data base and a new technique in file sequencing. Technical report, IBM, Ottawa, 1966.
-
M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang, S. Malik. Chaff: engineering an efficient SAT solver. In: Proceedings of the 38th Design Automation Conference (DAC 2001), ACM, 2001, 530–535, https://doi.org/10.1145/378239.379017.
-
R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995, https://doi.org/10.1017/CBO9780511814075.
-
Message Passing Interface Forum. MPI: A Message-Passing Interface Standard. Version 4.1, 2023, https://www.mpi-forum.org/docs/.
-
W. Mula. SIMD-friendly algorithms for substring searching. 2016, http://0x80.pl/notesen/2016-11-28-simd-strfind.html.
-
W. Muła, N. Kurz, D. Lemire. Faster population counts using AVX2 instructions. The Computer Journal 61(1) (2018), 111–120, https://doi.org/10.1093/comjnl/bxx046.
-
I. Müller, P. Sanders, R. Schulze, W. Zhou. Retrieval and perfect hashing using fingerprinting. Proceedings of the 13th International Symposium on Experimental Algorithms (SEA 2014), LNCS 8504 (2014), 138–149, https://doi.org/10.1007/978-3-319-07959-2_12.
-
J. Munkres. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics 5(1) (1957), 32–38, https://doi.org/10.1137/0105003.
-
J. I. Munro, T. Papadakis, R. Sedgewick. Deterministic skip lists. Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms (SODA 1992), 1992, 367–375.
-
J. I. Munro, V. Raman. Succinct representation of balanced parentheses and static trees. SIAM Journal on Computing 31(3) (2001), 762–776, https://doi.org/10.1137/S0097539799364092.
-
J. I. Munro, S. Wild. Nearly-optimal mergesorts: fast, practical sorting methods that optimally adapt to existing runs. 26th Annual European Symposium on Algorithms (ESA 2018), LIPIcs 112 (2018), 63:1–63:16, https://doi.org/10.4230/LIPIcs.ESA.2018.63.
-
D. R. Musser, A. A. Stepanov. Generic programming. In: Symbolic and Algebraic Computation (ISSAC '88), Lecture Notes in Computer Science 358, Springer, 1989, 13–25, https://doi.org/10.1007/3-540-51084-2_2.
-
D. R. Musser. Introspective sorting and selection algorithms. Software: Practice and Experience 27(8) (1997), 983–993, https://doi.org/10.1002/(SICI)1097-024X(199708)27:8%3C983::AID-SPE117%3E3.0.CO;2-%23.
-
E. W. Myers. An O(ND) difference algorithm and its variations. Algorithmica 1(1–4) (1986), 251–266, https://doi.org/10.1007/BF01840446.
-
G. Myers. A fast bit-vector algorithm for approximate string matching based on dynamic programming. Journal of the ACM 46(3) (1999), 395–415, https://doi.org/10.1145/316542.316550.
-
J. Navarro, S. Iyer, P. Druschel, A. Cox. Practical, transparent operating system support for superpages. ACM SIGOPS Operating Systems Review 36(SI) (2002), 89–104 (OSDI 2002), https://doi.org/10.1145/844128.844138.
-
G. Navarro, V. Mäkinen. Compressed full-text indexes. ACM Computing Surveys 39(1) (2007), 2, https://doi.org/10.1145/1216370.1216372.
-
G. Navarro, R. Paredes. On sorting, heaps, and minimum spanning trees. Algorithmica 57(4) (2010), 585–620, https://doi.org/10.1007/s00453-010-9400-6.
-
G. Navarro, E. Providel. Fast, small, simple rank/select on bitmaps. Proceedings of the 11th International Symposium on Experimental Algorithms (SEA 2012), LNCS 7276 (2012), 295–306, https://doi.org/10.1007/978-3-642-30850-5_26.
-
G. Navarro, K. Sadakane. Fully functional static and dynamic succinct trees. ACM Transactions on Algorithms 10(3) (2014), 16, https://doi.org/10.1145/2601073.
-
G. Navarro. Wavelet trees for all. Journal of Discrete Algorithms 25 (2014), 2–20, https://doi.org/10.1016/j.jda.2013.07.004.
-
G. Navarro. Compact Data Structures: A Practical Approach. Cambridge University Press, 2016, https://doi.org/10.1017/CBO9781316588284.
-
G. Navarro. Indexing highly repetitive string collections, part II: compressed indexes. ACM Computing Surveys 54(2) (2021), 26, https://doi.org/10.1145/3432999.
-
S. B. Needleman, C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology 48(3) (1970), 443–453, https://doi.org/10.1016/0022-2836(70)90057-4.
-
A. Neumaier. Rundungsfehleranalyse einiger Verfahren zur Summation endlicher Summen. Zeitschrift für Angewandte Mathematik und Mechanik 54(1) (1974), 39–51, https://doi.org/10.1002/zamm.19740540106.
-
E. Niebler. Suggested design for customization points. ISO/IEC JTC1 SC22 WG21 N4381, 2015, https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4381.html.
-
J. Nievergelt, E. M. Reingold. Binary search trees of bounded balance. SIAM Journal on Computing 2(1) (1973), 33–43, https://doi.org/10.1137/0202005.
-
R. Nikolaev. A scalable, portable, and memory-efficient lock-free FIFO queue. 33rd International Symposium on Distributed Computing (DISC), LIPIcs 146 (2019), 28:1–28:16, https://doi.org/10.4230/LIPIcs.DISC.2019.28.
-
T. Nishimoto, Y. Tabei. Optimal-time queries on BWT-runs compressed indexes. Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), LIPIcs 198, article 101, 2021, https://doi.org/10.4230/LIPIcs.ICALP.2021.101.
-
M. H. Nodine, J. S. Vitter. Greed Sort: optimal deterministic sorting on parallel disks. Journal of the ACM 42(4) (1995), 919–933, https://doi.org/10.1145/210332.210343.
-
G. Nong, S. Zhang, W. H. Chan. Two efficient algorithms for linear time suffix array construction. IEEE Transactions on Computers 60(10) (2011), 1471–1484, https://doi.org/10.1109/TC.2010.188.
-
D. Okanohara, K. Sadakane. Practical entropy-compressed rank/select dictionary. Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX 2007), 60–70, 2007, https://doi.org/10.1137/1.9781611972870.6.
-
C. Okasaki. Simple and efficient purely functional queues and deques. Journal of Functional Programming 5(4) (1995), 583–592, https://doi.org/10.1017/S0956796800001489.
-
P. O'Neil, E. Cheng, D. Gawlick, E. O'Neil. The log-structured merge-tree (LSM-tree). Acta Informatica 33(4) (1996), 351–385, https://doi.org/10.1007/s002360050048.
-
OpenMP Architecture Review Board. OpenMP Application Programming Interface, version 5.2. 2021, https://www.openmp.org/spec-html/5.2/.
-
J. O'Rourke. An on-line algorithm for fitting straight lines between data ranges. Communications of the ACM 24(9) (1981), 574–578, https://doi.org/10.1145/358746.358758.
-
J. O'Rourke. Computational Geometry in C. 2nd edition, Cambridge University Press, 1998, https://doi.org/10.1017/CBO9780511804120.
-
V. Osipov, P. Sanders, J. Singler. The filter-Kruskal minimum spanning tree algorithm. Workshop on Algorithm Engineering and Experiments (ALENEX) (2009), 52–61, https://doi.org/10.1137/1.9781611972894.5.
-
G. Ottaviano, R. Venturini. Partitioned Elias-Fano indexes. Proceedings of the 37th ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2014), 273–282, 2014, https://doi.org/10.1145/2600428.2609615.
-
M. H. Overmars, J. van Leeuwen. Dynamic multi-dimensional data structures based on quad- and k-d trees. Acta Informatica 17(3) (1982), 267–285, https://doi.org/10.1007/BF00264354.
-
M. H. Overmars. The Design of Dynamic Data Structures. LNCS 156, Springer, 1983, https://doi.org/10.1007/BFb0014927.
-
R. Pagh, F. F. Rodler. Cuckoo hashing. Journal of Algorithms 51(2) (2004), 122–144, https://doi.org/10.1016/j.jalgor.2003.12.002.
-
P. Pandey, M. A. Bender, R. Johnson. A fast x86 implementation of select. arXiv:1706.00990, 2017, https://arxiv.org/abs/1706.00990.
-
T. Papadakis, J. I. Munro, P. V. Poblete. Average search and update costs in skip lists. BIT 32(2) (1992), 316–332, https://doi.org/10.1007/BF01994884.
-
U. Pape. Implementation and efficiency of Moore-algorithms for the shortest route problem. Mathematical Programming 7(1) (1974), 212–222, https://doi.org/10.1007/BF01585517.
-
R. Paredes, G. Navarro. Optimal incremental sorting. Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX), 2006, 171–182, https://doi.org/10.1137/1.9781611972863.16.
-
S. K. Park, K. W. Miller. Random number generators: good ones are hard to find. Communications of the ACM 31(10) (1988), 1192–1201, https://doi.org/10.1145/63039.63042.
-
D. L. Parnas. On the criteria to be used in decomposing systems into modules. Communications of the ACM 15(12) (1972), 1053–1058, https://doi.org/10.1145/361598.361623.
-
Apache Parquet. Split block Bloom filter. Specification of the format Parquet, 2019, https://github.com/apache/parquet-format/blob/master/BloomFilter.md.
-
M. Pătrașcu, M. Thorup. Randomization does not help searching predecessors. Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 2007, 555–564.
-
M. Pătrașcu, M. Thorup. The power of simple tabulation hashing. Journal of the ACM 59(3) (2012), article 14, https://doi.org/10.1145/2220357.2220361.
-
M. M. A. Patwary, J. R. S. Blair, F. Manne. Experiments on union-find algorithms for the disjoint-set data structure. Experimental Algorithms (SEA 2010), Lecture Notes in Computer Science 6049, Springer, 2010, 411–423, https://doi.org/10.1007/978-3-642-13193-6_35.
-
D. J. Pearce. A space-efficient algorithm for finding strongly connected components. Information Processing Letters 116(1) (2016), 47–52, https://doi.org/10.1016/j.ipl.2015.08.010.
-
J. Pearl, J. H. Kim. Studies in semi-admissible heuristics. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-4(4) (1982), 392–399, https://doi.org/10.1109/TPAMI.1982.4767270.
-
R. Peng, B. Sandlund, D. D. Sleator. Optimal offline dynamic 2,3-edge/vertex connectivity. Algorithms and Data Structures (WADS 2019), Lecture Notes in Computer Science 11646, Springer, 2019, 553–565, https://doi.org/10.1007/978-3-030-24766-9_40.
-
Y. Perl, A. Itai, H. Avni. Interpolation search: a log log N search. Communications of the ACM 21(7) (1978), 550–553, https://doi.org/10.1145/359545.359557.
-
A. J. Perlis, C. Thornton. Symbol manipulation by threaded lists. Communications of the ACM 3(4) (1960), 195–204, https://doi.org/10.1145/367177.367202.
-
T. Peters. listsort.txt. The documentation of the sort of CPython, 2002, https://github.com/python/cpython/blob/main/Objects/listsort.txt.
-
O. R. L. Peters. Pattern-defeating quicksort. arXiv:2106.05123, 2021, https://doi.org/10.48550/arXiv.2106.05123.
-
W. W. Peterson. Addressing for random-access storage. IBM Journal of Research and Development 1(2) (1957), 130–146, https://doi.org/10.1147/rd.12.0130.
-
S. Pettie. Towards a final analysis of pairing heaps. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005, 174–183, https://doi.org/10.1109/SFCS.2005.75.
-
G. E. Pibiri, R. Venturini. Techniques for inverted index compression. ACM Computing Surveys 53(6) (2020), 125, https://doi.org/10.1145/3415148.
-
G. E. Pibiri, R. Trani. PTHash: revisiting FCH minimal perfect hashing. Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2021), 2021, 1339–1348, https://doi.org/10.1145/3404835.3462849.
-
G. E. Pibiri, R. Trani. Parallel and external-memory construction of minimal perfect hash functions with PTHash. IEEE Transactions on Knowledge and Data Engineering 36(3) (2024), 1249–1259, https://doi.org/10.1109/TKDE.2023.3303341.
-
K. Pipatsrisawat, A. Darwiche. A lightweight component caching scheme for satisfiability solvers. In: Theory and Applications of Satisfiability Testing (SAT 2007), Lecture Notes in Computer Science 4501, Springer, 2007, 294–299, https://doi.org/10.1007/978-3-540-72788-0_28.
-
I. Pohl. A sorting problem and its complexity. Communications of the ACM 15(6) (1972), 462–464, https://doi.org/10.1145/361405.361423.
-
J. M. Pollard. The fast Fourier transform in a finite field. Mathematics of Computation 25(114) (1971), 365–374, https://doi.org/10.1090/S0025-5718-1971-0301966-0.
-
J. M. Pollard. A Monte Carlo method for factorization. BIT 15(3) (1975), 331–334, https://doi.org/10.1007/BF01933667.
-
O. Polychroniou, K. A. Ross. A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, 2014, 755–766, https://doi.org/10.1145/2588555.2610522.
-
A. Postnikova, N. Koval, G. Nadiradze, D. Alistarh. Multi-queues can be state-of-the-art priority schedulers. Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022, 353–367, https://doi.org/10.1145/3503221.3508432.
-
V. R. Pratt. Shellsort and sorting networks. PhD thesis, Stanford University, 1971.
-
F. P. Preparata, M. I. Shamos. Computational Geometry: An Introduction. Springer, 1985, https://doi.org/10.1007/978-1-4612-1098-6.
-
B. Priest, T. Steil, G. Sanders, R. Pearce. You've Got Mail (YGM): building missing asynchronous communication primitives. IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), 2019, 221–230, https://doi.org/10.1109/IPDPSW.2019.00045.
-
R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal 36(6) (1957), 1389–1401, https://doi.org/10.1002/j.1538-7305.1957.tb01515.x.
-
W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM 33(6) (1990), 668–676, https://doi.org/10.1145/78973.78977.
-
W. Pugh. A skip list cookbook. Technical Report CS-TR-2286.1, University of Maryland, 1990.
-
S. J. Puglisi, W. F. Smyth, A. H. Turpin. A taxonomy of suffix array construction algorithms. ACM Computing Surveys 39(2) (2007), 4, https://doi.org/10.1145/1242471.1242472.
-
C. Purcell, T. Harris. Non-blocking hashtables with open addressing. Distributed Computing, DISC 2005, LNCS 3724 (2005), 108–121, https://doi.org/10.1007/11561927_10.
-
F. Putze, P. Sanders, J. Singler. Cache-, hash-, and space-efficient Bloom filters. ACM Journal of Experimental Algorithmics 14 (2009), 4.4, https://doi.org/10.1145/1498698.1594230.
-
M. O. Rabin. Probabilistic algorithms. In J. F. Traub (ed.), Algorithms and Complexity: New Directions and Recent Results, Academic Press, 1976, 21–39.
-
M. O. Rabin. Probabilistic algorithm for testing primality. Journal of Number Theory 12(1) (1980), 128–138, https://doi.org/10.1016/0022-314X(80)90084-0.
-
M. O. Rabin. Fingerprinting by random polynomials. Technical Report TR-15-81, Center for Research in Computing Technology, Harvard University, 1981.
-
M. O. Rabin, J. O. Shallit. Randomized algorithms in number theory. Communications on Pure and Applied Mathematics 39(S1) (1986), S239–S256, https://doi.org/10.1002/cpa.3160390713.
-
G. Ramalingam, T. Reps. An incremental algorithm for a generalization of the shortest-path problem. Journal of Algorithms 21(2) (1996), 267–305, https://doi.org/10.1006/jagm.1996.0046.
-
G. Ramalingam, T. Reps. On the computational complexity of dynamic graph problems. Theoretical Computer Science 158(1–2) (1996), 233–277, https://doi.org/10.1016/0304-3975(95)00079-8.
-
R. Raman, V. Raman, S. S. Rao. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms 3(4) (2007), 43, https://doi.org/10.1145/1290672.1290680.
-
J. Rao, K. A. Ross. Cache conscious indexing for decision-support in main memory. Proceedings of the 25th International Conference on Very Large Data Bases (VLDB 1999), 1999, 78–89.
-
J. Rao, K. A. Ross. Making B+-trees cache conscious in main memory. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data (SIGMOD 2000), 2000, 475–486, https://doi.org/10.1145/342009.335449.
-
D. P. Reed, R. K. Kanodia. Synchronization with eventcounts and sequencers. Communications of the ACM 22(2) (1979), 115–123, https://doi.org/10.1145/359060.359076.
-
B. Reed. The height of a random binary search tree. Journal of the ACM 50(3) (2003), 306–332, https://doi.org/10.1145/765568.765571.
-
J. Reinders. Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism. O'Reilly, 2007.
-
R. F. Rice. Some practical universal noiseless coding techniques. JPL Publication 79-22, Jet Propulsion Laboratory, Pasadena, 1979.
-
H. Rihani, P. Sanders, R. Dementiev. MultiQueues: simple relaxed concurrent priority queues. Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015, 80–82, https://doi.org/10.1145/2755573.2755616.
-
R. L. Rivest, A. Shamir, L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21(2) (1978), 120–126, https://doi.org/10.1145/359340.359342.
-
H. Robbins. A remark on Stirling's formula. The American Mathematical Monthly 62(1) (1955), 26–29, https://doi.org/10.2307/2308012.
-
A. Rosenfeld, J. L. Pfaltz. Sequential operations in digital picture processing. Journal of the ACM 13(4) (1966), 471–494, https://doi.org/10.1145/321356.321357.
-
D. J. Rosenkrantz, R. E. Stearns, P. M. Lewis. An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing 6(3) (1977), 563–581, https://doi.org/10.1137/0206041.
-
M. Rubinchik, A. M. Shur. EERTREE: an efficient data structure for processing palindromes in strings. European Journal of Combinatorics 68 (2018), 249–265, https://doi.org/10.1016/j.ejc.2017.07.021.
-
S. Russell, P. Norvig. Artificial Intelligence: A Modern Approach. 4th edition, Pearson, 2020, code at https://github.com/aimacode/aima-python.
-
Y. Saad. Iterative Methods for Sparse Linear Systems. 2nd edition, SIAM, 2003, https://doi.org/10.1137/1.9780898718003.
-
J. K. Salmon, M. A. Moraes, R. O. Dror, D. E. Shaw. Parallel random numbers: as easy as 1, 2, 3. International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2011, 1–12, https://doi.org/10.1145/2063384.2063405.
-
K. Samelson, F. L. Bauer. Sequential formula translation. Communications of the ACM 3(2) (1960), 76–83, https://doi.org/10.1145/366959.366968.
-
P. Sanders. Randomized priority queues for fast parallel access. Journal of Parallel and Distributed Computing 49(1) (1998), 86–97, https://doi.org/10.1006/jpdc.1998.1429.
-
P. Sanders. Fast priority queues for cached memory. ACM Journal of Experimental Algorithmics 5 (2000), article 7, https://doi.org/10.1145/351827.384249.
-
P. Sanders, S. Winkel. Super scalar sample sort. European Symposium on Algorithms (ESA), LNCS 3221 (2004), 784–796, https://doi.org/10.1007/978-3-540-30140-0_69.
-
P. Sanders, F. Transier. Intersection in integer inverted indices. In: Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX 2007), 2007, 71–83, https://doi.org/10.1137/1.9781611972870.7.
-
P. Sanders, C. Schulz. Think locally, act globally: highly balanced graph partitioning. Experimental Algorithms (SEA 2013), LNCS 7933 (2013), 164–175, https://doi.org/10.1007/978-3-642-38527-8_16.
-
P. Sanders, K. Mehlhorn, M. Dietzfelbinger, R. Dementiev. Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox. Springer, 2019, chapter 6, https://doi.org/10.1007/978-3-030-25209-0.
-
H. Sarbazi-Azad. Stupid sort: a new sorting algorithm. Newsletter 599, Department of Computing Science, University of Glasgow, 2000.
-
A. Sato, Y. Matsui. PCF learned sort: a learning augmented sort algorithm with \(O( n \log \log n )\) expected complexity. arXiv:2405.07122 (2024), https://doi.org/10.48550/arXiv.2405.07122.
-
R. Schaffer, R. Sedgewick. The analysis of heapsort. Journal of Algorithms 15(1) (1993), 76–100, https://doi.org/10.1006/jagm.1993.1031.
-
B. Schlegel, T. Willhalm, W. Lehner. Fast sorted-set intersection using SIMD instructions. In: Proceedings of the 2nd International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS 2011), 2011, 1–8.
-
H. Schorr, W. M. Waite. An efficient machine-independent procedure for garbage collection in various list structures. Communications of the ACM 10(8) (1967), 501–506, https://doi.org/10.1145/363534.363554.
-
E. S. Schwartz, B. Kallick. Generating a canonical prefix encoding. Communications of the ACM 7(3) (1964), 166–169, https://doi.org/10.1145/363958.363991.
-
J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM 27(4) (1980), 701–717, https://doi.org/10.1145/322217.322225.
-
R. Sedgewick. Permutation generation methods. ACM Computing Surveys 9(2) (1977), 137–164, https://doi.org/10.1145/356689.356692.
-
R. Sedgewick. Implementing Quicksort programs. Communications of the ACM 21(10) (1978), 847–857, https://doi.org/10.1145/359619.359631.
-
R. Sedgewick. Algorithms in C++, Parts 1–4. 3rd edition, Addison-Wesley, 1998.
-
R. Sedgewick. Algorithms in C++, Part 5: Graph Algorithms. 3rd edition, Addison-Wesley, 2002.
-
R. Sedgewick. Left-leaning red-black trees. Department of Computer Science, Princeton University, 2008.
-
R. Sedgewick, K. Wayne. Algorithms. 4th edition, Addison-Wesley, 2011, https://algs4.cs.princeton.edu.
-
R. Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of Computer and System Sciences 51(3) (1995), 400–403, https://doi.org/10.1006/jcss.1995.1078.
-
R. Seidel, C. R. Aragon. Randomized search trees. Algorithmica 16(4-5) (1996), 464–497, https://doi.org/10.1007/BF01940876.
-
P. H. Sellers. The theory and computation of evolutionary distances: pattern recognition. Journal of Algorithms 1(4) (1980), 359–373, https://doi.org/10.1016/0196-6774(80)90016-4.
-
M. I. Shamos, D. Hoey. Closest-point problems. Proceedings of the 16th Annual Symposium on Foundations of Computer Science (FOCS), 1975, 151–162, https://doi.org/10.1109/SFCS.1975.8.
-
C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal 27(3) (1948), 379–423, https://doi.org/10.1002/j.1538-7305.1948.tb01338.x.
-
Z. Shao, J. H. Reppy, A. W. Appel. Unrolling lists. Proceedings of the 1994 ACM Conference on LISP and Functional Programming, 1994, 185–195, https://doi.org/10.1145/182409.182453.
-
M. Sharir. A strong-connectivity algorithm and its applications in data flow analysis. Computers & Mathematics with Applications 7(1) (1981), 67–72, https://doi.org/10.1016/0898-1221(81)90008-0.
-
D. L. Shell. A high-speed sorting procedure. Communications of the ACM 2(7) (1959), 30–32, https://doi.org/10.1145/368370.368387.
-
Z. Shen, Z. Wan, Y. Gu, Y. Sun. Many sequential iterative algorithms can be parallel and (nearly) work-efficient. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2022), 273–286, https://doi.org/10.1145/3490148.3538574.
-
H. Shi, J. Schaeffer. Parallel sorting by regular sampling. Journal of Parallel and Distributed Computing 14(4) (1992), 361–372, https://doi.org/10.1016/0743-7315(92)90075-X.
-
Y. Shiloach, U. Vishkin. An \(O( \log n )\) parallel connectivity algorithm. Journal of Algorithms 3(1) (1982), 57–67, https://doi.org/10.1016/0196-6774(82)90008-6.
-
D. Shkarin. PPM: one step to practicality. Proceedings of the Data Compression Conference (DCC 2002), 202–211, 2002, https://doi.org/10.1109/DCC.2002.999958.
-
J. Shun, G. E. Blelloch. Phase-concurrent hash tables for determinism. Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2014, 96–107, https://doi.org/10.1145/2612669.2612687.
-
J. Shun, Y. Gu, G. E. Blelloch, J. T. Fineman, P. B. Gibbons. Sequential random permutation, list contraction and tree contraction are highly parallel. ACM-SIAM Symposium on Discrete Algorithms (SODA) (2015), 431–448, https://doi.org/10.1137/1.9781611973730.30.
-
J. Shun. Parallel wavelet tree construction. Proceedings of the 25th Data Compression Conference (DCC 2015), 63–72, 2015, https://doi.org/10.1109/DCC.2015.7.
-
J. G. Siek, L.-Q. Lee, A. Lumsdaine. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley, 2002.
-
J. Sinclair and others. Deterministic variants of the Miller-Rabin primality test. Web page, https://miller-rabin.appspot.com.
-
J. Sinclair, et al. Deterministic variants of the Miller-Rabin primality test. https://miller-rabin.appspot.com.
-
J. Singler, P. Sanders, F. Putze. MCSTL: the multi-core standard template library. Euro-Par 2007, LNCS 4641 (2007), 682–694, https://doi.org/10.1007/978-3-540-74466-5_72.
-
P. Sinha. A memory-efficient doubly linked list. Linux Journal 129 (2004).
-
M. Skarupke. I wrote a faster sorting algorithm. 2016, https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/.
-
S. S. Skiena, M. A. Revilla. Programming Challenges. Springer, 2003, https://doi.org/10.1007/b97559.
-
S. S. Skiena. The Algorithm Design Manual. 3rd edition, Springer, 2020, https://doi.org/10.1007/978-3-030-54256-6.
-
D. D. Sleator, R. E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences 26(3) (1983), 362–391, https://doi.org/10.1016/0022-0000(83)90006-5.
-
D. D. Sleator, R. E. Tarjan. Self-adjusting binary search trees. Journal of the ACM 32(3) (1985), 652–686, https://doi.org/10.1145/3828.3835.
-
D. D. Sleator, R. E. Tarjan. Self-adjusting heaps. SIAM Journal on Computing 15(1) (1986), 52–69, https://doi.org/10.1137/0215004.
-
S. Slotin. Algorithms for Modern Hardware. 2022, chapter 13.8 (Static B-trees), https://en.algorithmica.org/hpc/data-structures/s-tree/.
-
W. E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly 3(1–2) (1956), 59–66, https://doi.org/10.1002/nav.3800030106.
-
A. R. Smith. Tint fill. Proceedings of the 6th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH 1979), 1979, 276–283, https://doi.org/10.1145/800249.807456.
-
T. F. Smith, M. S. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology 147(1) (1981), 195–197, https://doi.org/10.1016/0022-2836(81)90087-5.
-
T. M. Smith, R. A. van de Geijn, M. Smelyanskiy, J. R. Hammond, F. G. Van Zee. Anatomy of high-performance many-threaded matrix multiplication. IEEE International Parallel and Distributed Processing Symposium (IPDPS) (2014), 1049–1059, https://doi.org/10.1109/IPDPS.2014.110.
-
Y. Solodkyy, G. Dos Reis, B. Stroustrup. Open and efficient type switch for C++. Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA 2012), 963–982, 2012, https://doi.org/10.1145/2384616.2384686.
-
M. Šošić, M. Šikić. Edlib: a C/C++ library for fast, exact sequence alignment using edit distance. Bioinformatics 33(9) (2017), 1394–1395, https://doi.org/10.1093/bioinformatics/btw753.
-
P. M. Spira, A. Pan. On finding and updating spanning trees and shortest paths. SIAM Journal on Computing 4(3) (1975), 375–380, https://doi.org/10.1137/0204032.
-
R. P. Stanley. Catalan Numbers. Cambridge University Press, 2015, https://doi.org/10.1017/CBO9781139871495.
-
J. T. Stasko, J. S. Vitter. Pairing heaps: experiments and analysis. Communications of the ACM 30(3) (1987), 234–249, https://doi.org/10.1145/214748.214759.
-
C. L. Staudt, A. Sazonovs, H. Meyerhenke. NetworKit: a tool suite for large-scale complex network analysis. Network Science 4(4) (2016), 508–530, https://doi.org/10.1017/nws.2016.20.
-
G. L. Steele, D. Lea, C. H. Flood. Fast splittable pseudorandom number generators. Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA), 2014, 453–472, https://doi.org/10.1145/2660193.2660195.
-
J. Stein. Computational problems associated with Racah algebra. Journal of Computational Physics 1(3) (1967), 397–405, https://doi.org/10.1016/0021-9991(67)90047-2.
-
A. Stepanov, P. McJones. Elements of Programming. Addison-Wesley, 2009.
-
J. A. Storer, T. G. Szymanski. Data compression via textual substitution. Journal of the ACM 29(4) (1982), 928–951, https://doi.org/10.1145/322344.322346.
-
Q. F. Stout, B. L. Warren. Tree rebalancing in optimal time and space. Communications of the ACM 29(9) (1986), 902–908, https://doi.org/10.1145/6592.6599.
-
V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik 13(4) (1969), 354–356, https://doi.org/10.1007/BF02165411.
-
B. Stroustrup. The C++ Programming Language. 4th edition, Addison-Wesley, 2013.
-
N. R. Sturtevant. HOG2. Software, https://github.com/MovingAILab/hog2.
-
N. R. Sturtevant. Benchmarks for grid-based pathfinding. IEEE Transactions on Computational Intelligence and AI in Games 4(2) (2012), 144–148, https://doi.org/10.1109/TCIAIG.2012.2197681.
-
K. Sugiyama, S. Tagawa, M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics 11(2) (1981), 109–125, https://doi.org/10.1109/TSMC.1981.4308636.
-
Y. Sun, D. Ferizovic, G. E. Blelloch. PAM: parallel augmented maps. Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2018, 290–304, https://doi.org/10.1145/3178487.3178509.
-
Y. Sun, G. E. Blelloch. Parallel range, segment and rectangle queries with augmented maps. Proceedings of the 21st Workshop on Algorithm Engineering and Experiments (ALENEX), 2019, 159–173, https://doi.org/10.1137/1.9781611975499.13.
-
H. Sundell, P. Tsigas. Fast and lock-free concurrent priority queues for multi-thread systems. Journal of Parallel and Distributed Computing 65(5) (2005), 609–627, https://doi.org/10.1016/j.jpdc.2004.12.005; first in the Proceedings of the 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), 11, https://doi.org/10.1109/IPDPS.2003.1213189.
-
A. Sutton, B. Stroustrup. Design of concept libraries for C++. In: Software Language Engineering (SLE 2011), Lecture Notes in Computer Science 6940, Springer, 2012, 97–118, https://doi.org/10.1007/978-3-642-28830-2_6.
-
M. Sutton, T. Ben-Nun, A. Barak. Optimizing parallel graph connectivity computation via subgraph sampling. IEEE International Parallel and Distributed Processing Symposium (IPDPS) (2018), 12–21, https://doi.org/10.1109/IPDPS.2018.00012.
-
K. Tangwongsan, M. Hirzel, S. Schneider. In-order sliding-window aggregation in worst-case constant time. The VLDB Journal 30(6) (2021), 933–957, https://doi.org/10.1007/s00778-021-00668-3.
-
F. J. Tapia. Boost.Sort: spinsort, flat_stable_sort. Boost C++ Libraries 1.67, 2018, https://www.boost.org/doc/libs/1_67_0/libs/sort/doc/html/index.html.
-
R. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing 1(2) (1972), 146–160, https://doi.org/10.1137/0201010.
-
R. Tarjan. Enumeration of the elementary circuits of a directed graph. SIAM Journal on Computing 2(3) (1973), 211–216, https://doi.org/10.1137/0202017.
-
R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM 22(2) (1975), 215–225, https://doi.org/10.1145/321879.321884.
-
R. E. Tarjan. Sensitivity analysis of minimum spanning trees and shortest path trees. Information Processing Letters 14(1) (1982), 30–33, https://doi.org/10.1016/0020-0190(82)90137-5.
-
R. E. Tarjan. Data Structures and Network Algorithms. SIAM, 1983, chapter 4 (the join of the Red-Black trees), https://doi.org/10.1137/1.9781611970265.
-
R. E. Tarjan, J. van Leeuwen. Worst-case analysis of set union algorithms. Journal of the ACM 31(2) (1984), 245–281, https://doi.org/10.1145/62.2160.
-
R. E. Tarjan. Amortized computational complexity. SIAM Journal on Algebraic and Discrete Methods 6(2) (1985), 306–318, https://doi.org/10.1137/0606031.
-
R. E. Tarjan. Sensitivity analysis of minimum spanning trees and shortest path trees (corrigendum). Information Processing Letters 23(4) (1986), 219, https://doi.org/10.1016/0020-0190(86)90139-0.
-
R. E. Tarjan, R. F. Werneck. Dynamic trees in practice. ACM Journal of Experimental Algorithmics 14 (2009), article 4.5, https://doi.org/10.1145/1498698.1594231.
-
J. T. Thayer, W. Ruml. Bounded suboptimal search: a direct approach using inadmissible estimates. Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), 2011, 674–679, https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-119.
-
M. Thorup. High speed hashing for integers and strings. arXiv:1504.06804, 2015, https://doi.org/10.48550/arXiv.1504.06804.
-
I. H. Toroslu, G. Üçoluk. Incremental assignment problem. Information Sciences 177(6) (2007), 1523–1529, https://doi.org/10.1016/j.ins.2006.05.004.
-
R. K. Treiber. Systems programming: coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, 1986.
-
C. R. Trott, D. Lebrun-Grandié, D. Arndt, J. Ciesko, V. Dang, N. Ellingwood, R. Gayatri, E. Harvey, D. S. Hollman, D. Ibanez, N. Liber, J. Madsen, J. Miles, D. Poliakoff, A. Powell, S. Rajamanickam, M. Simberg, D. Sunderland, B. Turcksin, J. Wilke. Kokkos 3: programming model extensions for the exascale era. IEEE Transactions on Parallel and Distributed Systems 33(4) (2022), 805–817, https://doi.org/10.1109/TPDS.2021.3097283.
-
H. F. Trotter. Algorithm 115: Perm. Communications of the ACM 5(8) (1962), 434–435, https://doi.org/10.1145/368637.368660.
-
S. Tschöke, R. Lüling, B. Monien. Solving the traveling salesman problem with a distributed branch-and-bound algorithm on a 1024 processor network. Proceedings of the 9th International Parallel Processing Symposium (IPPS), 1995, 182–189, https://doi.org/10.1109/IPPS.1995.395930.
-
T. Tseng, L. Dhulipala, J. Shun. Parallel batch-dynamic minimum spanning forest and the efficiency of dynamic agglomerative graph clustering. Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2022), 2022, 233–245, https://doi.org/10.1145/3490148.3538584.
-
J. W. Tukey. The ninther, a technique for low-effort robust (resistant) location in large samples. In: H. A. David (ed.), Contributions to Survey Sampling and Applied Statistics, Academic Press, 1978, 251–257, https://doi.org/10.1016/B978-0-12-204750-3.50024-1.
-
E. Ukkonen. Algorithms for approximate string matching. Information and Control 64(1–3) (1985), 100–118, https://doi.org/10.1016/S0019-9958(85)80046-2.
-
E. Ukkonen. Finding approximate patterns in strings. Journal of Algorithms 6(1) (1985), 132–137, https://doi.org/10.1016/0196-6774(85)90023-9.
-
E. Ukkonen. On-line construction of suffix trees. Algorithmica 14(3) (1995), 249–260, https://doi.org/10.1007/BF01206331.
-
K. Vaidya, S. Chatterjee, E. Knorr, M. Mitzenmacher, S. Idreos, T. Kraska. SNARF: a learning-enhanced range filter. Proceedings of the VLDB Endowment 15(8) (2022), 1632–1644, https://doi.org/10.14778/3529337.3529347.
-
P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters 6(3) (1977), 80–82, https://doi.org/10.1016/0020-0190(77)90031-X.
-
J. van Leeuwen, D. Wood. Interval heaps. The Computer Journal 36(3) (1993), 209–216, https://doi.org/10.1093/comjnl/36.3.209.
-
P. J. Varman, S. D. Scheufler, B. R. Iyer, G. R. Ricard. Merging multiple lists on hierarchical-memory multiprocessors. Journal of Parallel and Distributed Computing 12(2) (1991), 171–177, https://doi.org/10.1016/0743-7315(91)90022-2.
-
S. Vigna. Broadword implementation of rank/select queries. In: Experimental Algorithms (WEA 2008), Lecture Notes in Computer Science 5038, Springer, 2008, 154–168, https://doi.org/10.1007/978-3-540-68552-4_12.
-
S. Vigna. Quasi-succinct indices. Proceedings of the 6th ACM Conference on Web Search and Data Mining (WSDM 2013), 83–92, 2013, https://doi.org/10.1145/2433396.2433409.
-
J. S. Vitter. Implementations for coalesced hashing. Communications of the ACM 25(12) (1982), 911–926, https://doi.org/10.1145/358728.358745.
-
J. S. Vitter. Faster methods for random sampling. Communications of the ACM 27(7) (1984), 703–718, https://doi.org/10.1145/358105.893.
-
J. S. Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical Software 11(1) (1985), 37–57, https://doi.org/10.1145/3147.3165.
-
J. S. Vitter. An efficient algorithm for sequential random sampling. ACM Transactions on Mathematical Software 13(1) (1987), 58–67, https://doi.org/10.1145/23002.23003.
-
J. S. Vitter. External memory algorithms and data structures: dealing with massive data. ACM Computing Surveys 33(2) (2001), 209–271, https://doi.org/10.1145/384192.384193.
-
B. Vöcking. How asymmetry helps load balancing. Journal of the ACM 50(4) (2003), 568–589, https://doi.org/10.1145/792538.792546.
-
A. Volgenant. An addendum on the incremental assignment problem. Information Sciences 178(23) (2008), 4583, https://doi.org/10.1016/j.ins.2008.07.020.
-
M. D. Vose. A linear algorithm for generating random numbers with a given distribution. IEEE Transactions on Software Engineering 17(9) (1991), 972–975, https://doi.org/10.1109/32.92917.
-
M. Voss, R. Asenjo, J. Reinders. Pro TBB: C++ Parallel Programming with Threading Building Blocks. Apress, 2019, https://doi.org/10.1007/978-1-4842-4398-5.
-
J. Vuillemin. A data structure for manipulating priority queues. Communications of the ACM 21(4) (1978), 309–315, https://doi.org/10.1145/359460.359478.
-
J. Vuillemin. A unifying look at data structures. Communications of the ACM 23(4) (1980), 229–239, https://doi.org/10.1145/358841.358852.
-
D. Vyukov. Bounded MPMC queue. 2010, https://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue.
-
D. B. Wagner, B. G. Calder. Leapfrogging: a portable technique for implementing efficient futures. ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) (1993), 208–217, https://doi.org/10.1145/155332.155354.
-
A. J. Walker. An efficient method for generating discrete random variables with general distributions. ACM Transactions on Mathematical Software 3(3) (1977), 253–256, https://doi.org/10.1145/355744.355749.
-
S. Walzer, M. Williams. A simple yet exact analysis of the MultiQueue. 33rd European Symposium on Algorithms (ESA), LIPIcs 351 (2025), 85:1–85:14, https://doi.org/10.4230/LIPIcs.ESA.2025.85.
-
H. Wang. Proving theorems by pattern recognition II. Bell System Technical Journal 40(1) (1961), 1–41, https://doi.org/10.1002/j.1538-7305.1961.tb03975.x.
-
J. Wang, K. Zhang, X. Tang, B. Hua. B-Queue: efficient and practical queuing for fast core-to-core communication. International Journal of Parallel Programming 41(1) (2013), 137–159, https://doi.org/10.1007/s10766-012-0213-x.
-
X. Wang, Y. Hong, H. Chang, K. Park, G. Langdale, J. Hu, H. Zhu. Hyperscan: a fast multi-pattern regex matcher for modern CPUs. Proceedings of the 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2019, 631–648, https://www.usenix.org/conference/nsdi19/presentation/wang-xiang.
-
Wang Yi. wyhash and wyrand. Software, https://github.com/wangyi-fudan/wyhash.
-
M. K. Warmuth, D. Haussler. On the complexity of iterated shuffle. Journal of Computer and System Sciences 28(3) (1984), 345–358, https://doi.org/10.1016/0022-0000(84)90018-7.
-
H. C. von Warnsdorf. Des Rösselsprunges einfachste und allgemeinste Lösung. Schmalkalden, 1823.
-
H. S. Warren. Hacker's Delight. 2nd edition, Addison-Wesley, 2012.
-
S. Warshall. A theorem on Boolean matrices. Journal of the ACM 9(1) (1962), 11–12, https://doi.org/10.1145/321105.321107.
-
J. Wassenberg, M. Blacher, J. Giesen, P. Sanders. Vectorized and performance-portable quicksort. Software: Practice and Experience 52(12) (2022), 2684–2699, https://doi.org/10.1002/spe.3142.
-
I. Wegener. BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small). Theoretical Computer Science 118(1) (1993), 81–98, https://doi.org/10.1016/0304-3975(93)90364-Y.
-
M. N. Wegman, J. L. Carter. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences 22(3) (1981), 265–279, https://doi.org/10.1016/0022-0000(81)90033-7.
-
P. Weiner. Linear pattern matching algorithms. Proceedings of the 14th Annual Symposium on Switching and Automata Theory (SWAT), 1973, 1–11, https://doi.org/10.1109/SWAT.1973.13.
-
M. A. Weiss. Data Structures and Algorithm Analysis in C++. 4th edition, Pearson, 2014.
-
T. A. Welch. A technique for high-performance data compression. IEEE Computer 17(6) (1984), 8–19, https://doi.org/10.1109/MC.1984.1659158.
-
J. Westbrook, R. E. Tarjan. Amortized analysis of algorithms for set union with backtracking. SIAM Journal on Computing 18(1) (1989), 1–11, https://doi.org/10.1137/0218001.
-
S. Wild, M. E. Nebel. Average case analysis of Java 7's dual pivot quicksort. Proceedings of the 20th European Symposium on Algorithms (ESA 2012), LNCS 7501 (2012), 825–836, https://doi.org/10.1007/978-3-642-33090-2_71.
-
D. E. Willard. Log-logarithmic worst-case range queries are possible in space \(\Theta( N )\). Information Processing Letters 17(2) (1983), 81–84, https://doi.org/10.1016/0020-0190(83)90075-3.
-
D. E. Willard. New data structures for orthogonal range queries. SIAM Journal on Computing 14(1) (1985), 232–253, https://doi.org/10.1137/0214019.
-
J. W. J. Williams. Algorithm 232: Heapsort. Communications of the ACM 7(6) (1964), 347–348, https://doi.org/10.1145/512274.3734138.
-
S. Williams, L. Oliker, R. Vuduc, J. Shalf, K. Yelick, J. Demmel. Optimization of sparse matrix-vector multiplication on emerging multicore platforms. Parallel Computing 35(3) (2009), 178–194, https://doi.org/10.1016/j.parco.2008.12.006.
-
A. Williams. C++ Concurrency in Action. 2nd edition, Manning, 2019.
-
M. Williams, P. Sanders, R. Dementiev. Engineering MultiQueues: fast relaxed concurrent priority queues. 29th European Symposium on Algorithms (ESA), LIPIcs 204 (2021), 81:1–81:17, https://doi.org/10.4230/LIPIcs.ESA.2021.81.
-
M. Williams, P. Sanders. The MultiQueue: a simple and fast relaxed concurrent priority queue. ACM Transactions on Parallel Computing 12(4) (2025), 1–39, https://doi.org/10.1145/3771738.
-
P. R. Wilson, M. S. Johnstone, M. Neely, D. Boles. Dynamic storage allocation: a survey and critical review. Memory Management (IWMM 1995), Lecture Notes in Computer Science 986, Springer, 1995, 1–116, https://doi.org/10.1007/3-540-60368-9_19.
-
M. Wimmer, F. Versaci, J. L. Träff, D. Cederman, P. Tsigas. Data structures for task-based priority scheduling. Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 2014, 379–380, https://doi.org/10.1145/2555243.2555278.
-
P. Winkler. Mathematical Puzzles: A Connoisseur's Collection. A K Peters, 2004.
-
S. Winograd. On multiplication of 2 x 2 matrices. Linear Algebra and its Applications 4(4) (1971), 381–388, https://doi.org/10.1016/0024-3795(71)90009-7.
-
I. H. Witten, R. M. Neal, J. G. Cleary. Arithmetic coding for data compression. Communications of the ACM 30(6) (1987), 520–540, https://doi.org/10.1145/214762.214771.
-
I. H. Witten, T. C. Bell. The zero-frequency problem: estimating the probabilities of novel events in adaptive text compression. IEEE Transactions on Information Theory 37(4) (1991), 1085–1094, https://doi.org/10.1109/18.87000.
-
I. H. Witten, A. Moffat, T. C. Bell. Managing Gigabytes. 2nd edition, Morgan Kaufmann, 1999.
-
S. Wu, U. Manber. A fast algorithm for multi-pattern searching. Technical Report TR-94-17, Department of Computer Science, University of Arizona, 1994.
-
J. C. Wyllie. The complexity of parallel computations. PhD thesis, Cornell University, 1979.
-
Q. Xie, C. Pang, X. Zhou, X. Zhang, K. Deng. Maximum error-bounded piecewise linear representation for online stream approximation. The VLDB Journal 23(6) (2014), 915–937, https://doi.org/10.1007/s00778-014-0355-0.
-
H. Yan, S. Ding, T. Suel. Inverted index compression and query processing with optimized document ordering. Proceedings of the 18th International World Wide Web Conference (WWW 2009), 401–410, 2009, https://doi.org/10.1145/1526709.1526764.
-
F. F. Yao. Efficient dynamic programming using quadrangle inequalities. Proceedings of the 12th ACM Symposium on Theory of Computing (1980), 429–435, https://doi.org/10.1145/800141.804691.
-
A. C.-C. Yao. A lower bound to finding convex hulls. Journal of the ACM 28(4) (1981), 780–787, https://doi.org/10.1145/322276.322289.
-
P. Yap. Grid-based path-finding. Advances in Artificial Intelligence, LNCS 2338 (2002), 44–55, https://doi.org/10.1007/3-540-47922-8_4.
-
V. Yaroslavskiy. Dual-pivot quicksort. 2009.
-
H. Zhang, H. Lim, V. Leis, D. G. Andersen, M. Kaminsky, K. Keeton, A. Pavlo. SuRF: practical range query filtering with fast succinct tries. In: Proceedings of the 2018 ACM SIGMOD International Conference on Management of Data, 2018, 323–336, https://doi.org/10.1145/3183713.3196931.
-
Y. Zhang, A. Brahmakshatriya, X. Chen, L. Dhulipala, S. Kamil, S. Amarasinghe, J. Shun. Optimizing ordered graph algorithms with GraphIt. ACM/IEEE International Symposium on Code Generation and Optimization (CGO) (2020), 158–170, https://doi.org/10.1145/3368826.3377909.
-
G. Zhang, G. Posluns, M. C. Jeffrey. Multi bucket queues: efficient concurrent priority scheduling. Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024, https://doi.org/10.1145/3626183.3659962.
-
D. Zhou, D. G. Andersen, M. Kaminsky. Space-efficient, high-performance rank and select structures on uncompressed bit sequences. Proceedings of the 12th Symposium on Experimental Algorithms (SEA 2013), LNCS 7933, 151–163, 2013, https://doi.org/10.1007/978-3-642-38527-8_15.
-
R. Zippel. Probabilistic algorithms for sparse polynomials. Proceedings of EUROSAM 1979, LNCS 72 (1979), 216–226, https://doi.org/10.1007/3-540-09519-5_73.
-
J. Ziv, A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory 23(3) (1977), 337–343, https://doi.org/10.1109/TIT.1977.1055714.
-
J. Ziv, A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory 24(5) (1978), 530–536, https://doi.org/10.1109/TIT.1978.1055934.
-
A. L. Zobrist. A new hashing method with application for game playing. Technical Report 88, Computer Sciences Department, University of Wisconsin, 1970; reprinted in ICGA Journal 13(2) (1990), 69–73, https://doi.org/10.3233/ICG-1990-13203.
-
M. Zukowski, S. Heman, N. Nes, P. Boncz. Super-scalar RAM-CPU cache compression. Proceedings of the 22nd International Conference on Data Engineering (ICDE 2006), 59, 2006, https://doi.org/10.1109/ICDE.2006.150.