ACM TRANSACTIONS ON ALGORITHMS 欢迎提交最高质量的原始研究，处理本质上离散和有限的算法，并且在目标或分析中以自然的方式具有数学内容。最受欢迎的是新算法和数据结构、新的和改进的分析以及复杂性结果。该杂志涵盖的具体计算领域包括组合搜索和对象；计数；离散优化和近似；随机化和量子计算；并行和分布式计算；图形算法、几何、算术、数论、字符串；在线分析；密码学；编码;数据压缩;学习算法;算法分析方法;离散算法应用于生物学、经济学、博弈论、通信、计算机系统与体系结构、硬件设计、科学计算等应用领域

ACM Transactions on Algorithms welcomes submissions of high-quality original research that deals with discrete and finite algorithms, naturally incorporating mathematical content in its objectives or analyses. We particularly encourage new algorithms and data structures, novel and improved analyses, and complexity results. The specific computational areas covered by the journal include combinatorial search and objects, counting, discrete optimization and approximation, randomized and quantum computing, parallel and distributed computing, graph algorithms, geometry, arithmetic, number theory, string processing, online analysis, cryptography, coding, data compression, learning algorithms, algorithmic analysis methods, and the application of discrete algorithms in fields such as biology, economics, game theory, communications, computer systems and architecture, hardware design, and scientific computing.

《ACM Transactions on Algorithms》欢迎提交高质量的原创研究，主要涉及离散和有限算法，且在目标或分析中自然包含数学内容。我们特别欢迎新算法和数据结构的提出、新的和改进的分析方法，以及复杂性结果的研究。该期刊涵盖的具体计算领域包括组合搜索与对象、计数、离散优化与近似、随机化与量子计算、并行与分布式计算、图算法、几何、算术、数论、字符串处理、在线分析、密码学、编码、数据压缩、学习算法、算法分析方法，以及离散算法在生物学、经济学、博弈论、通信、计算机系统与体系结构、硬件设计、科学计算等领域的应用。

ACM Transactions on Algorithms

Motivated by an application in computational geometry, we consider a novel variant of the problem of efficiently maintaining a forest of dynamic rooted trees. This variant includes an operation that merges two tree paths. In contrast to the standard problem, in which a single operation can only add or delete one arc, one merge can add and delete up to a linear number of arcs. In spite of this, we develop three different methods that need only polylogarithmic time per operation. The first method extends a solution of Farach and Thorup [1998] for the special case of paths. Each merge takes O (log 2 n ) amortized time on an n -node forest and each standard dynamic tree operation takes O (log n ) time; the latter bound is amortized, worst case, or randomized depending on the underlying data structure. For the special case that occurs in the motivating application, in which arbitrary arc deletions (cuts) do not occur, we give a method that takes O (log n ) time per operation, including merging. This is best possible in a model of computation with an Ω( n log n ) lower bound for sorting n numbers, since such sorting can be done in O ( n ) tree operations. For the even-more-special case in which there are no cuts and no parent queries, we give a method that uses standard dynamic trees as a black box: each mergeable tree operation becomes a constant number of standard dynamic tree operations. This third method can also be used in the motivating application, but only by changing the algorithm in the application. Each of our three methods needs different analytical tools and reveals different properties of dynamic trees.

Loukas Georgiadis

Haim Kaplan

Nira Shafrir

Robert E. Tarjan

Renato F. Werneck

Data structures for mergeable trees

可合并树的数据结构

Exact string matching in labeled graphs is the problem of searching paths of a graph G=(V, E) such that the concatenation of their node labels is equal to a given pattern string P [1. m ]. This basic problem can be found at the heart of more complex operations on variation graphs in computational biology, of query operations in graph databases, and of analysis operations in heterogeneous networks. We prove a conditional lower bound stating that, for any constant ε &gt; 0, an O (| E | 1 - ε m ) time, or an O (| E | m 1 - ε )time algorithm for exact string matching in graphs, with node labels and pattern drawn from a binary alphabet, cannot be achieved unless the Strong Exponential Time Hypothesis ( SETH ) is false. This holds even if restricted to undirected graphs with maximum node degree 2—that is, to zig-zag matching in bidirectional strings , or to deterministic directed acyclic graphs whose nodes have maximum sum of indegree and outdegree 3. These restricted cases make the lower bound stricter than what can be directly derived from related bounds on regular expression matching (Backurs and Indyk, FOCS’16). In fact, our bounds are tight in the sense that lowering the degree or the alphabet size yields linear time solvable problems. An interesting corollary is that exact and approximate matching are equally hard (i.e., quadratic time) in graphs under SETH . In comparison, the same problems restricted to strings have linear time vs quadratic time solutions, respectively (approximate pattern matching having also a matching SETH lower bound (Backurs and Indyk, STOC’15)).

