Communication

295 relations: A* search algorithm, Aanderaa–Karp–Rosenberg conjecture, Abstract rewriting system, ACC0, Adin Falkoff, Alexander Razborov, Alexander Vardy, Allan Borodin, Alternating Turing machine, Andrew V. Goldberg, Angela Y. Wu, Apex graph, Arrival theorem, Ashok K. Chandra, Association for Computing Machinery, Éva Tardos, Baker's technique, Baruch Awerbuch, Bentley–Ottmann algorithm, Berman–Hartmanis conjecture, Bernard Chazelle, Bidimensionality, Bidirectional search, Binary search algorithm, Bipartite half, BIT predicate, Blum axioms, Blum's speedup theorem, Bottleneck traveling salesman problem, Bounded expansion, Brenda Baker, Bucket queue, Busy beaver, Carlo Ghezzi, Chemical database, Chvátal–Sankoff constants, Clique problem, Clique-sum, Closest string, Clustered planarity, Commitment scheme, Common knowledge (logic), Communicating sequential processes, Communications of the ACM, Computational geometry, Computational resource, Computational topology, Computer magazine, Computers and Intractability, Connected component (graph theory), ..., Connectivity (graph theory), Consensus (computer science), Convex polytope, Convex position, Convex volume approximation, Cut (graph theory), Cycle rank, CYK algorithm, Cynthia Dwork, Daniel Sleator, Danny Dolev, David Eppstein, Davis–Putnam algorithm, Degeneracy (graph theory), Denotational semantics of the Actor model, Depth-first search, Derek Corneil, Dijkstra Prize, Dominating set, Don Towsley, Donald B. Johnson, Douglas McIlroy, DPLL algorithm, Edward M. McCreight, Entropy compression, Euclidean shortest path, Existential theory of the reals, Expander graph, Exponential search, Fast Fourier transform, Feedback arc set, Feedback vertex set, Firing squad synchronization problem, Floyd–Warshall algorithm, Frame problem, Frankl–Rödl graph, Fulkerson Prize, Fusion tree, Gap theorem, Gábor Tardos, Gödel Prize, Gbcast, Gerard Salton, Giuseppe F. Italiano, Gossip protocol, Graph homomorphism, Graph isomorphism problem, Graph minor, Graph power, Graphic matroid, Hagit Attiya, Hamiltonian completion, Hamiltonian path problem, Hardness of approximation, Harry R. Lewis, Hilary Putnam, Horn clause, Horn-satisfiability, Householder transformation, Hypertree, Iacono's working set structure, IBM System/360 Model 67, Imieliński-Lipski algebra, Implicit graph, In-place algorithm, Independent set (graph theory), Indexed grammar, Indexed language, Informatics General, Integer sorting, Iterative refinement, James B. Saxe, Jan Bergstra, János Komlós (mathematician), Jeannette Wing, Job shop scheduling, Joel Hass, John Alan Robinson, John C. Reynolds, Johnson's algorithm, Johnson–Lindenstrauss lemma, Joseph Halpern, Joseph Seffi Naor, Julia Chuzhoy, K-independent hashing, K-minimum spanning tree, Karloff–Zwick algorithm, Kenneth L. Clarkson, Kuratowski's theorem, L/poly, Larry Stockmeyer, Lempel–Ziv–Storer–Szymanski, Line graph, Linear congruential generator, Link/cut tree, Linkless embedding, List of computer science journals, List of important publications in computer science, List of important publications in concurrent, parallel, and distributed computing, List of important publications in theoretical computer science, List of scientific journals, Longest common subsequence problem, Longest palindromic substring, Longest path problem, Loopless algorithm, LP-type problem, M/M/1 queue, M/M/c queue, Manuel Blum, Map graph, Marvin Stein (computer scientist), Massachusetts Computer Associates, Matching (graph theory), Matroid parity problem, Matthew K. Franklin, Maxima of a point set, Maximum cut, Maximum flow problem, Mean value analysis, Median graph, Michael J. Fischer, Mihalis Yannakakis, Mikkel Thorup, Minimum spanning tree, Minimum-weight triangulation, Naive Bayes classifier, Naor–Reingold pseudorandom function, Nathan Netanyahu, Needleman–Wunsch algorithm, Neighbourhood (graph theory), Nested stack automaton, Newman's lemma, Nimrod Megiddo, Nondeterministic algorithm, Null (SQL), Omer Reingold, Open-shop scheduling, Order-maintenance problem, Otakar Borůvka, Outerplanar graph, Package-merge algorithm, Parallel computation thesis, Parametric search, Patrick C. Fischer, Paxos (computer science), PCP theorem, Penny graph, Perfect hash function, Permanent (mathematics), Permutation pattern, Peter B. Andrews, Peter Landin, Peter Sanders (computer scientist), Planar cover, Planar separator theorem, Planarity testing, Polynomial identity testing, Power domains, Prabhakar Raghavan, Predecessor problem, Prefix sum, Priority queue, Probabilistically checkable proof, Processor sharing, Product-form solution, Pseudorandom function family, QMA, Queueing theory, Rajeev Motwani, Random projection, Randomized algorithm, Raphael Rom, Raymond Reiter, Reachability, Read-once function, Relative neighborhood graph, Replicator (cellular automaton), Resolution (logic), Richard Weber (mathematician), Robert Kowalski, Robertson–Seymour theorem, Rotation map, Rule 90, Ruth Silverman, S. L. Hakimi, Sauer–Shelah lemma, Science and technology in Venezuela, Sentence extraction, Series-parallel graph, Set cover problem, Set splitting problem, Sethi–Ullman algorithm, Shafi Goldwasser, Shannon switching game, SHARE Operating System, Sheila Greibach, Shellsort, Situation calculus, SL (complexity), Soft heap, Soundex, Splay tree, Spline (mathematics), Split (graph theory), Stack-sortable permutation, Star-shaped polygon, Steven Muchnick, Strong NP-completeness, Structured program theorem, Subgraph isomorphism problem, Subset sum problem, Suffix tree, Sum of radicals, Super-prime, Symmetric Turing machine, Tabulation hashing, Takao Nishizeki, Tarjan's off-line lowest common ancestors algorithm, Teofilo F. Gonzalez, Theoretical computer science, Timeline of computational mathematics, Timeline of numerical analysis after 1945, Timeline of scientific computing, Tomasz Imieliński, Transitive reduction, Travelling salesman problem, Tree-depth, Treewidth, Trigonometric tables, Turing machine, Ukkonen's algorithm, Unary numeral system, Unique games conjecture, Unknotting problem, Urquhart graph, Valerie King, Vertex cover, Vertex cycle cover, Victor Vianu, Wayne Snyder, Wiener index, Work stealing, Xuong tree, Zig-zag product, 2-satisfiability. Expand index (245 more) » « Shrink index

A* search algorithm

In computer science, A* (pronounced as "A star") is a computer algorithm that is widely used in pathfinding and graph traversal, which is the process of plotting an efficiently directed path between multiple points, called "nodes".

New!!: Journal of the ACM and A* search algorithm · See more »

Aanderaa–Karp–Rosenberg conjecture

In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture (also known as the Aanderaa–Rosenberg conjecture or the evasiveness conjecture) is a group of related conjectures about the number of questions of the form "Is there an edge between vertex u and vertex v?" that have to be answered to determine whether or not an undirected graph has a particular property such as planarity or bipartiteness.

New!!: Journal of the ACM and Aanderaa–Karp–Rosenberg conjecture · See more »

Abstract rewriting system

In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviation ARS) is a formalism that captures the quintessential notion and properties of rewriting systems.

New!!: Journal of the ACM and Abstract rewriting system · See more »

ACC0

ACC0, sometimes called ACC, is a class of computational models and problems defined in circuit complexity, a field of theoretical computer science.

New!!: Journal of the ACM and ACC0 · See more »

Adin Falkoff

Adin D. Falkoff (19 December 1921 – 13 August 2010) was an engineer and computer systems and programming systems designer who was mostly known for his work on the programming language APL and systems for IBM.

New!!: Journal of the ACM and Adin Falkoff · See more »

Alexander Razborov

