Journal of the ACM
Công bố khoa học tiêu biểu
* Dữ liệu chỉ mang tính chất tham khảo
Sắp xếp:
Optimal scheduling policies for a class of queues with customer deadlines to the beginning of serviceMany problems can be modeled as single-server queues with impatient customers. An example is that of the transmission of voice packets over a packet-switched network. If the voice packets do not reach their destination within a certain time interval of their transmission, they are useless to the receiver and considered lost. It is therefore desirable to schedule the customers such that the... ... hiện toàn bộ
Journal of the ACM - Tập 35 Số 4 - Trang 832-844 - 1988
A Space-Economical Suffix Tree Construction AlgorithmA new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching. This algorithm has the same asymptotic running time bound as previously published algorithms, but is more economical in space. Some implementation considerations are discussed, and new work on the modification of these search trees in response to incremental changes in th... ... hiện toàn bộ
Journal of the ACM - Tập 23 Số 2 - Trang 262-272 - 1976
Interval arithmeticWe start with a mathematical definition of a real interval as a closed, connected set of reals. Interval arithmetic operations (addition, subtraction, multiplication, and division) are likewise defined mathematically and we provide algorithms for computing these operations assuming exact real arithmetic. Next, we define interval arithmetic operations on intervals with IEEE 754 floating poi... ... hiện toàn bộ
Journal of the ACM - Tập 48 Số 5 - Trang 1038-1068 - 2001
Lower bounds for orthogonal range searching: I. The reporting case
We establish lower bounds on the complexity of orthogonal range reporting in the static case. Given a collection of
n
points in
d
-space and a box [
a
1
,
b... hiện toàn bộ
Journal of the ACM - Tập 37 Số 2 - Trang 200-212 - 1990
The Locality of Distributed Symmetry Breaking
Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the
randomized
complexity of f... ... hiện toàn bộ
Journal of the ACM - Tập 63 Số 3 - Trang 1-45 - 2016
Communication Steps for Parallel Query Processing
We study the problem of computing conjunctive queries over large databases on parallel architectures without shared storage. Using the structure of such a query
q
and the skew in the data, we study tradeoffs between the number of processors, the number of rounds of communication, and the per-processor
... ... hiện toàn bộ
Journal of the ACM - Tập 64 Số 6 - Trang 1-58 - 2017
An Algorithm for Subgraph IsomorphismSubgraph isomorphism can be determined by means of a brute-force tree-search enumeration procedure. In this paper a new algorithm is introduced that attains efficiency by inferentially eliminating successor nodes in the tree search. To assess the time actually taken by the new algorithm, subgraph isomorphism, clique detection, graph isomorphism, and directed graph isomorphism experiments h... ... hiện toàn bộ
Journal of the ACM - Tập 23 Số 1 - Trang 31-42 - 1976
How to assign votes in a distributed system
In a distributed system, one strategy for achieving mutual exclusion of groups of nodes without communication is to assign to each node a number of votes. Only a group with a majority of votes can execute the critical operations, and mutual exclusion is achieved because at any given time there is at most one such group. A second strategy, which
appears... ... hiện toàn bộ
Journal of the ACM - Tập 32 Số 4 - Trang 841-860 - 1985
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Journal of the ACM - Tập 42 Số 6 - Trang 1115-1145 - 1995
Tổng số: 77
- 1
- 2
- 3
- 4
- 5
- 6
- 8