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 service
Journal of the ACM - Tập 35 Số 4 - Trang 832-844 - 1988
Shivendra S. Panwar, Don Towsley, Jack K. Wolf
Many 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ộ
Connected Component Labeling Using Quadtrees
Journal of the ACM - Tập 28 Số 3 - Trang 487-501 - 1981
Hanan Samet
A Space-Economical Suffix Tree Construction Algorithm
Journal of the ACM - Tập 23 Số 2 - Trang 262-272 - 1976
Edward M. McCreight
A 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ộ
Interval arithmetic
Journal of the ACM - Tập 48 Số 5 - Trang 1038-1068 - 2001
Timothy J. Hickey, Qun Ju, M. H. van Emden
We 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ộ
Lower bounds for orthogonal range searching: I. The reporting case
Journal of the ACM - Tập 37 Số 2 - Trang 200-212 - 1990
Bernard Chazelle
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ộ
The Locality of Distributed Symmetry Breaking
Journal of the ACM - Tập 63 Số 3 - Trang 1-45 - 2016
Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider
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ộ
Communication Steps for Parallel Query Processing
Journal of the ACM - Tập 64 Số 6 - Trang 1-58 - 2017
Paul Beame, Paraschos Koutris, Dan Suciu
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ộ
An Algorithm for Subgraph Isomorphism
Journal of the ACM - Tập 23 Số 1 - Trang 31-42 - 1976
J. R. Ullmann
Subgraph 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ộ
How to assign votes in a distributed system
Journal of the ACM - Tập 32 Số 4 - Trang 841-860 - 1985
Héctor García-Molina, Daniel Barbará
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ộ
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
Michel X. Goemans, David P. Williamson
Tổng số: 77   
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 8