Massimo Equi

Veli Mäkinen

Alexandru I. Tomescu

Roberto Grossi

On the Complexity of String Matching for Graphs

图上字符串匹配的复杂性研究

Given a weighted, ordered query set \(Q\) and a partition of \(Q\) into classes, we study the problem of computing a minimum-cost decision tree that, given any query \(q\in Q\) , uses equality tests and less-than tests to determine \(q\) ’s class. Such a tree can be faster and smaller than a conventional search tree and smaller than a lookup table (both of which must identify \(q\) , not just its class). We give the first polynomial-time algorithm for the problem. The algorithm extends naturally to the setting where each query has multiple allowed classes.

Marek Chrobak

Neal E. Young

Classification via Two-Way Comparisons

通过双向比较进行分类

Since the invention of the pairing heap by Fredman, Sedgewick, Sleator, and Tarjan [8], it has been an open question whether this or any other simple “self-adjusting” heap supports decrease-key operations in \(\mathrm{O}(\log\log n)\) time, where \(n\) is the number of heap items. Using powerful new techniques, we answer this question in the affirmative. We prove that both slim and smooth heaps, recently introduced self-adjusting heaps, support heap operations in the following amortized time bounds: \(\mathrm{O}(\log n)\) for delete-min and delete, \(\mathrm{O}(\log\log n)\) for decrease-key, and \(\mathrm{O}(1)\) for all other heap operations, including insert and meld, where \(n\) is the number of heap items that are eventually deleted: Items inserted but never deleted do not count in the bounds. We also analyze the multipass pairing heap, a variant of pairing heaps. For this heap implementation, we obtain the same bounds except for decrease-key, for which our bound is \(\mathrm{O}(\log\log n\cdot\log\log\log n)\) , where again items that are never deleted do not count in \(n\) . Our bounds significantly improve the best previously known bounds for all three data structures. For slim and smooth heaps our bounds are tight, since they match lower bounds of Iacono and Özkan [13].

Corwin Sinnamon

Efficiency of Self-Adjusting Heaps

自调整堆的效率

An independent set in a graph \(G\) is a set of pairwise non-adjacent vertices. A graph \(G\) is bipartite if its vertex set can be partitioned into two independent sets. In the Odd Cycle Transversal problem, the input is a graph \(G\) along with a weight function w associating a rational weight with each vertex, and the task is to find a minimum weight vertex subset \(S\) in \(G\) such that \(G-S\) is bipartite; the weight of \(S\) , \(\text{w}(S)=\sum_{v\in S}\text{w}(v)\) . We show that Odd Cycle Transversal is polynomial-time solvable on graphs excluding \(P_{5}\) (a path on five vertices) as an induced subgraph. The problem was previously known to be polynomial-time solvable on \(P_{4}\) -free graphs and NP -hard on \(P_{6}\) -free graphs [Dabrowski, Feghali, Johnson, Paesani, Paulusma and Rzążewski, Algorithmica 2020]. Bonamy, Dabrowski, Feghali, Johnson and Paulusma [Algorithmica 2019] posed the existence of a polynomial-time algorithm on \(P_{5}\) -free graphs as an open problem. This was later re-stated by Rzążewski [Dagstuhl Reports, 9(6): 2019], by Chudnovsky, King, Pilipczuk, Rzążewski, and Spirkl [SIDMA 2021] who gave an algorithm with running time \(n^{O(\sqrt{n})}\) for the problem, and by Agrawal, Lima, Lokshtanov, Saurabh, and Sharma [SODA 2024] who gave a quasi-polynomial time algorithm.

Akanksha Agrawal

Paloma T. Lima

Daniel Lokshtanov

Paweł Rzążewski

Saket Saurabh

