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

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

An elimination tree for a connected graph \(G\) is a rooted tree on the vertices of \(G\) obtained by choosing a root \(x\) and recursing on the connected components of \(G-x\) to produce the subtrees of \(x\) . Elimination trees appear in many guises in computer science and discrete mathematics, and they encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent Hartung-Hoang-Mütze-Williams combinatorial generation framework to elimination trees, and prove that all elimination trees for a chordal graph \(G\) can be generated by tree rotations using a simple greedy algorithm. This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs. Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations. As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations. Our algorithm for generating all elimination trees for a chordal graph \(G\) can be implemented in time \(cO(\sigma)\) on average per generated elimination tree, where \(\sigma=\sigma(G)\) denotes the maximum number of edges of an induced star in \(G\) . If \(G\) is a tree, we improve this to a loopless algorithm running in time \(cO(1)\) per generated elimination tree. We also prove that our algorithm produces a Hamilton cycle on the graph associahedron of \(G\) , rather than just Hamilton path, if the graph \(G\) is chordal and 2-connected. Moreover, our algorithm characterizes chordality, i.e., it computes a Hamilton path on the graph associahedron of \(G\) if and only if \(G\) is chordal.

Jean Cardinal

Arturo Merino

Torsten Mütze

Combinatorial generation via permutation languages. IV. Elimination trees

通过排列语言的组合生成。IV. 消除树

This paper introduces a new data-structural object that we call the tiny pointer. In many applications, traditional \(\log n\) -bit pointers can be replaced with \(o(\log n)\) -bit tiny pointers at the cost of only a constant-factor time overhead and a small probability of failure. We develop a comprehensive theory of tiny pointers, and give optimal constructions for both fixed-size tiny pointers (i.e., settings in which all of the tiny pointers must be the same size) and variable-size tiny pointers (i.e., settings in which the average tiny-pointer size must be small, but some tiny pointers can be larger). If a tiny pointer references an item in an array filled to load factor \(1-\delta\) , then the optimal tiny-pointer size is \(\Theta(\log\log\log n+\log\delta^{-1})\) bits in the fixed-size case, and \(\Theta(\log\delta^{-1})\) expected bits in the variable-size case. Our tiny-pointer constructions also require us to revisit several classic problems having to do with balls and bins; these results may be of independent interest. Using tiny pointers, we apply tiny pointers to five classic data-structure problems. We show that: A data structure storing \(n\) \(v\) -bit values for \(n\) keys with constant-factor time modifications/queries can be implemented to take space \(nv+O(n\log^{(r)}n)\) bits, for any constant \(r\gt0\) , as long as the user stores a tiny pointer of expected size \(O(1)\) with each key—here, \(\log^{(r)}n\) is the \(r\) -th iterated logarithm. Any binary search tree can be made succinct, meaning that it achieves \((1+o(1))\) times the optimal space, with constant-factor time overhead, and can even be made to be within \(O(n)\) bits of optimal if we allow for \(O(\log^{*}n)\) -time modifications—this holds even for rotation-based trees such as the splay tree and the red-black tree. Any fixed-capacity key-value dictionary can be made stable (i.e., items do not move once inserted) with constant-factor time overhead and \((1+o(1))\) -factor space overhead. Any key-value dictionary that requires uniform-size values can be made to support arbitrary-size values with constant-factor time overhead and with an additional space consumption of \(\log^{(r)}n+O(\log j)\) bits per \(j\) -bit value for an arbitrary constant \(r\gt0\) of our choice. Given an external-memory array \(A\) of size \((1+\varepsilon)n\) containing a dynamic set of up to \(n\) key-value pairs, it is possible to maintain an internal-memory stash of size \(O(n\log\varepsilon^{-1})\) bits so that the location of any key-value pair in \(A\) can be computed in constant time (and with no IOs). In each case tiny pointers allow for us to take a natural space-inefficient solution that uses pointers and make it space-efficient for free.

Michael A. Bender

Alex Conway

Martín Farach-Colton

William Kuszmaul

Guido Tagliavini

Tiny Pointers

微小指针