Aleksandr Aleksandrovich Razborov (Алекса́ндр Алекса́ндрович Разбо́ров; born February 16, 1963), sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist.

New!!: Journal of the ACM and Alexander Razborov · See more »

Alexander Vardy

Alexander Vardy is a Russian-born and Israeli-educated electrical engineer known for his expertise in coding theory.

New!!: Journal of the ACM and Alexander Vardy · See more »

Allan Borodin

Allan Bertram Borodin (born 1941) is a Canadian-American computer scientist who is a University Professor at the University of Toronto.

New!!: Journal of the ACM and Allan Borodin · See more »

Alternating Turing machine

In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP.

New!!: Journal of the ACM and Alternating Turing machine · See more »

Andrew V. Goldberg

Andrew Vladislav Goldberg (born 1960) is an American computer scientist working primarily on design, analysis, and experimental evaluation of algorithms.

New!!: Journal of the ACM and Andrew V. Goldberg · See more »

Angela Y. Wu

Angela Yuen Wu is an American computer scientist, a professor emerita at American University.

New!!: Journal of the ACM and Angela Y. Wu · See more »

Apex graph

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex.

New!!: Journal of the ACM and Apex graph · See more »

Arrival theorem

In queueing theory, a discipline within the mathematical theory of probability, the arrival theorem (also referred to as the random observer property, ROP or job observer property) states that "upon arrival at a station, a job observes the system as if in steady state at an arbitrary instant for the system without that job." The arrival theorem always holds in open product-form networks with unbounded queues at each node, but it also holds in more general networks.

New!!: Journal of the ACM and Arrival theorem · See more »

Ashok K. Chandra

Ashok K. Chandra (30 July 1948 – 15 November 2014) was a computer scientist at Microsoft Research in Mountain View, California, United States, where he was a general manager at the Internet Services Research Center.

New!!: Journal of the ACM and Ashok K. Chandra · See more »

Association for Computing Machinery

The Association for Computing Machinery (ACM) is an international learned society for computing.

New!!: Journal of the ACM and Association for Computing Machinery · See more »

Éva Tardos

Éva Tardos (born 1 October 1957) is a Hungarian mathematician and the Jacob Gould Schurman Professor of Computer Science at Cornell University.

New!!: Journal of the ACM and Éva Tardos · See more »

Baker's technique

In theoretical computer science, Baker's technique is a method for designing polynomial-time approximation schemes (PTASs) for problems on planar graphs.

New!!: Journal of the ACM and Baker's technique · See more »

Baruch Awerbuch

Baruch Awerbuch (born 1958) is an Israeli-American computer scientist, a professor of computer science at Johns Hopkins University.

New!!: Journal of the ACM and Baruch Awerbuch · See more »

Bentley–Ottmann algorithm

In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all ''crossings'' in a set of line segments, i.e. it finds the intersection points (or, simply, intersections) of line segments.

New!!: Journal of the ACM and Bentley–Ottmann algorithm · See more »

Berman–Hartmanis conjecture

In structural complexity theory, the Berman–Hartmanis conjecture is an unsolved conjecture named after Leonard C. Berman and Juris Hartmanis that states that all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms.

New!!: Journal of the ACM and Berman–Hartmanis conjecture · See more »

Bernard Chazelle

Bernard Chazelle (born November 5, 1955) is a French-American computer scientist.

New!!: Journal of the ACM and Bernard Chazelle · See more »

Bidimensionality

Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs.

New!!: Journal of the ACM and Bidimensionality · See more »

Bidirectional search

Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph.

New!!: Journal of the ACM and Bidirectional search · See more »

Binary search algorithm

In computer science, binary search, also known as half-interval search,logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.

New!!: Journal of the ACM and Binary search algorithm · See more »

Bipartite half

In graph theory, the bipartite half or half-square of a bipartite graph G.

New!!: Journal of the ACM and Bipartite half · See more »

BIT predicate

In mathematics and computer science, the BIT predicate or Ackermann coding, sometimes written BIT(i, j), is a predicate which tests whether the jth bit of the number i is 1, when i is written in binary.

New!!: Journal of the ACM and BIT predicate · See more »

Blum axioms

In computational complexity theory the Blum axioms or Blum complexity axioms are axioms that specify desirable properties of complexity measures on the set of computable functions.

New!!: Journal of the ACM and Blum axioms · See more »

Blum's speedup theorem

In computational complexity theory, Blum's speedup theorem, first stated by Manuel Blum in 1967, is a fundamental theorem about the complexity of computable functions.

New!!: Journal of the ACM and Blum's speedup theorem · See more »

Bottleneck traveling salesman problem

The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization.

New!!: Journal of the ACM and Bottleneck traveling salesman problem · See more »

Bounded expansion

In graph theory, a family of graphs is said to have bounded expansion if all of its shallow minors are sparse graphs.

New!!: Journal of the ACM and Bounded expansion · See more »

Brenda Baker

Brenda Sue Baker is an American computer scientist.

New!!: Journal of the ACM and Brenda Baker · See more »

Bucket queue

In the design and analysis of data structures, a bucket queue (also called a bucket priority queue. See also p. 157 for the history and naming of this structure. or bounded-height priority queue) is a priority queue for prioritizing elements whose priorities are small integers.

New!!: Journal of the ACM and Bucket queue · See more »

Busy beaver

The busy beaver game consists of designing a halting, binary-alphabet Turing machine which writes the most 1s on the tape, using only a limited set of states.

New!!: Journal of the ACM and Busy beaver · See more »

Carlo Ghezzi

Carlo Ghezzi is a professor and Chair of Software Engineering at the Politecnico di Milano, Italy and an Adjunct Professor at the Università della Svizzera italiana (USI), Switzerland.

New!!: Journal of the ACM and Carlo Ghezzi · See more »

Chemical database

A chemical database is a database specifically designed to store chemical information.

New!!: Journal of the ACM and Chemical database · See more »

Chvátal–Sankoff constants

In mathematics, the Chvátal–Sankoff constants are mathematical constants that describe the lengths of longest common subsequences of random strings.

New!!: Journal of the ACM and Chvátal–Sankoff constants · See more »

Clique problem

In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph.

New!!: Journal of the ACM and Clique problem · See more »

Clique-sum

In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology.

New!!: Journal of the ACM and Clique-sum · See more »

Closest string

In theoretical computer science, the closest string is an NP-hard computational problem, which tries to find the geometrical center of a set of input strings.

New!!: Journal of the ACM and Closest string · See more »

Clustered planarity

In graph drawing, a clustered planar graph is a graph together with a hierarchical clustering on its vertices, such that the graph drawn together with a collection of simple closed curves surrounding each cluster, so that there are no crossings between graph edges or clusters.

New!!: Journal of the ACM and Clustered planarity · See more »

Commitment scheme

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later.

New!!: Journal of the ACM and Commitment scheme · See more »

Common knowledge (logic)

Common knowledge is a special kind of knowledge for a group of agents.

New!!: Journal of the ACM and Common knowledge (logic) · See more »

Communicating sequential processes

In computer science, communicating sequential processes (CSP) is a formal language for describing patterns of interaction in concurrent systems.

New!!: Journal of the ACM and Communicating sequential processes · See more »

Communications of the ACM

Communications of the ACM is the monthly journal of the Association for Computing Machinery (ACM).

New!!: Journal of the ACM and Communications of the ACM · See more »

Computational geometry

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry.

New!!: Journal of the ACM and Computational geometry · See more »

Computational resource

In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.

New!!: Journal of the ACM and Computational resource · See more »

Computational topology

Algorithmic topology, or computational topology, is a subfield of topology with an overlap with areas of computer science, in particular, computational geometry and computational complexity theory.

New!!: Journal of the ACM and Computational topology · See more »

Computer magazine

Computer magazines are about computers and related subjects, such as networking and the Internet.

New!!: Journal of the ACM and Computer magazine · See more »

Computers and Intractability

In computer science, more specifically computational complexity theory, Computers and Intractability: A Guide to the Theory of NP-Completeness is an influential textbook by Michael Garey and David S. Johnson.

