Log in

Relevant bibliographies by topics / Deterministic constant time algorithms

Contents

Journal articles

Academic literature on the topic 'Deterministic constant time algorithms'

Author: Grafiati

Published: 30 May 2022

Last updated: 31 May 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Deterministic constant time algorithms.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Deterministic constant time algorithms"

1

Jayanti, Prasad, and Siddhartha Jayanti. "Deterministic Constant-Amortized-RMR Abortable Mutex for CC and DSM." ACM Transactions on Parallel Computing 8, no. 4 (2021): 1–26. http://dx.doi.org/10.1145/3490559.

Full text

Abstract:

The abortable mutual exclusion problem, proposed by Scott and Scherer in response to the needs in real-time systems and databases, is a variant of mutual exclusion that allows processes to abort from their attempt to acquire the lock. Worst-case constant remote memory reference algorithms for mutual exclusion using hardware instructions such as Fetch&Add or Fetch&Store have long existed for both cache coherent (CC) and distributed shared memory multiprocessors, but no such algorithms are known for abortable mutual exclusion. Even relaxing the worst-case requirement to amortized, algori

APA, Harvard, Vancouver, ISO, and other styles

2

SUEL, TORSTEN. "PERMUTATION ROUTING AND SORTING ON MESHES WITH ROW AND COLUMN BUSES." Parallel Processing Letters 05, no. 01 (1995): 63–80. http://dx.doi.org/10.1142/s0129626495000072.

Full text

Abstract:

We study the problems of permutation routing and sorting on several models of meshes with fixed and reconfigurable row and column buses. We describe two fast and fairly simple deterministic algorithms for permutation routing on two-dimensional networks, and a more complicated algorithm for multi-dimensional networks. The algorithms are obtained by converting two known off-line routing schemes into deterministic routing algorithms, and they can be implemented on a variety of different models of meshes with buses. We also give a deterministic algorithm for 1–1 sorting whose running time matches

APA, Harvard, Vancouver, ISO, and other styles

3

DAS, SAJAL K., and RANETTE H. HALVERSON. "SIMPLE DETERMINISTIC AND RANDOMIZED ALGORITHMS FOR LINKED LIST RANKING ON THE EREW PRAM MODEL." Parallel Processing Letters 04, no. 01n02 (1994): 15–27. http://dx.doi.org/10.1142/s012962649400003x.

Full text

Abstract:

An asynchronous, CRCW PRAM (or APRAM) algorithm for linked list ranking, proposed by Martel and Subramonian, performs EO (n log log n) expected work employing [Formula: see text] processors. Motivated by their unique approach, this paper proposes two EREW list ranking algorithms – one deterministic and the other randomized. The deterministic algorithm performs in [Formula: see text] time using p processors, where n≥p log p. Thus, for p= O (n/ log n), it requires O ( log n log log n) time and O (n log log n) work. Although not work-optimal, this algorithm is very simple compared to the known wo

APA, Harvard, Vancouver, ISO, and other styles

4

Khadiev, Kamil, and Vladislav Remidovskii. "Classical and Quantum Algorithms for Assembling a Text from a Dictionary." Nonlinear Phenomena in Complex Systems 24, no. 3 (2021): 207–21. http://dx.doi.org/10.33581/1561-4085-2021-24-3-207-221.

Full text

Abstract:

We study algorithms for solving the problem of assembling a text (long string) from a dictionary (a sequence of small strings). The problem has an application in bioinformatics and has a connection with the sequence assembly method for reconstructing a long deoxyribonucleic-acid (DNA) sequence from small fragments. The problem is assembling a string t of length n from strings s1,...,sm. Firstly, we provide a classical (randomized) algorithm with running time Õ(nL0.5 + L) where L is the sum of lengths of s1,...,sm. Secondly, we provide a quantum algorithm with running time Õ(nL0.25 + √mL). Thir

APA, Harvard, Vancouver, ISO, and other styles

5

Allender, Eric, V. Arvind, Rahul Santhanam, and Fengming Wang. "Uniform derandomization from pathetic lower bounds." Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 370, no. 1971 (2012): 3512–35. http://dx.doi.org/10.1098/rsta.2011.0318.

Full text

Abstract:

The notion of probabilistic computation dates back at least to Turing, who also wrestled with the practical problems of how to implement probabilistic algorithms on machines with, at best, very limited access to randomness. A more recent line of research, known as derandomization, studies the extent to which randomness is superfluous. A recurring theme in the literature on derandomization is that probabilistic algorithms can be simulated quickly by deterministic algorithms, if one can obtain impressive (i.e. superpolynomial, or even nearly exponential) circuit size lower bounds for certain pro

APA, Harvard, Vancouver, ISO, and other styles

6

Rajasekaran, Sanguthevar. "On the Euclidean Minimum Spanning Tree Problem." Computing Letters 1, no. 1 (2005): 11–14. http://dx.doi.org/10.1163/1574040053326325.

Full text

Abstract:

Given a weighted graph G(V;E), a minimum spanning tree for G can be obtained in linear time using a randomized algorithm or nearly linear time using a deterministic algorithm. Given n points in the plane, we can construct a graph with these points as nodes and an edge between every pair of nodes. The weight on any edge is the Euclidean distance between the two points. Finding a minimum spanning tree for this graph is known as the Euclidean minimum spanning tree problem (EMSTP). The minimum spanning tree algorithms alluded to before will run in time O(n2) (or nearly O(n2)) on this graph. In thi

APA, Harvard, Vancouver, ISO, and other styles

7

Efthymiou, Charilaos. "Deterministic counting of graph colourings using sequences of subgraphs." Combinatorics, Probability and Computing 29, no. 4 (2020): 555–86. http://dx.doi.org/10.1017/s0963548320000255.

Full text

Abstract:

AbstractIn this paper we propose a polynomial-time deterministic algorithm for approximately counting the k-colourings of the random graph G(n, d/n), for constant d>0. In particular, our algorithm computes in polynomial time a $(1\pm n^{-\Omega(1)})$ -approximation of the so-called ‘free energy’ of the k-colourings of G(n, d/n), for $k\geq (1+\varepsilon) d$ with probability $1-o(1)$ over the graph instances.Our algorithm uses spatial correlation decay to compute numerically estimates of marginals of the Gibbs distribution. Spatial correlation decay has been used in different counting schem

APA, Harvard, Vancouver, ISO, and other styles

8

Tarnawski, Jakub. "New graph algorithms via polyhedral techniques." it - Information Technology 63, no. 3 (2021): 177–82. http://dx.doi.org/10.1515/itit-2021-0014.

Full text

Abstract:

Abstract This article gives a short overview of my dissertation, where new algorithms are given for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. The first part of the dissertation addresses a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given edge-weighted directed graph. A ρ-approximation algorithm for AT

APA, Harvard, Vancouver, ISO, and other styles

9

Hu, Xiao-Bing, Ming Wang, Mark S. Leeson, Ezequiel A. Di Paolo, and Hao Liu. "Deterministic Agent-Based Path Optimization by Mimicking the Spreading of Ripples." Evolutionary Computation 24, no. 2 (2016): 319–46. http://dx.doi.org/10.1162/evco_a_00156.

Full text

Abstract:

Inspirations from nature have contributed fundamentally to the development of evolutionary computation. Learning from the natural ripple-spreading phenomenon, this article proposes a novel ripple-spreading algorithm (RSA) for the path optimization problem (POP). In nature, a ripple spreads at a constant speed in all directions, and the node closest to the source is the first to be reached. This very simple principle forms the foundation of the proposed RSA. In contrast to most deterministic top-down centralized path optimization methods, such as Dijkstra’s algorithm, the RSA is a bottom-up dec

APA, Harvard, Vancouver, ISO, and other styles

10

Mehta, Dinesh P., Carl Shetters, and Donald W. Bouldin. "Meta-Algorithms for Scheduling a Chain of Coarse-Grained Tasks on an Array of Reconfigurable FPGAs." VLSI Design 2013 (December 25, 2013): 1–13. http://dx.doi.org/10.1155/2013/249592.

Full text

Abstract:

This paper considers the problem of scheduling a chain of n coarse-grained tasks on a linear array of k reconfigurable FPGAs with the objective of primarily minimizing reconfiguration time. A high-level meta-algorithm along with two detailed meta-algorithms (GPRM and SPRM) that support a wide range of problem formulations and cost functions is presented. GPRM, the more general of the two schemes, reduces the problem to computing a shortest path in a DAG; SPRM, the less general scheme, employs dynamic programming. Both meta algorithms are linear in n and compute optimal solutions. GPRM can be e

APA, Harvard, Vancouver, ISO, and other styles

More sources

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!