We consider the problem of computing the Maximal Exact Matches (MEMs) of a given pattern \(P[1\mathinner{.. }m]\) on a large repetitive text collection \(T[1\mathinner{.. }n]\) over an alphabet of size \(\sigma\) , which is represented as a (hopefully much smaller) run-length context-free grammar of size \(g_{rl}\) . We show that the problem can be solved in time \(O(m^{2}\log^{\epsilon}n)\) , for any constant \(\epsilon\gt0\) , on a data structure of size \(O(g_{rl})\) . Further, on a locally consistent grammar of size \(O(\delta\log\frac{n\log\sigma}{\delta\log n})\) , the time decreases to \(O(m\log m(\log m+\log^{\epsilon}n))\) . The value \(\delta\) is a function of the substring complexity of \(T\) and \(\Omega(\delta\log\frac{n\log\sigma}{\delta\log n})\) is a tight lower bound on the compressibility of repetitive texts \(T\) , so our structure has optimal size in terms of \(n\) , \(\sigma\) , and \(\delta\) . We extend our results to several related problems, such as finding \(k\) -MEMs, MUMs, rare MEMs, and applications. Categories and Subject Descriptors: E.1 [Data structures] ; E.2 [Data storage representations] ; E.4 [Coding and information theory]: Data compaction and compression; F.2.2 [Analysis of algorithms and problem complexity] : Nonnumerical algorithms and problems— Pattern matching, Computations on discrete structures, Sorting and searching

Gonzalo Navarro

Computing MEMs and Relatives on Repetitive Text Collections

重复文本集合上的MEMs及其相关计算

Maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this significant problem in the fully dynamic setting, where elements can be both inserted and deleted in real-time. Our main result is a randomized algorithm that maintains an efficient data structure with an \({\tilde{O}({k^{2}}{\varepsilon})}\) amortized update time (in the number of insertions and deletions) and yields a \({(4+O(\varepsilon))}\) -approximate solution with respect to the dynamic optimum, where \(k\) is the rank of the matroid.

Paul Dütting

Federico Fusco

Silvio Lattanzi

Ashkan Norouzi-Fard

Morteza Zadimoghaddam

Fully Dynamic Submodular Maximization over Matroids

完全动态子模最大化在拟阵上的研究

The \(k\) -Strong Conflict-Free ( \(k\) -SCF, in short) colouring problem seeks to find a colouring of the vertices of a hypergraph \(H\) using minimum number of colours so that in every hyperedge \(e\) of \(H\) , there are at least \(\min\{|e|,k\}\) vertices whose colours are different from that of all other vertices in \(e\) . In the case of interval hypergraphs, we present an exact \({\mathsf{P}}\) -time algorithm for the \(k\) -SCF problem thus solving an open problem posed by Cheilaris et al. (2014). We achieve our results by showing that for any hypergraph, a \(k\) -SCF colouring is a proper colouring of a related simple graph which we refer to as a co-occurrence graph . We then show that a co-occurrence graph is obtained by identifying an induced subgraph of a second simple graph that we introduce, which we refer to as the conflict graph . For interval hypergraphs, we show that each co-occurrence graph and the conflict graph are perfect graphs. This property plays a crucial role in our polynomial time algorithm. Secondly, we show that for an interval hypergraph, the \(1\) -SCF colouring number is the minimum partition of its intervals into sets such that each set has an exact hitting set (a hitting set in which each interval is hit exactly once).

N.S. Narayanaswamy

S.M. Dhannya

Perfect Resolution of Strong Conflict-Free Colouring of Interval Hypergraphs

区间超图的强无冲突着色的完美分辨率

短名	ACM Trans. Algorithms
Journal Impact	0.79
国际分区	MATHEMATICS, APPLIED(Q3)
期刊索引	SCI Q3中科院 3 区

ISSN	1549-6325, 1549-6333
h-index	59
国内分区	计算机科学(3区)计算机科学计算机理论方法(2区)计算机科学应用数学(2区)

涉及主题	计算机科学数学组合数学离散数学算法数学分析程序设计语言理论计算机科学数学优化工程类图形操作系统几何学哲学上下界人工智能物理统计时间复杂性生物
出版信息	出版商: Association for Computing Machinery (ACM)，出版周期: Quarterly，期刊类型: journal，开源期刊: 否
基本数据	创刊年份: 2005，原创研究文献占比: 100.00%，自引率:0.00%， Gold OA占比: 0.88%
平均审稿周期	网友分享经验：较慢,6-12周
平均录用比例	网友分享经验：容易

ACM Transactions on Algorithms

期刊引文格式

有 1 位以上作者的期刊

有 2 位作者的期刊

有 3 位作者的期刊

有 5 位以上作者的期刊

书籍引用格式

学位论文引用格式

网页引用格式

专利引用格式

手工熬夜修改参考文献？研飞自动匹配期刊，一键轻松成稿，支持 Word/WPS

投稿经验分享

Data structures for mergeable trees

On the Complexity of String Matching for Graphs

Combinatorial generation via permutation languages. IV. Elimination trees

Tiny Pointers

Computing MEMs and Relatives on Repetitive Text Collections

Combinatorial generation via permutation languages. IV. Elimination trees

Computing MEMs and Relatives on Repetitive Text Collections

Tiny Pointers

Fully Dynamic Submodular Maximization over Matroids

Perfect Resolution of Strong Conflict-Free Colouring of Interval Hypergraphs