New!!: Journal of the ACM and Computers and Intractability · See more »

Connected component (graph theory)

In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.

New!!: Journal of the ACM and Connected component (graph theory) · See more »

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to disconnect the remaining nodes from each other.

New!!: Journal of the ACM and Connectivity (graph theory) · See more »

Consensus (computer science)

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes.

New!!: Journal of the ACM and Consensus (computer science) · See more »

Convex polytope

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn.

New!!: Journal of the ACM and Convex polytope · See more »

Convex position

In discrete and computational geometry, a set of points in the Euclidean plane is said to be in convex position or convex independent if none of the points can be represented as a convex combination of the others.

New!!: Journal of the ACM and Convex position · See more »

Convex volume approximation

In the analysis of algorithms, several authors have studied the computation of the volume of high-dimensional convex bodies, a problem that can also be used to model many other problems in combinatorial enumeration.

New!!: Journal of the ACM and Convex volume approximation · See more »

Cut (graph theory)

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets.

New!!: Journal of the ACM and Cut (graph theory) · See more »

Cycle rank

In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi.

New!!: Journal of the ACM and Cycle rank · See more »

CYK algorithm

In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars, named after its inventors, John Cocke, Daniel Younger and Tadao Kasami.

New!!: Journal of the ACM and CYK algorithm · See more »

Cynthia Dwork

Cynthia Dwork (born 1958) is an American computer scientist at Harvard University, where she is Gordon McKay Professor of Computer Science, Radcliffe Alumnae Professor at the Radcliffe Institute for Advanced Study, and Affiliated Professor, Harvard Law School.

New!!: Journal of the ACM and Cynthia Dwork · See more »

Daniel Sleator

Daniel Dominic Kaplan Sleator (born 10 December 1953 in St. Louis) is a Professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States.

New!!: Journal of the ACM and Daniel Sleator · See more »

Danny Dolev

Daniel (Danny) Dolev is an Israeli computer scientist known for his research in cryptography and distributed computing.

New!!: Journal of the ACM and Danny Dolev · See more »

David Eppstein

David Arthur Eppstein (born 1963) is an American computer scientist and mathematician.

New!!: Journal of the ACM and David Eppstein · See more »

Davis–Putnam algorithm

The Davis–Putnam algorithm was developed by Martin Davis and Hilary Putnam for checking the validity of a first-order logic formula using a resolution-based decision procedure for propositional logic.

New!!: Journal of the ACM and Davis–Putnam algorithm · See more »

Degeneracy (graph theory)

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges.

New!!: Journal of the ACM and Degeneracy (graph theory) · See more »

Denotational semantics of the Actor model

The denotational semantics of the Actor model is the subject of denotational domain theory for Actors.

New!!: Journal of the ACM and Denotational semantics of the Actor model · See more »

Depth-first search

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.

New!!: Journal of the ACM and Depth-first search · See more »

Derek Corneil

Derek Gordon Corneil is a Canadian mathematician and computer scientist, a professor emeritus of computer science at the University of Toronto, and an expert in graph algorithms and graph theory.

New!!: Journal of the ACM and Derek Corneil · See more »

Dijkstra Prize

The Edsger W. Dijkstra Paper Prize in Distributed Computing is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade.

New!!: Journal of the ACM and Dijkstra Prize · See more »

Dominating set

In graph theory, a dominating set for a graph G.

New!!: Journal of the ACM and Dominating set · See more »

Don Towsley

Donald Fred "Don" Towsley (born 1949) is an American computer scientist who has been a Distinguished University Professor in the School of Computer Science at the University of Massachusetts Amherst.

New!!: Journal of the ACM and Don Towsley · See more »

Donald B. Johnson

Donald Bruce Johnson (December 16, 1933 – September 10, 1994) was an American computer scientist, a researcher in the design and analysis of algorithms, and the founding chair of the computer science department at Dartmouth College.

New!!: Journal of the ACM and Donald B. Johnson · See more »

Douglas McIlroy

Malcolm Douglas McIlroy (born 1932) is a mathematician, engineer, and programmer.

New!!: Journal of the ACM and Douglas McIlroy · See more »

DPLL algorithm

In computer science, the Davis–Putnam–Logemann–Loveland (DPLL) algorithm is a complete, backtracking-based search algorithm for deciding the satisfiability of propositional logic formulae in conjunctive normal form, i.e. for solving the CNF-SAT problem.

New!!: Journal of the ACM and DPLL algorithm · See more »

Edward M. McCreight

Edward Meyers McCreight is an American computer scientist.

New!!: Journal of the ACM and Edward M. McCreight · See more »

Entropy compression

In mathematics and theoretical computer science, entropy compression is an information theoretic method for proving that a random process terminates, originally used by Robin Moser to prove an algorithmic version of the Lovász local lemma.

New!!: Journal of the ACM and Entropy compression · See more »

Euclidean shortest path

The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles.

New!!: Journal of the ACM and Euclidean shortest path · See more »

Existential theory of the reals

In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form where F(X_1,\dots X_n) is a quantifier-free formula involving equalities and inequalities of real polynomials.

New!!: Journal of the ACM and Existential theory of the reals · See more »

Expander graph

In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below.

New!!: Journal of the ACM and Expander graph · See more »

Exponential search

In computer science, an exponential search (also called doubling search or galloping search or Struzik search) is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists.

New!!: Journal of the ACM and Exponential search · See more »

Fast Fourier transform

A fast Fourier transform (FFT) is an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components.

New!!: Journal of the ACM and Fast Fourier transform · See more »

Feedback arc set

In graph theory, a directed graph may contain directed cycles, a one-way loop of edges.

New!!: Journal of the ACM and Feedback arc set · See more »

Feedback vertex set

In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles.

New!!: Journal of the ACM and Feedback vertex set · See more »

Firing squad synchronization problem

The firing squad synchronization problem is a problem in computer science and cellular automata in which the goal is to design a cellular automaton that, starting with a single active cell, eventually reaches a state in which all cells are simultaneously active.

New!!: Journal of the ACM and Firing squad synchronization problem · See more »

Floyd–Warshall algorithm

In computer science, the Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).

New!!: Journal of the ACM and Floyd–Warshall algorithm · See more »

Frame problem

In artificial intelligence, the frame problem describes an issue with using first-order logic (FOL) to express facts about a robot in the world.

New!!: Journal of the ACM and Frame problem · See more »

Frankl–Rödl graph

In graph theory and computational complexity theory, a Frankl–Rödl graph is a graph defined by connecting pairs of vertices of a hypercube that are at a specified even distance from each other.

New!!: Journal of the ACM and Frankl–Rödl graph · See more »

Fulkerson Prize

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS).

New!!: Journal of the ACM and Fulkerson Prize · See more »

Fusion tree

In computer science, a fusion tree is a type of tree data structure that implements an associative array on -bit integers.

New!!: Journal of the ACM and Fusion tree · See more »

Gap theorem

In computational complexity theory the Gap Theorem, also known as the Borodin-Trakhtenbrot Gap Theorem, is a major theorem about the complexity of computable functions.

New!!: Journal of the ACM and Gap theorem · See more »

Gábor Tardos

Gábor Tardos (born 11 July 1964) is a Hungarian mathematician, currently a professor at Central European University and previously a Canada Research Chair at Simon Fraser University.

New!!: Journal of the ACM and Gábor Tardos · See more »

Gödel Prize

The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory (ACM SIGACT).

New!!: Journal of the ACM and Gödel Prize · See more »

Gbcast

Gbcast (also known as group broadcast) is a reliable multicast protocol that provides ordered, fault-tolerant (all-or-none) message delivery in a group of receivers within a network of machines that experience crash failure.

New!!: Journal of the ACM and Gbcast · See more »

Gerard Salton

Gerard A. "Gerry" Salton (8 March 1927 in Nuremberg – 28 August 1995), was a Professor of Computer Science at Cornell University.

New!!: Journal of the ACM and Gerard Salton · See more »

Giuseppe F. Italiano

Giuseppe Francesco (Pino) Italiano (born March 16, 1961) is an Italian computer scientist.