Roohani Sharma

Odd Cycle Transversal on \(P_{5}\) -free Graphs in Polynomial Time

在多项式时间内解决 \(P_{5}\) -无奇环图的奇环横贯问题

We present the strict Fibonacci heap , the first pointer-based heap implementation with time bounds matching those of Fibonacci heaps in the worst case. Strict Fibonacci heaps support make-heap, insert, find-min, meld and decrease-key in worst-case \(O(1)\) time, and delete and delete-min in worst-case \(O(\lg n)\) time, where \(n\) is the size of the heap. The data structure uses linear space. A previous solution achieving the same time bounds in the RAM model made essential use of arrays and extensive use of redundant counter schemes to maintain balance. Our solution uses neither. Our key simplification is to discard the structure of the smaller heap when doing a meld, and to use the pigeonhole principle in place of the redundant counter mechanism to maintain balance.

Gerth Stølting Brodal

George Lagogiannis

Strict Fibonacci Heaps

严格斐波那契堆

In the matroid partitioning problem, we are given \(k\) matroids \(\mathcal{M}_{1}=(V,\mathcal{I}_{1}),\dots,\mathcal{M}_{k}=(V,\mathcal{I}_{k})\) defined over a common ground set \(V\) of \(n\) elements, and we need to find a partitionable set \(S\subseteq V\) of largest possible cardinality, denoted by \(p\) . Here, a set \(S\subseteq V\) is called partitionable if there exists a partition \((S_{1},\dots,S_{k})\) of \(S\) with \(S_{i}\in\mathcal{I}_{i}\) for \(i=1,\ldots,k\) . In 1986, Cunningham [SICOMP 1986] presented a matroid partition algorithm that uses \(O(np^{3/2}+kn)\) independence oracle queries, which was the previously known best algorithm. This query complexity is \(O(n^{5/2})\) when \(k\leq n\) . Our main result is to present a matroid partition algorithm that uses \(\tilde{O}(k^{\prime 1/3}np+kn)\) independence oracle queries, where \(k^{\prime}=\min\{k,p\}\) . This query complexity is \(\tilde{O}(n^{7/3})\) when \(k\leq n\) , which improves upon that of Cunningham’s algorithm. To obtain our algorithm, we present a new approach edge recycling augmentation , which can be attained through new ideas: an efficient utilization of the binary search technique by Nguy \(\tilde{{\hat{\text{e}}}}\) n [2019] and Chakrabarty-Lee-Sidford-Singla-Wong [FOCS 2019] and a careful analysis of the independence oracle query complexity. Our analysis differs significantly from the one for matroid intersection algorithms, because of the parameter \(k\) . We also present a matroid partition algorithm that uses \(\tilde{O}((n+k)\sqrt{p})\) rank oracle queries.

Abbreviation	ACM Trans. Algorithms
Journal Impact	0.79
Quartiles(Global)	MATHEMATICS, APPLIED(Q3)

ISSN	1549-6325, 1549-6333
h-index	59

Publication Information	Publisher: Association for Computing Machinery (ACM)，Publishing cycle: Quarterly，Journal Type: journal，Open Access Journals: No
Basic data	Year of publication: 2005，Proportion of original research papers: 100.00%，Self Citation Rate:0.00%， Gold OA Rate: 0.88%
Average review cycle	网友分享经验：较慢,6-12周
Average recruitment ratio	网友分享经验：容易

ACM Transactions on Algorithms

Journal Citation Format

A journal article with 1 author

A journal article with 2 authors

A journal article with 3 authors

A journal article with 5 or more authors

Books Citation Format

Thesis Citation Format

Web sites Citation Format

Patent Citation Format

Staying up late manually editing references? ivySCI automatically matches journals and helps you generate references with a single click.

Share Submission Experience

Data structures for mergeable trees

On the Complexity of String Matching for Graphs

Classification via Two-Way Comparisons

Efficiency of Self-Adjusting Heaps

Odd Cycle Transversal on \(P_{5}\) -free Graphs in Polynomial Time

Classification via Two-Way Comparisons

Efficiency of Self-Adjusting Heaps

Odd Cycle Transversal on \(P_{5}\) -free Graphs in Polynomial Time

Strict Fibonacci Heaps

Faster Matroid Partition Algorithms