New!!: Journal of the ACM and Giuseppe F. Italiano · See more »

Gossip protocol

A gossip protocol is a procedure or process of computer-computer communication that is based on the way social networks disseminate information or how epidemics spread.

New!!: Journal of the ACM and Gossip protocol · See more »

Graph homomorphism

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure.

New!!: Journal of the ACM and Graph homomorphism · See more »

Graph isomorphism problem

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

New!!: Journal of the ACM and Graph isomorphism problem · See more »

Graph minor

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.

New!!: Journal of the ACM and Graph minor · See more »

Graph power

In graph theory, a branch of mathematics, the kth power Gk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k.

New!!: Journal of the ACM and Graph power · See more »

Graphic matroid

In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given undirected graph.

New!!: Journal of the ACM and Graphic matroid · See more »

Hagit Attiya

Hagit Attiya is an Israeli computer scientist who holds the Harry W. Labov and Charlotte Ullman Labov Academic Chair of Computer Science at the Technion – Israel Institute of Technology in Haifa, Israel.

New!!: Journal of the ACM and Hagit Attiya · See more »

Hamiltonian completion

The Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian.

New!!: Journal of the ACM and Hamiltonian completion · See more »

Hamiltonian path problem

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected).

New!!: Journal of the ACM and Hamiltonian path problem · See more »

Hardness of approximation

In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems.

New!!: Journal of the ACM and Hardness of approximation · See more »

Harry R. Lewis

Lewis has been honored for his "particularly distinguished contributions to undergraduate teaching"; his students have included future entrepreneurs Bill Gates and Mark Zuckerberg, and numerous future faculty members at Harvard and other schools.

New!!: Journal of the ACM and Harry R. Lewis · See more »

Hilary Putnam

Hilary Whitehall Putnam (July 31, 1926 – March 13, 2016) was an American philosopher, mathematician, and computer scientist, and a major figure in analytic philosophy in the second half of the 20th century.

New!!: Journal of the ACM and Hilary Putnam · See more »

Horn clause

In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form which gives it useful properties for use in logic programming, formal specification, and model theory.

New!!: Journal of the ACM and Horn clause · See more »

Horn-satisfiability

In formal logic, Horn-satisfiability, or HORNSAT, is the problem of deciding whether a given set of propositional Horn clauses is satisfiable or not.

New!!: Journal of the ACM and Horn-satisfiability · See more »

Householder transformation

In linear algebra, a Householder transformation (also known as a Householder reflection or elementary reflector) is a linear transformation that describes a reflection about a plane or hyperplane containing the origin.

New!!: Journal of the ACM and Householder transformation · See more »

Hypertree

In mathematics, a hypergraph H is called a hypertree if it admits a host graph T such that T is a tree.

New!!: Journal of the ACM and Hypertree · See more »

Iacono's working set structure

In computer science, Iacono's working set structure is a comparison based dictionary.

New!!: Journal of the ACM and Iacono's working set structure · See more »

IBM System/360 Model 67

The IBM System/360 Model 67 (S/360-67) was an important IBM mainframe model in the late 1960s.

New!!: Journal of the ACM and IBM System/360 Model 67 · See more »

Imieliński-Lipski algebra

An Imieliński-Lipski algebras is an extension of relational algebra onto tables with different types of null values.

New!!: Journal of the ACM and Imieliński-Lipski algebra · See more »

Implicit graph

In the study of graph algorithms, an implicit graph representation (or more simply implicit graph) is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically from some more concise input.

New!!: Journal of the ACM and Implicit graph · See more »

In-place algorithm

In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure.

New!!: Journal of the ACM and In-place algorithm · See more »

Independent set (graph theory)

In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent.

New!!: Journal of the ACM and Independent set (graph theory) · See more »

Indexed grammar

Indexed grammars are a generalization of context-free grammars in that nonterminals are equipped with lists of flags, or index symbols.

New!!: Journal of the ACM and Indexed grammar · See more »

Indexed language

Indexed languages are a class of formal languages discovered by Alfred Aho; they are described by indexed grammars and can be recognized by nested stack automata.

New!!: Journal of the ACM and Indexed language · See more »

Informatics General

Informatics General Corporation, earlier Informatics, Inc., was an American computer software company in existence from 1962 through 1985 and based in Los Angeles, California.

New!!: Journal of the ACM and Informatics General · See more »

Integer sorting

In computer science, integer sorting is the algorithmic problem of sorting a collection of data values by numeric keys, each of which is an integer.

New!!: Journal of the ACM and Integer sorting · See more »

Iterative refinement

Iterative refinement is an iterative method proposed by James H. Wilkinson to improve the accuracy of numerical solutions to systems of linear equations.

New!!: Journal of the ACM and Iterative refinement · See more »

James B. Saxe

James Benjamin Saxe is an American computer scientist who has worked for many years at the DEC Systems Research Center and its successors, the Compaq Systems Research Center and the Systems Research Center of HP Labs.

New!!: Journal of the ACM and James B. Saxe · See more »

Jan Bergstra

Johannes Aldert "Jan" Bergstra (born 1951) is a Dutch computer scientist.

New!!: Journal of the ACM and Jan Bergstra · See more »

János Komlós (mathematician)

János Komlós (Budapest, 23 May 1942) is a Hungarian-American mathematician, working in probability theory and discrete mathematics.

New!!: Journal of the ACM and János Komlós (mathematician) · See more »

Jeannette Wing

Jeannette Marie Wing is Avanessians Director of the Data Sciences Institute at Columbia University, where she is also a professor of computer science.

New!!: Journal of the ACM and Jeannette Wing · See more »

Job shop scheduling

Job shop scheduling or the job-shop problem (JSP) is an optimization problem in computer science and operations research in which jobs are assigned to resources at particular times.

New!!: Journal of the ACM and Job shop scheduling · See more »

Joel Hass

Joel Hass is an American mathematician, a professor of mathematics and chair of the mathematics department at the University of California, Davis.

New!!: Journal of the ACM and Joel Hass · See more »

John Alan Robinson

John Alan Robinson (9 March 1930 – 5 August 2016) was a philosopher, mathematician, and computer scientist.

New!!: Journal of the ACM and John Alan Robinson · See more »

John C. Reynolds

John Charles Reynolds (June 1, 1935 – April 28, 2013) was an American computer scientist.

New!!: Journal of the ACM and John C. Reynolds · See more »

Johnson's algorithm

Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in a sparse, edge-weighted, directed graph.

New!!: Journal of the ACM and Johnson's algorithm · See more »

Johnson–Lindenstrauss lemma

In mathematics, the Johnson–Lindenstrauss lemma is a result named after William B. Johnson and Joram Lindenstrauss concerning low-distortion embeddings of points from high-dimensional into low-dimensional Euclidean space.

New!!: Journal of the ACM and Johnson–Lindenstrauss lemma · See more »

Joseph Halpern

Joseph Yehuda Halpern (born 1953) is a professor of computer science at Cornell University.

New!!: Journal of the ACM and Joseph Halpern · See more »

Joseph Seffi Naor

Joseph Seffi Naor (פרופ' ספי נאור) is an Israeli professor of computer science and an author of over 200 peer-reviewed articles which were published in such journals as Journal of the ACM, IEEE Transactions on Pattern Analysis and Machine Intelligence and SIAM Journal on Computing among others.

New!!: Journal of the ACM and Joseph Seffi Naor · See more »

Julia Chuzhoy

Julia Chuzhoy is an Israeli mathematician and computer scientist at the Toyota Technological Institute at Chicago, known for her research on approximation algorithms and graph theory.

New!!: Journal of the ACM and Julia Chuzhoy · See more »

K-independent hashing

In computer science, a family of hash functions is said to be k-independent or k-universal if selecting a function at random from the family guarantees that the hash codes of any designated k keys are independent random variables (see precise mathematical definitions below).

New!!: Journal of the ACM and K-independent hashing · See more »

K-minimum spanning tree

The -minimum spanning tree problem, studied in theoretical computer science, asks for a tree of minimum cost that has exactly vertices and forms a subgraph of a larger graph.

New!!: Journal of the ACM and K-minimum spanning tree · See more »

Karloff–Zwick algorithm

The Karloff–Zwick algorithm, in computational complexity theory, is a randomised approximation algorithm taking an instance of MAX-3SAT Boolean satisfiability problem as input.

New!!: Journal of the ACM and Karloff–Zwick algorithm · See more »

Kenneth L. Clarkson

Kenneth Lee Clarkson is an American computer scientist known for his research in computational geometry.

New!!: Journal of the ACM and Kenneth L. Clarkson · See more »

Kuratowski's theorem

In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski.

New!!: Journal of the ACM and Kuratowski's theorem · See more »

L/poly

In computational complexity theory, L/poly is the complexity class of logarithmic space machines with a polynomial amount of advice.

New!!: Journal of the ACM and L/poly · See more »

Larry Stockmeyer

Larry Joseph Stockmeyer (1948 – 31 July 2004) was an American computer scientist.

New!!: Journal of the ACM and Larry Stockmeyer · See more »

Lempel–Ziv–Storer–Szymanski

Lempel–Ziv–Storer–Szymanski (LZSS) is a lossless data compression algorithm, a derivative of LZ77, that was created in 1982 by James Storer and Thomas Szymanski.

New!!: Journal of the ACM and Lempel–Ziv–Storer–Szymanski · See more »

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name line graph comes from a paper by although both and used the construction before this.

New!!: Journal of the ACM and Line graph · See more »

Linear congruential generator

A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation.

New!!: Journal of the ACM and Linear congruential generator · See more »

Link/cut tree

A link/cut tree is a data structure for representing a forest, a set of rooted trees, and offers the following operations.

New!!: Journal of the ACM and Link/cut tree · See more »

Linkless embedding

In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into Euclidean space in such a way that no two cycles of the graph are linked.

New!!: Journal of the ACM and Linkless embedding · See more »

List of computer science journals

Below is a list of computer science journals.

New!!: Journal of the ACM and List of computer science journals · See more »

List of important publications in computer science

This is a list of important publications in computer science, organized by field.

New!!: Journal of the ACM and List of important publications in computer science · See more »

List of important publications in concurrent, parallel, and distributed computing

This is a list of important publications in concurrent, parallel, and distributed computing, organized by field.

New!!: Journal of the ACM and List of important publications in concurrent, parallel, and distributed computing · See more »

List of important publications in theoretical computer science

This is a list of important publications in theoretical computer science, organized by field.

New!!: Journal of the ACM and List of important publications in theoretical computer science · See more »

List of scientific journals

The following is a partial list of scientific journals.

New!!: Journal of the ACM and List of scientific journals · See more »

Longest common subsequence problem

The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences).

New!!: Journal of the ACM and Longest common subsequence problem · See more »

Longest palindromic substring

In computer science, the longest palindromic substring or longest symmetric factor problem is the problem of finding a maximum-length contiguous substring of a given string that is also a palindrome.

New!!: Journal of the ACM and Longest palindromic substring · See more »

Longest path problem

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph.

New!!: Journal of the ACM and Longest path problem · See more »

Loopless algorithm

In computational combinatorics, a loopless algorithm or loopless imperative algorithm is an imperative algorithm that generates successive combinatorial objects, such as partitions, permutations, and combinations, in constant time and the first object in linear time.

New!!: Journal of the ACM and Loopless algorithm · See more »

LP-type problem

In the study of algorithms, an LP-type problem (also called a generalized linear program) is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms.

New!!: Journal of the ACM and LP-type problem · See more »

M/M/1 queue

In queueing theory, a discipline within the mathematical theory of probability, an M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times have an exponential distribution.

New!!: Journal of the ACM and M/M/1 queue · See more »

M/M/c queue

In queueing theory, a discipline within the mathematical theory of probability, the M/M/c queue (or Erlang–C model) is a multi-server queueing model.

New!!: Journal of the ACM and M/M/c queue · See more »

Manuel Blum

Manuel Blum (Caracas, 26 April 1938) is a Venezuelan computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".

New!!: Journal of the ACM and Manuel Blum · See more »

Map graph

In graph theory, a branch of mathematics, a map graph is an undirected graph formed as the intersection graph of finitely many simply connected and internally disjoint regions of the Euclidean plane.

New!!: Journal of the ACM and Map graph · See more »

Marvin Stein (computer scientist)

Marvin Stein (1924-2015) was a mathematician and computer scientist, and the "father of computer science" at the University of Minnesota.

New!!: Journal of the ACM and Marvin Stein (computer scientist) · See more »

Massachusetts Computer Associates

Massachusetts Computer Associates, also known as COMPASS, was a software company based in Wakefield, Massachusetts from approximately 1961 to 1987, focusing primarily on programming language design and implementation, especially source-to-source transformation.

New!!: Journal of the ACM and Massachusetts Computer Associates · See more »

Matching (graph theory)

In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices.

New!!: Journal of the ACM and Matching (graph theory) · See more »

Matroid parity problem

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid.

New!!: Journal of the ACM and Matroid parity problem · See more »

Matthew K. Franklin

Matthew Keith "Matt" Franklin is an American cryptographer, and a professor of computer science at the University of California, Davis.

New!!: Journal of the ACM and Matthew K. Franklin · See more »

Maxima of a point set

In computational geometry, a point in a finite set of points is said to be maximal or non-dominated if there is no other point in whose coordinates are all greater than or equal to the corresponding coordinates of.

New!!: Journal of the ACM and Maxima of a point set · See more »

Maximum cut

For a graph, a maximum cut is a cut whose size is at least the size of any other cut.

New!!: Journal of the ACM and Maximum cut · See more »

Maximum flow problem

In optimization theory, maximum flow problems involve finding a feasible flow through a single-source, single-sink flow network that is maximum.

New!!: Journal of the ACM and Maximum flow problem · See more »

Mean value analysis

In queueing theory, a discipline within the mathematical theory of probability, mean value analysis (MVA) is a recursive technique for computing expected queue lengths, waiting time at queueing nodes and throughput in equilibrium for a closed separable system of queues.

New!!: Journal of the ACM and Mean value analysis · See more »

Median graph

In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest paths between each pair of a, b, and c. The concept of median graphs has long been studied, for instance by or (more explicitly) by, but the first paper to call them "median graphs" appears to be.

New!!: Journal of the ACM and Median graph · See more »

Michael J. Fischer

Michael John Fischer (born 1942) is a computer scientist who works in the fields of distributed computing, parallel computing, cryptography, algorithms and data structures, and computational complexity.

New!!: Journal of the ACM and Michael J. Fischer · See more »

Mihalis Yannakakis

Mihalis Yannakakis (Μιχάλης Γιαννακάκης; born 13 September 1953 in Athens, Greece) (accessed 12 November 2009) is Professor of Computer Science at Columbia University.

New!!: Journal of the ACM and Mihalis Yannakakis · See more »

Mikkel Thorup

Mikkel Thorup (born 1965) is a Danish computer scientist jointly affiliated at AT&T Labs in Florham Park, New Jersey, United States and at Copenhagen University.

New!!: Journal of the ACM and Mikkel Thorup · See more »

Minimum spanning tree

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted (un)directed graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

New!!: Journal of the ACM and Minimum spanning tree · See more »

Minimum-weight triangulation

In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length.

New!!: Journal of the ACM and Minimum-weight triangulation · See more »

Naive Bayes classifier

In machine learning, naive Bayes classifiers are a family of simple "probabilistic classifiers" based on applying Bayes' theorem with strong (naive) independence assumptions between the features.

New!!: Journal of the ACM and Naive Bayes classifier · See more »

Naor–Reingold pseudorandom function

In 1997, Moni Naor and Omer Reingold described efficient constructions for various cryptographic primitives in private key as well as public-key cryptography.

New!!: Journal of the ACM and Naor–Reingold pseudorandom function · See more »

Nathan Netanyahu

Nathan S. Netanyahu (נָתָן נְתַנְיָהוּ; born 28 November 1951) is an Israeli computer scientist, a professor of computer science at Bar-Ilan University.

New!!: Journal of the ACM and Nathan Netanyahu · See more »

Needleman–Wunsch algorithm

The Needleman–Wunsch algorithm is an algorithm used in bioinformatics to align protein or nucleotide sequences.

New!!: Journal of the ACM and Needleman–Wunsch algorithm · See more »

Neighbourhood (graph theory)

In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge.

New!!: Journal of the ACM and Neighbourhood (graph theory) · See more »

Nested stack automaton

In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks.

New!!: Journal of the ACM and Nested stack automaton · See more »

Newman's lemma

In mathematics, in the theory of rewriting systems, Newman's lemma, also commonly called the diamond lemma, states that a terminating (or strongly normalizing) abstract rewriting system (ARS), that is, one in which there are no infinite reduction sequences, is confluent if it is locally confluent.

New!!: Journal of the ACM and Newman's lemma · See more »

Nimrod Megiddo

Nimrod Megiddo (נמרוד מגידו) is a mathematician and computer scientist.

New!!: Journal of the ACM and Nimrod Megiddo · See more »

Nondeterministic algorithm

In computer science, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm.

New!!: Journal of the ACM and Nondeterministic algorithm · See more »

Null (SQL)

Null (or NULL) is a special marker used in Structured Query Language to indicate that a data value does not exist in the database.

New!!: Journal of the ACM and Null (SQL) · See more »

Omer Reingold

Omer Reingold (עומר ריינגולד) is a faculty member of the Computer Science Department at Stanford University.

New!!: Journal of the ACM and Omer Reingold · See more »

Open-shop scheduling

In theoretical computer science and operations research, the open-shop scheduling problem (OSSP) is a scheduling problem in which a given set of jobs must each be processed for given amounts of time at each of a given set of workstations, in an arbitrary order, and the goal is to determine the time at which each job is to be processed at each workstation.

New!!: Journal of the ACM and Open-shop scheduling · See more »

Order-maintenance problem

In computer science, the order-maintenance problem involves maintaining a totally ordered set supporting the following operations.

New!!: Journal of the ACM and Order-maintenance problem · See more »

Otakar Borůvka

Otakar Borůvka (10 May 1899 in Uherský Ostroh – 22 July 1995 in Brno) was a Czech mathematician best known today for his work in graph theory, long before this was an established mathematical discipline.

New!!: Journal of the ACM and Otakar Borůvka · See more »

Outerplanar graph

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

New!!: Journal of the ACM and Outerplanar graph · See more »

Package-merge algorithm

The package-merge algorithm is an O(nL)-time algorithm for finding an optimal length-limited Huffman code for a given distribution on a given alphabet of size n, where no code word is longer than L. It is a greedy algorithm, and a generalization of Huffman's original algorithm.

New!!: Journal of the ACM and Package-merge algorithm · See more »

Parallel computation thesis

In computational complexity theory, the parallel computation thesis is a hypothesis which states that the time used by a (reasonable) parallel machine is polynomially related to the space used by a sequential machine.

New!!: Journal of the ACM and Parallel computation thesis · See more »

Parametric search

In the design and analysis of algorithms for combinatorial optimization, parametric search is a technique invented by for transforming a decision algorithm (does this optimization problem have a solution with quality better than some given threshold?) into an optimization algorithm (find the best solution).

New!!: Journal of the ACM and Parametric search · See more »

Patrick C. Fischer

Patrick Carl Fischer (December 3, 1935 – August 26, 2011) was an American computer scientist, a noted researcher in computational complexity theory and database theory, and a target of the Unabomber.

New!!: Journal of the ACM and Patrick C. Fischer · See more »

Paxos (computer science)

Paxos is a family of protocols for solving consensus in a network of unreliable processors.

New!!: Journal of the ACM and Paxos (computer science) · See more »

PCP theorem

In computational complexity theory, the PCP theorem (also known as the PCP characterization theorem) states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomized algorithm) of constant query complexity and logarithmic randomness complexity (uses a logarithmic number of random bits).

New!!: Journal of the ACM and PCP theorem · See more »

Penny graph

In geometric graph theory, a penny graph is a contact graph of unit circles.

New!!: Journal of the ACM and Penny graph · See more »

Perfect hash function

In computer science, a perfect hash function for a set is a hash function that maps distinct elements in to a set of integers, with no collisions.

New!!: Journal of the ACM and Perfect hash function · See more »

Permanent (mathematics)

In linear algebra, the permanent of a square matrix is a function of the matrix similar to the determinant.

New!!: Journal of the ACM and Permanent (mathematics) · See more »

Permutation pattern

In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation.

New!!: Journal of the ACM and Permutation pattern · See more »

Peter B. Andrews

Peter Bruce Andrews (born 1937) is an American mathematician and Professor of Mathematics, Emeritus at Carnegie Mellon University in Pittsburgh, Pennsylvania, and the creator of the mathematical logic Q0.

New!!: Journal of the ACM and Peter B. Andrews · See more »

Peter Landin

Peter John Landin (5 June 1930, Sheffield – 3 June 2009) was a British computer scientist.

New!!: Journal of the ACM and Peter Landin · See more »

Peter Sanders (computer scientist)

Peter Sanders (born 1967) is a German computer scientist who works as a professor of computer science at the Karlsruhe Institute of Technology.

New!!: Journal of the ACM and Peter Sanders (computer scientist) · See more »

Planar cover

In graph theory, a planar cover of a finite graph G is a finite covering graph of G that is itself a planar graph.

New!!: Journal of the ACM and Planar cover · See more »

Planar separator theorem

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices.

New!!: Journal of the ACM and Planar separator theorem · See more »

Planarity testing

In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections).

New!!: Journal of the ACM and Planarity testing · See more »

Polynomial identity testing

In mathematics, polynomial identity testing (PIT) is the problem of efficiently determining whether two multivariate polynomials are identical.

New!!: Journal of the ACM and Polynomial identity testing · See more »

Power domains

In denotational semantics and domain theory, power domains are domains of nondeterministic and concurrent computations.

New!!: Journal of the ACM and Power domains · See more »

Prabhakar Raghavan

Prabhakar Raghavan is a Vice President of Engineering at Google.

New!!: Journal of the ACM and Prabhakar Raghavan · See more »

Predecessor problem

In computer science, the predecessor problem involves maintaining a set of items to, given an element, efficiently query which element precedes or succeeds that element in an order.

New!!: Journal of the ACM and Predecessor problem · See more »

Prefix sum

In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers is a second sequence of numbers, the sums of prefixes (running totals) of the input sequence: For instance, the prefix sums of the natural numbers are the triangular numbers: |- !input numbers | 1 || 2 || 3 || 4 || 5 || 6 ||...

New!!: Journal of the ACM and Prefix sum · See more »

Priority queue

In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it.

New!!: Journal of the ACM and Priority queue · See more »

Probabilistically checkable proof

In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof.

New!!: Journal of the ACM and Probabilistically checkable proof · See more »

Processor sharing

Processor sharing or egalitarian processor sharing is a service policy where the customers, clients or jobs are all served simultaneously, each receiving an equal fraction of the service capacity available.

New!!: Journal of the ACM and Processor sharing · See more »

Product-form solution

In probability theory, a product-form solution is a particularly efficient form of solution for determining some metric of a system with distinct sub-components, where the metric for the collection of components can be written as a product of the metric across the different components.

New!!: Journal of the ACM and Product-form solution · See more »

Pseudorandom function family

In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish (with significant advantage) between a function chosen randomly from the PRF family and a random oracle (a function whose outputs are fixed completely at random).

New!!: Journal of the ACM and Pseudorandom function family · See more »

QMA

In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the quantum analog of the nonprobabilistic complexity class NP or the probabilistic complexity class MA.

New!!: Journal of the ACM and QMA · See more »

Queueing theory

Queueing theory is the mathematical study of waiting lines, or queues.

New!!: Journal of the ACM and Queueing theory · See more »

Rajeev Motwani

Rajeev Motwani (राजीव मोटवानी; March 26, 1962 – June 5, 2009) was a professor of Computer Science at Stanford University whose research focused on theoretical computer science.

New!!: Journal of the ACM and Rajeev Motwani · See more »

Random projection

In mathematics and statistics, random projection is a technique used to reduce the dimensionality of a set of points which lie in Euclidean space.

New!!: Journal of the ACM and Random projection · See more »

Randomized algorithm

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.

New!!: Journal of the ACM and Randomized algorithm · See more »

Raphael Rom

Raphael "Raphi" Rom is an Israeli computer scientist working at Technion – Israel Institute of Technology.

New!!: Journal of the ACM and Raphael Rom · See more »

Raymond Reiter

Raymond Reiter (June 12, 1939 – September 16, 2002), was a Canadian computer scientist and logician.

New!!: Journal of the ACM and Raymond Reiter · See more »

Reachability

In graph theory, reachability refers to the ability to get from one vertex to another within a graph.

New!!: Journal of the ACM and Reachability · See more »

Read-once function

In mathematics, a read-once function is a special type of Boolean function that can be described by a Boolean expression in which each variable appears only once.

New!!: Journal of the ACM and Read-once function · See more »

Relative neighborhood graph

In computational geometry, the relative neighborhood graph (RNG) is an undirected graph defined on a set of points in the Euclidean plane by connecting two points p and q by an edge whenever there does not exist a third point r that is closer to both p and q than they are to each other.

New!!: Journal of the ACM and Relative neighborhood graph · See more »

Replicator (cellular automaton)

In cellular automata, a replicator is a pattern that produces copies of itself.

New!!: Journal of the ACM and Replicator (cellular automaton) · See more »

Resolution (logic)

In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation theorem-proving technique for sentences in propositional logic and first-order logic.

New!!: Journal of the ACM and Resolution (logic) · See more »

Richard Weber (mathematician)

Richard Robert Weber (born 25 February 1953) is a mathematician working in operational research.

New!!: Journal of the ACM and Richard Weber (mathematician) · See more »

Robert Kowalski

Robert Anthony "Bob" Kowalski (born 15 May 1941) is a logician and computer scientist, who has spent most of his career in the United Kingdom.

New!!: Journal of the ACM and Robert Kowalski · See more »

Robertson–Seymour theorem

In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering.

New!!: Journal of the ACM and Robertson–Seymour theorem · See more »

Rotation map

In mathematics, a rotation map is a function that represents an undirected edge-labeled graph, where each vertex enumerates its outgoing neighbors.

New!!: Journal of the ACM and Rotation map · See more »

Rule 90

In the mathematical study of cellular automata, Rule 90 is an elementary cellular automaton based on the exclusive or function.

New!!: Journal of the ACM and Rule 90 · See more »

Ruth Silverman

Ruth Silverman (born 1936 or 1937, died April 25, 2011) was an American mathematician and computer scientist known for her research in computational geometry.

New!!: Journal of the ACM and Ruth Silverman · See more »

S. L. Hakimi

Seifollah Louis Hakimi (1932 – June 23, 2005) was an Iranian-American mathematician born in Iran, a professor emeritus at Northwestern University, where he chaired the department of electrical engineering from 1973 to 1978.

New!!: Journal of the ACM and S. L. Hakimi · See more »

Sauer–Shelah lemma

In combinatorial mathematics and extremal set theory, the Sauer–Shelah lemma states that every family of sets with small VC dimension consists of a small number of sets.

New!!: Journal of the ACM and Sauer–Shelah lemma · See more »

Science and technology in Venezuela

Science and technology in Venezuela includes research based on exploring Venezuela's diverse ecology and the lives of its indigenous peoples.

New!!: Journal of the ACM and Science and technology in Venezuela · See more »

Sentence extraction

Sentence extraction is a technique used for automatic summarization of a text.

New!!: Journal of the ACM and Sentence extraction · See more »

Series-parallel graph

In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations.

New!!: Journal of the ACM and Series-parallel graph · See more »

Set cover problem

The set cover problem is a classical question in combinatorics, computer science and complexity theory.

New!!: Journal of the ACM and Set cover problem · See more »

Set splitting problem

In computational complexity theory, the Set Splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S1 or S2.

New!!: Journal of the ACM and Set splitting problem · See more »

Sethi–Ullman algorithm

In computer science, the Sethi–Ullman algorithm is an algorithm named after Ravi Sethi and Jeffrey D. Ullman, its inventors, for translating abstract syntax trees into machine code that uses as few registers as possible.

New!!: Journal of the ACM and Sethi–Ullman algorithm · See more »

Shafi Goldwasser

Shafrira Goldwasser (שפרירה גולדווסר; born 1959) is an American-Israeli computer scientist and winner of the Turing Award in 2012.

New!!: Journal of the ACM and Shafi Goldwasser · See more »

Shannon switching game

The Shannon switching game is an abstract strategy game for two players, invented by American mathematician and electrical engineer Claude Shannon, the "father of information theory" some time before 1951.

New!!: Journal of the ACM and Shannon switching game · See more »

SHARE Operating System

The SHARE Operating System (SOS) was created in 1959 as an improvement on the General Motors GM-NAA I/O operating system, the first operating system, by the SHARE user group.

New!!: Journal of the ACM and SHARE Operating System · See more »

Sheila Greibach

Sheila Adele Greibach (born 6 October 1939 in New York City) is a researcher in formal languages in computing, automata, compiler theory (in particular), and computer science.

New!!: Journal of the ACM and Sheila Greibach · See more »

Shellsort

Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort.

New!!: Journal of the ACM and Shellsort · See more »

Situation calculus

The situation calculus is a logic formalism designed for representing and reasoning about dynamical domains.

New!!: Journal of the ACM and Situation calculus · See more »

SL (complexity)

In computational complexity theory, SL (Symmetric Logspace or Sym-L) is the complexity class of problems log-space reducible to USTCON (undirected s-t connectivity), which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same connected component.

New!!: Journal of the ACM and SL (complexity) · See more »

Soft heap

In computer science, a soft heap is a variant on the simple heap data structure that has constant amortized time for 5 types of operations.

New!!: Journal of the ACM and Soft heap · See more »

Soundex

Soundex is a phonetic algorithm for indexing names by sound, as pronounced in English.

New!!: Journal of the ACM and Soundex · See more »

Splay tree

A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again.

New!!: Journal of the ACM and Splay tree · See more »

Spline (mathematics)

In mathematics, a spline is a function defined piecewise by polynomials.

New!!: Journal of the ACM and Spline (mathematics) · See more »

Split (graph theory)

In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph.

New!!: Journal of the ACM and Split (graph theory) · See more »

Stack-sortable permutation

In mathematics and computer science, a stack-sortable permutation (also called a tree permutation) is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure.

New!!: Journal of the ACM and Stack-sortable permutation · See more »

Star-shaped polygon

A star-shaped polygon is a polygonal region in the plane that is a star domain, that is, a polygon that contains a point from which the entire polygon boundary is visible.

New!!: Journal of the ACM and Star-shaped polygon · See more »

Steven Muchnick

Steven Stanley Muchnick is a noted computer science researcher, best known as author of the 1997 treatise on compilers, "Advanced Compiler Design and Implementation.".

New!!: Journal of the ACM and Steven Muchnick · See more »

Strong NP-completeness

In computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness.

New!!: Journal of the ACM and Strong NP-completeness · See more »

Structured program theorem

The structured program theorem, also called Böhm-Jacopini theorem, is a result in programming language theory.

New!!: Journal of the ACM and Structured program theorem · See more »

Subgraph isomorphism problem

In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H. Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete.

New!!: Journal of the ACM and Subgraph isomorphism problem · See more »

Subset sum problem

In computer science, the subset sum problem is an important problem in complexity theory and cryptography.

New!!: Journal of the ACM and Subset sum problem · See more »

Suffix tree

In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values.

New!!: Journal of the ACM and Suffix tree · See more »

Sum of radicals

In computational complexity theory, there is an open problem of whether some information about a sum of radicals may be computed in polynomial time depending on the input size, i.e., in the number of bits necessary to represent this sum.

New!!: Journal of the ACM and Sum of radicals · See more »

Super-prime

Super-prime numbers (also known as higher-order primes or prime-indexed primes) are the subsequence of prime numbers that occupy prime-numbered positions within the sequence of all prime numbers.

New!!: Journal of the ACM and Super-prime · See more »

Symmetric Turing machine

A symmetric Turing machine is a Turing machine which has a configuration graph that is undirected (that is, configuration i yields configuration j if and only if j yields i).

New!!: Journal of the ACM and Symmetric Turing machine · See more »

Tabulation hashing

In computer science, tabulation hashing is a method for constructing universal families of hash functions by combining table lookup with exclusive or operations.

New!!: Journal of the ACM and Tabulation hashing · See more »

Takao Nishizeki

is a Japanese mathematician and computer scientist who specializes in graph algorithms and graph drawing.

New!!: Journal of the ACM and Takao Nishizeki · See more »

Tarjan's off-line lowest common ancestors algorithm

In computer science, Tarjan's off-line lowest common ancestors algorithm is an algorithm for computing lowest common ancestors for pairs of nodes in a tree, based on the union-find data structure.

New!!: Journal of the ACM and Tarjan's off-line lowest common ancestors algorithm · See more »

Teofilo F. Gonzalez

Teofilo Francisco Gonzalez Arce (born January 26, 1948 in Monterrey, Mexico) is a Mexican-American computer scientist who is professor emeritus of computer science at the University of California, Santa Barbara.

New!!: Journal of the ACM and Teofilo F. Gonzalez · See more »

Theoretical computer science

Theoretical computer science, or TCS, is a subset of general computer science and mathematics that focuses on more mathematical topics of computing and includes the theory of computation.

New!!: Journal of the ACM and Theoretical computer science · See more »

Timeline of computational mathematics

This is a timeline of key developments in computational mathematics.

New!!: Journal of the ACM and Timeline of computational mathematics · See more »

Timeline of numerical analysis after 1945

The following is a timeline of numerical analysis after 1945, and deals with developments after the invention of the modern electronic computer, which began during Second World War.

New!!: Journal of the ACM and Timeline of numerical analysis after 1945 · See more »

Timeline of scientific computing

The following is a timeline of scientific computing, also known as computational science.

New!!: Journal of the ACM and Timeline of scientific computing · See more »

Tomasz Imieliński

Tomasz Imieliński (born July 11, 1954 in Toruń, Poland) is a Polish-American computer scientist, most known in the areas of data mining, mobile computing, data extraction, and search engine technology.

New!!: Journal of the ACM and Tomasz Imieliński · See more »

Transitive reduction

In mathematics, a transitive reduction of a directed graph D is another directed graph with the same vertices and as few edges as possible, such that if there is a (directed) path from vertex v to vertex w in D, then there is also such a path in the reduction.

New!!: Journal of the ACM and Transitive reduction · See more »

Travelling salesman problem

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

New!!: Journal of the ACM and Travelling salesman problem · See more »

Tree-depth

In graph theory, the tree-depth of a connected undirected graph G is a numerical invariant of G, the minimum height of a Trémaux tree for a supergraph of G. This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages.

New!!: Journal of the ACM and Tree-depth · See more »

Treewidth

In graph theory, the treewidth of an undirected graph is a number associated with the graph.

New!!: Journal of the ACM and Treewidth · See more »

Trigonometric tables

In mathematics, tables of trigonometric functions are useful in a number of areas.

New!!: Journal of the ACM and Trigonometric tables · See more »

Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

New!!: Journal of the ACM and Turing machine · See more »

Ukkonen's algorithm

In computer science, Ukkonen's algorithm is a linear-time, online algorithm for constructing suffix trees, proposed by Esko Ukkonen in 1995.

New!!: Journal of the ACM and Ukkonen's algorithm · See more »

Unary numeral system

The unary numeral system is the bijective base-1 numeral system.

New!!: Journal of the ACM and Unary numeral system · See more »

Unique games conjecture

In computational complexity theory, the unique games conjecture is a conjecture made by Subhash Khot in 2002.

New!!: Journal of the ACM and Unique games conjecture · See more »

Unknotting problem

In mathematics, the unknotting problem is the problem of algorithmically recognizing the unknot, given some representation of a knot, e.g., a knot diagram.

New!!: Journal of the ACM and Unknotting problem · See more »

Urquhart graph

In computational geometry, the Urquhart graph of a set of points in the plane, named after Roderick B. Urquhart, is obtained by removing the longest edge from each triangle in the Delaunay triangulation.

New!!: Journal of the ACM and Urquhart graph · See more »

Valerie King

Valerie King is an American and Canadian computer scientist who works as a professor at the University of Victoria.

New!!: Journal of the ACM and Valerie King · See more »

Vertex cover

In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.

New!!: Journal of the ACM and Vertex cover · See more »

Vertex cycle cover

In mathematics, a vertex cycle cover (commonly called simply cycle cover) of a graph G is a set of cycles which are subgraphs of G and contain all vertices of G. If the cycles of the cover have no vertices in common, the cover is called vertex-disjoint or sometimes simply disjoint cycle cover.

New!!: Journal of the ACM and Vertex cycle cover · See more »

Victor Vianu

Victor Vianu is a computer scientist, a professor of computer science and engineering at the University of California, San Diego, UCSD, retrieved 2011-03-21.

New!!: Journal of the ACM and Victor Vianu · See more »

Wayne Snyder

Wayne Snyder is an associate professor at Boston University known for his work in E-unification theory.

New!!: Journal of the ACM and Wayne Snyder · See more »

Wiener index

In chemical graph theory, the Wiener index (also Wiener number) introduced by Harry Wiener, is a topological index of a molecule, defined as the sum of the lengths of the shortest paths between all pairs of vertices in the chemical graph representing the non-hydrogen atoms in the molecule.

New!!: Journal of the ACM and Wiener index · See more »

Work stealing

In parallel computing, work stealing is a scheduling strategy for multithreaded computer programs.

New!!: Journal of the ACM and Work stealing · See more »

Xuong tree

In graph theory, a Xuong tree is a spanning tree T of a given graph G with the property that, in the remaining graph G-T, the number of connected components with an odd number of edges is as small as possible.

New!!: Journal of the ACM and Xuong tree · See more »

Zig-zag product

In graph theory, the zig-zag product of regular graphs G,H, denoted by G \circ H, takes a large graph (G) and a small graph (H), and produces a graph that approximately inherits the size of the large one but the degree of the small one.

New!!: Journal of the ACM and Zig-zag product · See more »

2-satisfiability

In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables.

New!!: Journal of the ACM and 2-satisfiability · See more »

Redirects here:

J ACM, J. ACM, JACM, Journal of the ACM (JACM), Journal of the Association for Computing Machinery.

References

[1] https://en.wikipedia.org/wiki/Journal_of_the_ACM

Unionpedia is a concept map or semantic network organized like an encyclopedia – dictionary. It gives a brief definition of each concept and its relationships.

This is a giant online mental map that serves as a basis for concept diagrams. It's free to use and each article or document can be downloaded. It's a tool, resource or reference for study, research, education, learning or teaching, that can be used by teachers, educators, pupils or students; for the academic world: for school, primary, secondary, high school, middle, technical degree, college, university, undergraduate, master's or doctoral degrees; for papers, reports, projects, ideas, documentation, surveys, summaries, or thesis. Here is the definition, explanation, description, or the meaning of each significant on which you need information, and a list of their associated concepts as a glossary. Available in English, Spanish, Portuguese, Japanese, Chinese, French, German, Italian, Polish, Dutch, Russian, Arabic, Hindi, Swedish, Ukrainian, Hungarian, Catalan, Czech, Hebrew, Danish, Finnish, Indonesian, Norwegian, Romanian, Turkish, Vietnamese, Korean, Thai, Greek, Bulgarian, Croatian, Slovak, Lithuanian, Filipino, Latvian, Estonian and Slovenian. More languages soon.

All the information was extracted from Wikipedia, and it's available under the Creative Commons Attribution-ShareAlike License.

Unionpedia is not endorsed by or affiliated with the Wikimedia Foundation.

Google Play, Android and the Google Play logo are trademarks of Google Inc.

Privacy Policy

OutgoingIncoming