Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: Computational complexity of mathematical operations (view), Computational complexity of matrix multiplication (view), Computational complexity theory (view), Electronic Colloquium on Computational Complexity (view), Asymptotic computational complexity (view), Computational Complexity Conference (view), Implicit computational complexity (view)

searching for Computational complexity 156 found (1560 total)

alternate case: computational complexity

Filter design (3,300 words) [view diff] exact match in snippet view article find links to article

filter required? Finite (in duration) impulse response required? Computational complexity Technology The required frequency response is an important parameter

Empirical risk minimization (1,626 words) [view diff] no match in snippet view article find links to article

Empirical risk minimization is a principle in statistical learning theory which defines a family of learning algorithms based on evaluating performance

Go and mathematics (1,714 words) [view diff] exact match in snippet view article find links to article

use in Go). Generalized Go is played on n × n boards, and the computational complexity of determining the winner in a given position of generalized Go

Polygon triangulation (1,386 words) [view diff] no match in snippet view article find links to article

In computational geometry, polygon triangulation is the partition of a polygonal area (simple polygon) P into a set of triangles, i.e., finding a set of

Probabilistic analysis of algorithms (303 words) [view diff] exact match in snippet view article find links to article

probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption

Ray tracing (graphics) (7,577 words) [view diff] no match in snippet view article

In 3D computer graphics, ray tracing is a technique for modeling light transport for use in a wide variety of rendering algorithms for generating digital

Threshold theorem (1,056 words) [view diff] no match in snippet view article find links to article

In quantum computing, the threshold theorem (or quantum fault-tolerance theorem) states that a quantum computer with a physical error rate below a certain

Strong duality (259 words) [view diff] case mismatch in snippet view article find links to article

Retrieved October 3, 2011. Manyem, Prabhu (2010). "Duality Gap, Computational Complexity and NP Completeness: A Survey". arXiv:1012.5568 [math.OC].

K-vertex-connected graph (571 words) [view diff] no match in snippet view article find links to article

In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer

Graph coloring (7,988 words) [view diff] exact match in snippet view article find links to article

S2CID 13131049 Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. (1990), "On the computational complexity of the Jones and Tutte polynomials", Mathematical Proceedings of

Knapsack problem (7,661 words) [view diff] no match in snippet view article find links to article

The knapsack problem is the following problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine which items

Rolling hash (2,009 words) [view diff] no match in snippet view article find links to article

A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input

Monadic second-order logic (1,308 words) [view diff] exact match in snippet view article find links to article

equivalent to the inequality of NP and coNP, an open question in computational complexity. By contrast, when we wish to check whether a Boolean MSO formula

Unknotting problem (1,318 words) [view diff] exact match in snippet view article find links to article

in the complexity class P. First steps toward determining the computational complexity were undertaken in proving that the problem is in larger complexity

Triangulation (computer vision) (2,386 words) [view diff] no match in snippet view article

In computer vision, triangulation refers to the process of determining a point in 3D space given its projections onto two, or more, images. In order to

Triangulation (computer vision) (2,386 words) [view diff] no match in snippet view article

In computer vision, triangulation refers to the process of determining a point in 3D space given its projections onto two, or more, images. In order to

Full Rate (697 words) [view diff] exact match in snippet view article find links to article

of development (early 1990s) it was a good compromise between computational complexity and quality, requiring only on the order of a million additions

Minesweeper (video game) (1,935 words) [view diff] no match in snippet view article

Minesweeper is a logic puzzle video game genre generally played on personal computers. The game features a grid of clickable tiles, with hidden "mines"

Least squares inference in phylogeny (698 words) [view diff] exact match in snippet view article find links to article

of phylogenetic trees. Science 155: 279-84. William H.E. Day, Computational complexity of inferring phylogenies from dissimilarity matrices, Bulletin

Cylindrical algebraic decomposition (430 words) [view diff] exact match in snippet view article find links to article

together with an algorithm for computing it. Collins' algorithm has a computational complexity that is double exponential in n. This is an upper bound, which

SBC (codec) (799 words) [view diff] exact match in snippet view article

obtain a reasonably good audio quality at medium bit rates with low computational complexity. As of A2DP version 1.3, the Low Complexity Subband Coding remains

3-subset meet-in-the-middle attack (1,556 words) [view diff] exact match in snippet view article find links to article

another, thus allowing for a basic MITM attack that reduces the computational complexity from 2 112 ( = 2 2 × 56 ) {\displaystyle 2^{112}(=2^{2\times 56})}

Antichain (1,090 words) [view diff] no match in snippet view article find links to article

In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are

G.719 (522 words) [view diff] exact match in snippet view article find links to article

bit-allocation and low complexity lattice vector quantization. The computational complexity is quite low (18 floating-point MIPS) for an efficient high-quality

Parity function (859 words) [view diff] exact match in snippet view article find links to article

number of 2 n − 1 clauses of length n. Some of the earliest work in computational complexity was 1961 bound of Bella Subbotovskaya showing the size of a Boolean

Instance-based learning (292 words) [view diff] exact match in snippet view article find links to article

worst case, a hypothesis is a list of n training items and the computational complexity of classifying a single new instance is O(n). One advantage that

Biclique attack (3,173 words) [view diff] exact match in snippet view article find links to article

2019[update]) the best publicly known single-key attack on AES. The computational complexity of the attack is 2 126.1 {\displaystyle 2^{126.1}} , 2 189.7 {\displaystyle

Disjunctive normal form (2,073 words) [view diff] exact match in snippet view article find links to article

conflicting literals. An important variation used in the study of computational complexity is k-DNF. A formula is in k-DNF if it is in DNF and each conjunction

CA-duality (360 words) [view diff] exact match in snippet view article find links to article

asymptotically anti-de Sitter background corresponds to quantum computational complexity, and that black holes produce complexity at the fastest possible

Mike Paterson (654 words) [view diff] exact match in snippet view article find links to article

publications, especially in the design and analysis of algorithms and computational complexity. Paterson's distinguished career was recognised with the EATCS

Open-shop scheduling (624 words) [view diff] no match in snippet view article find links to article

Open-shop scheduling or open-shop scheduling problem (OSSP) is an optimization problem in computer science and operations research. It is a variant of

Evolutionary algorithm (4,461 words) [view diff] exact match in snippet view article find links to article

most real applications of EAs, computational complexity is a prohibiting factor. In fact, this computational complexity is due to fitness function evaluation

Triangular network coding (451 words) [view diff] exact match in snippet view article find links to article

and decoding computational complexity. While linear encoding and decoding over GF(2) alleviates the concern of high computational complexity, coding over

Levenshtein distance (2,435 words) [view diff] no match in snippet view article find links to article

In information theory, linguistics, and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences

Self-complementary graph (366 words) [view diff] no match in snippet view article find links to article

In the mathematical field of graph theory, a self-complementary graph is a graph which is isomorphic to its complement. The simplest non-trivial self-complementary

List of game theorists (469 words) [view diff] exact match in snippet view article find links to article

bargaining theory, learning and language Thomas Jerome Schaefer – computational complexity of perfect-information games Suzanne Scotchmer – patent law incentive

Extremal optimization (1,490 words) [view diff] exact match in snippet view article find links to article

self-organised critical process. Another piece in the puzzle is work on computational complexity, specifically that critical points have been shown to exist in

Diffie–Hellman problem (909 words) [view diff] no match in snippet view article find links to article

The Diffie–Hellman problem (DHP) is a mathematical problem first proposed by Whitfield Diffie and Martin Hellman in the context of cryptography and serves

Sieve of Atkin (1,995 words) [view diff] no match in snippet view article find links to article

In mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes

TwixT (1,554 words) [view diff] no match in snippet view article find links to article

TwixT is a two-player strategy board game, an early entrant in the 1960s 3M bookshelf game series. It became one of the most popular and enduring games

Chris Umans (593 words) [view diff] exact match in snippet view article find links to article

California Institute of Technology. He is known for work on algorithms, computational complexity, algebraic complexity, and hardness of approximation. Umans studied

Martin Demaine (695 words) [view diff] exact match in snippet view article find links to article

unfolding objects out of flat materials such as paper and on the computational complexity of games and puzzles. Martin and Erik were fans of Martin Gardner

Rush Hour (puzzle) (833 words) [view diff] no match in snippet view article

Rush Hour is a sliding block puzzle invented by Nob Yoshigahara in the 1970s. It was first sold in the United States in 1996. It is now being manufactured

Dissipative particle dynamics (1,678 words) [view diff] exact match in snippet view article find links to article

equilibrium state. A series of new DPD algorithms with reduced computational complexity and better control of transport properties are presented. The algorithms

List of lemmas (522 words) [view diff] no match in snippet view article find links to article

This following is a list of lemmas (or, "lemmata", i.e. minor theorems, or sometimes intermediate technical results factored out of proofs). See also list

Phutball (714 words) [view diff] no match in snippet view article find links to article

Phutball (short for Philosopher's Football) is a two-player abstract strategy board game described in Elwyn Berlekamp, John Horton Conway, and Richard

Kempner function (846 words) [view diff] no match in snippet view article find links to article

In number theory, the Kempner function S ( n ) {\displaystyle S(n)} is defined for a given positive integer n {\displaystyle n} to be the smallest number

Greedy algorithm (1,748 words) [view diff] exact match in snippet view article find links to article

strategy for the travelling salesman problem (which is of high computational complexity) is the following heuristic: "At each step of the journey, visit

Computational indistinguishability (420 words) [view diff] exact match in snippet view article find links to article

In computational complexity and cryptography, two families of distributions are computationally indistinguishable if no efficient algorithm can tell the

Semantic security (821 words) [view diff] exact match in snippet view article find links to article

the message length (and not the ciphertext). This concept is the computational complexity analogue to Shannon's concept of perfect secrecy. Perfect secrecy

Quadratic assignment problem (651 words) [view diff] no match in snippet view article find links to article

The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research

Bipartite matroid (363 words) [view diff] no match in snippet view article find links to article

In mathematics, a bipartite matroid is a matroid all of whose circuits have even size. A uniform matroid U n r {\displaystyle U{}_{n}^{r}} is bipartite

Order dimension (1,205 words) [view diff] no match in snippet view article find links to article

In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial

AC0 (356 words) [view diff] exact match in snippet view article find links to article

polynomial hierarchy and PSPACE. Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. pp. 117–118, 287

Core (graph theory) (399 words) [view diff] no match in snippet view article

In the mathematical field of graph theory, a core is a notion that describes behavior of a graph with respect to graph homomorphisms. Graph C {\displaystyle

G.722.1 (800 words) [view diff] exact match in snippet view article find links to article

using a Modulated Lapped Transform (MLT), a type of MDCT. The computational complexity is quite low (5.5 floating-point MIPS) for an efficient high-quality

Vincent Blondel (706 words) [view diff] exact match in snippet view article find links to article

computer science. He is mostly known for his contributions in computational complexity in control, multi-agent coordination and complex networks. Blondel

Neil Immerman (332 words) [view diff] exact match in snippet view article find links to article

currently applying to research in model checking, database theory, and computational complexity theory. Professor Immerman is an editor of the SIAM Journal on

Quadratic bottleneck assignment problem (224 words) [view diff] no match in snippet view article find links to article

In mathematics, the quadratic bottleneck assignment problem (QBAP) is one of the fundamental combinatorial optimization problems in the branch of optimization

Closest pair of points problem (1,210 words) [view diff] exact match in snippet view article find links to article

that were treated at the origins of the systematic study of the computational complexity of geometric algorithms. Randomized algorithms that solve the problem

English draughts (2,515 words) [view diff] no match in snippet view article find links to article

English draughts (British English) or checkers (American English), also called straight checkers or simply draughts, is a form of the strategy board game

Graph embedding (1,747 words) [view diff] no match in snippet view article find links to article

In topological graph theory, an embedding (also spelled imbedding) of a graph G {\displaystyle G} on a surface Σ {\displaystyle \Sigma } is a representation

Caterpillar tree (1,199 words) [view diff] no match in snippet view article find links to article

In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path. Caterpillars were first

Method of fundamental solutions (1,175 words) [view diff] exact match in snippet view article find links to article

of a boundary discretization numerical technique and reduce the computational complexity by one dimensionality and have particular edge over the domain-type

H. T. Kung (1,052 words) [view diff] exact match in snippet view article find links to article

He remains an active researcher, with ongoing contributions to computational complexity theory, hardware design, parallel computing, routing, wireless

Integral polytope (943 words) [view diff] no match in snippet view article find links to article

In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it

Matching polynomial (882 words) [view diff] no match in snippet view article find links to article

In the mathematical fields of graph theory and combinatorics, a matching polynomial (sometimes called an acyclic polynomial) is a generating function of

Hamming graph (651 words) [view diff] no match in snippet view article find links to article

Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics (graph theory) and computer science

Christofides algorithm (1,259 words) [view diff] no match in snippet view article find links to article

The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on

Circuit (598 words) [view diff] exact match in snippet view article find links to article

circuit, a mathematical object of computational complexity Circuit complexity, a branch of computational complexity theory Cycle (graph theory), a closed

Shakashaka (190 words) [view diff] exact match in snippet view article find links to article

Erik D.; Okamoto, Yoshio; Uehara, Ryuhei; Uno, Yushi (2014), "Computational complexity and an integer programming model of Shakashaka", IEICE Transactions

Derangement (2,197 words) [view diff] no match in snippet view article find links to article

In combinatorial mathematics, a derangement is a permutation of the elements of a set in which no element appears in its original position. In other words

Master theorem (analysis of algorithms) (1,955 words) [view diff] no match in snippet view article

In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides an asymptotic analysis for many recurrence relations that

Discrete logarithm (2,042 words) [view diff] exact match in snippet view article find links to article

method is known for computing them in general. In cryptography, the computational complexity of the discrete logarithm problem and its application, was first

Path cover (381 words) [view diff] no match in snippet view article find links to article

Given a directed graph G = (V, E), a path cover is a set of directed paths such that every vertex v ∈ V belongs to at least one path. Note that a path

Graph sandwich problem (524 words) [view diff] no match in snippet view article find links to article

In graph theory and computer science, the graph sandwich problem is a problem of finding a graph that belongs to a particular family of graphs and is "sandwiched"

Unit disk graph (1,379 words) [view diff] no match in snippet view article find links to article

In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one

Ghost (game) (1,086 words) [view diff] no match in snippet view article

Ghost (also known as ghosts or endbee) is a written or spoken word game in which players take turns to extend the letters of a word without completing

Director string (675 words) [view diff] exact match in snippet view article find links to article

and Mackie as a mechanism for understanding and controlling the computational complexity cost of beta reduction. In beta reduction, one defines the value

Tanner graph (357 words) [view diff] no match in snippet view article find links to article

In coding theory, a Tanner graph, named after Michael Tanner, is a bipartite graph used to state constraints or equations which specify error correcting

Graph power (1,260 words) [view diff] no match in snippet view article find links to article

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

Exact coloring (520 words) [view diff] no match in snippet view article find links to article

In graph theory, an exact coloring is a (proper) vertex coloring in which every pair of colors appears on exactly one pair of adjacent vertices. That is

Tile-matching video game (2,728 words) [view diff] no match in snippet view article find links to article

A tile-matching video game is a type of puzzle video game where the player manipulates tiles in order to make them disappear according to a matching criterion

Convex hull algorithms (2,229 words) [view diff] exact match in snippet view article find links to article

For a finite set of points in the plane, the lower bound on the computational complexity of finding the convex hull represented as a convex polygon is easily

List of Jewish American computer scientists (1,638 words) [view diff] exact match in snippet view article find links to article

(Turing Award (1995)), Venezuelan-American computer scientist; computational complexity, parents of Avrim Blum (Co-training) Dan Bricklin, creator of the

Matching (graph theory) (2,938 words) [view diff] no match in snippet view article

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

Subgraph isomorphism problem (1,847 words) [view diff] no match in snippet view article find links to article

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

Fractional graph isomorphism (267 words) [view diff] no match in snippet view article find links to article

In graph theory, a fractional isomorphism of graphs whose adjacency matrices are denoted A and B is a doubly stochastic matrix D such that DA = BD. If

Kayles (907 words) [view diff] no match in snippet view article find links to article

Kayles is a simple impartial game in combinatorial game theory, invented by Henry Dudeney in 1908. Given a row of imagined bowling pins, players take turns

Pancyclic graph (1,500 words) [view diff] no match in snippet view article find links to article

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from

Borwein's algorithm (1,545 words) [view diff] case mismatch in snippet view article find links to article

the book Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity. These two are examples of a Ramanujan–Sato series. The related

Grötzsch's theorem (1,145 words) [view diff] no match in snippet view article find links to article

In the mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free planar graph can be colored with only three colors

Series-parallel partial order (2,253 words) [view diff] no match in snippet view article find links to article

In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two

Numberlink (522 words) [view diff] no match in snippet view article find links to article

Numberlink is a type of logic puzzle involving finding paths to connect numbers in a grid. The player has to pair up all the matching numbers on the grid

Edge dominating set (673 words) [view diff] no match in snippet view article find links to article

In graph theory, an edge dominating set for a graph G = (V, E) is a subset D ⊆ E such that every edge not in D is adjacent to at least one edge in D. An

Markov decision process (4,869 words) [view diff] exact match in snippet view article find links to article

for finite MDPs. Thus, decision problems based on MDPs are in computational complexity class P. However, due to the curse of dimensionality, the size

Information Processing Letters (520 words) [view diff] exact match in snippet view article find links to article

science, including algorithms, formal languages and automata, computational complexity, computational logic, distributed and parallel algorithms, computational

Edge dominating set (673 words) [view diff] no match in snippet view article find links to article

In graph theory, an edge dominating set for a graph G = (V, E) is a subset D ⊆ E such that every edge not in D is adjacent to at least one edge in D. An

Sanjeev Arora (432 words) [view diff] case mismatch in snippet view article find links to article

Mathematicians. He is a coauthor (with Boaz Barak) of the book Computational Complexity: A Modern Approach. He was a founder of Princeton's Center for

Structured program theorem (2,826 words) [view diff] no match in snippet view article find links to article

The structured program theorem, also called the Böhm–Jacopini theorem, is a result in programming language theory. It states that a class of control-flow

Graph toughness (623 words) [view diff] no match in snippet view article find links to article

In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t-tough for a given real number t if, for every integer

Induced matching (809 words) [view diff] no match in snippet view article find links to article

In graph theory, an induced matching or strong matching is a subset of the edges of an undirected graph that do not share any vertices (it is a matching)

Nurikabe (puzzle) (1,275 words) [view diff] no match in snippet view article

Nurikabe (hiragana: ぬりかべ) is a binary determination puzzle named for Nurikabe, an invisible wall in Japanese folklore that blocks roads and delays foot

Light Up (puzzle) (778 words) [view diff] no match in snippet view article

Light Up (Japanese: 美術館 bijutsukan, art gallery), also called Akari (明かり, light) is a binary-determination logic puzzle published by Nikoli. As of 2011

K-minimum spanning tree (1,057 words) [view diff] exact match in snippet view article find links to article

graphs with only two distinct edge weights. Because of the high computational complexity of finding an optimal solution to the k-minimum spanning tree,

Modular arithmetic (3,934 words) [view diff] no match in snippet view article find links to article

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus

Alternating tree automata (98 words) [view diff] no match in snippet view article find links to article

In automata theory, an alternating tree automaton (ATA) is an extension of nondeterministic tree automaton as same as alternating finite automaton extends

Theory of Computing Systems (101 words) [view diff] exact match in snippet view article find links to article

research from all areas of theoretical computer science, such as computational complexity, algorithms and data structures, or parallel and distributed algorithms

Shannon switching game (1,327 words) [view diff] no match in snippet view article find links to article

The Shannon switching game is a connection game for two players, invented by American mathematician and electrical engineer Claude Shannon, the "father

Kovner–Besicovitch measure (467 words) [view diff] no match in snippet view article find links to article

In plane geometry the Kovner–Besicovitch measure is a number defined for any bounded convex set describing how close to being centrally symmetric it is

Matchstick graph (1,571 words) [view diff] no match in snippet view article find links to article

In geometric graph theory, a branch of mathematics, a matchstick graph is a graph that can be drawn in the plane in such a way that its edges are line

Clique-width (2,057 words) [view diff] exact match in snippet view article find links to article

polynomial increases with the clique-width, and evidence from computational complexity theory shows that this dependence is likely to be necessary. The

Havannah (board game) (956 words) [view diff] no match in snippet view article

Havannah is a two-player abstract strategy board game invented by Christian Freeling. It belongs to the family of games commonly called connection games;

Ptolemaic graph (804 words) [view diff] no match in snippet view article find links to article

In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek

Ordo (266 words) [view diff] exact match in snippet view article find links to article

and ending in a rest Big O notation in calculation of algorithm computational complexity Orda (organization), also ordo or horde, was a nomadic palace for

Criss-cross algorithm (2,432 words) [view diff] no match in snippet view article find links to article

In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm

Domatic number (973 words) [view diff] no match in snippet view article find links to article

In graph theory, a domatic partition of a graph G = ( V , E ) {\displaystyle G=(V,E)} is a partition of V {\displaystyle V} into disjoint sets V 1 {\displaystyle

Perfectly orderable graph (1,149 words) [view diff] no match in snippet view article find links to article

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering

NP (278 words) [view diff] exact match in snippet view article find links to article

Polynomial, a computational complexity class NP-complete, a class of decision problems NP-hard, a class of problems in computational complexity Co-NP, a complexity

Steerable filter (222 words) [view diff] exact match in snippet view article find links to article

approximations of a given filter shape up to a desired error or computational complexity. Freeman, W. T. & Adelson, E. H. (1991). "The design and use of

Eulerian matroid (1,070 words) [view diff] no match in snippet view article find links to article

In matroid theory, an Eulerian matroid is a matroid whose elements can be partitioned into a collection of disjoint circuits. In a uniform matroid U n

RAC drawing (1,145 words) [view diff] no match in snippet view article find links to article

In graph drawing, a RAC drawing of a graph is a drawing in which the vertices are represented as points, the edges are represented as straight line segments

Game of the Amazons (983 words) [view diff] no match in snippet view article find links to article

The Game of the Amazons (in Spanish, El Juego de las Amazonas; often called Amazons for short) is a two-player abstract strategy game invented in 1988

Computers and Intractability (779 words) [view diff] exact match in snippet view article find links to article

as well. [...] Garey and Johnson has the best introduction to computational complexity I have ever seen." List of NP-complete problems Garey, M. R.; Johnson

Thickness (graph theory) (1,256 words) [view diff] no match in snippet view article

In graph theory, the thickness of a graph G is the minimum number of planar graphs into which the edges of G can be partitioned. That is, if there exists

Bag (puzzle) (342 words) [view diff] no match in snippet view article

Bag (also called Corral or Cave) is a binary-determination logic puzzle published by Nikoli. Bag is played on a rectangular grid, usually of dashed lines

Quotient graph (596 words) [view diff] no match in snippet view article find links to article

In graph theory, a quotient graph Q of a graph G is a graph whose vertices are blocks of a partition of the vertices of G and where block B is adjacent

Art gallery problem (2,530 words) [view diff] exact match in snippet view article find links to article

hdl:2043/11487, MR 3044626, S2CID 1458082. Lee, D. T.; Lin, A. K. (1986), "Computational complexity of art gallery problems", IEEE Transactions on Information Theory

Equitable coloring (2,291 words) [view diff] exact match in snippet view article find links to article

Eldridge, S. E. (1978), "Packings of graphs and applications to computational complexity", Journal of Combinatorial Theory, Series B, 25 (2): 105–124, doi:10

Tatamibari (166 words) [view diff] no match in snippet view article find links to article

Tatamibari (Japanese: タタミバリ) is a type of logic puzzle designed and published by Nikoli. The puzzle is based on Japanese tatami mats. A Tatamibari puzzle

Tentai Show (635 words) [view diff] no match in snippet view article find links to article

Tentai Show (Japanese: 天体ショー tentai shō), also known by the names Tentaisho, Galaxies, Spiral Galaxies, or Sym-a-Pix, is a binary-determination logic puzzle

Continuous knapsack problem (518 words) [view diff] exact match in snippet view article find links to article

in the formulation of a problem can have a large impact on its computational complexity. An instance of either the continuous or classic knapsack problems

Angular resolution (graph drawing) (1,617 words) [view diff] exact match in snippet view article

1007/BFb0049393. Garg, Ashim; Tamassia, Roberto (1995), "On the computational complexity of upward and rectilinear planarity testing", in Tamassia, Roberto;

Exponentiation by squaring (3,378 words) [view diff] no match in snippet view article find links to article

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number

PTAS (71 words) [view diff] exact match in snippet view article find links to article

currency PTAS reduction, an approximation-preserving reduction in computational complexity theory Preferential trading area, another term for a trade bloc

Kinodynamic planning (305 words) [view diff] exact match in snippet view article find links to article

the original PTAS algorithms (i.e., none have a provably lower computational complexity). Donald, B.; Xavier, P.; Canny, J.; Reif, J. (1993), "Kinodynamic

Time-inhomogeneous hidden Bernoulli model (240 words) [view diff] exact match in snippet view article find links to article

programming at state-level in TI-HBM decoding process. Thus, the computational complexity of TI-HBM for probability evaluation and state estimation is O

Checkers (3,228 words) [view diff] no match in snippet view article find links to article

Checkers (American English), also known as draughts (/drɑːfts, dræfts/; British English), is a group of strategy board games for two players which involve

Distinguishing coloring (1,309 words) [view diff] exact match in snippet view article find links to article

Alexander; Sundaram, Ravi (1998), "A note on the asymptotics and computational complexity of graph distinguishability", Electronic Journal of Combinatorics

Linear arboricity (858 words) [view diff] no match in snippet view article find links to article

In graph theory, a branch of mathematics, the linear arboricity of an undirected graph is the smallest number of linear forests its edges can be partitioned

MaxDDBS (222 words) [view diff] exact match in snippet view article find links to article

Degree-Diameter Problem has been active since the 1960s. Regarding its computational complexity, the problem is NP-hard, and not in APX (i.e. it cannot be approximated

Random neural network (1,063 words) [view diff] exact match in snippet view article find links to article

includes feedback loops (it is also a recurrent neural network) is of computational complexity O(n^3) (the number of computations is proportional to the cube

Maximum cut (2,800 words) [view diff] no match in snippet view article find links to article

In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary

Halin graph (2,157 words) [view diff] no match in snippet view article find links to article

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four

Queue number (2,712 words) [view diff] no match in snippet view article find links to article

In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using

Matroid girth (763 words) [view diff] no match in snippet view article find links to article

In matroid theory, a mathematical discipline, the girth of a matroid is the size of its smallest circuit or dependent set. The cogirth of a matroid is

Tutte polynomial (5,349 words) [view diff] exact match in snippet view article find links to article

{\displaystyle (x,y)} , one can define a rational analogue of #P. The computational complexity of exactly computing T G ( x , y ) {\displaystyle T_{G}(x,y)} falls

SL (409 words) [view diff] exact match in snippet view article find links to article

top-level domain for Sierra Leone SL (complexity), a class of computational complexity Scientific Linux, a Linux distribution Service Loading, a variant

Segmentation-based object categorization (1,901 words) [view diff] no match in snippet view article find links to article

The image segmentation problem is concerned with partitioning an image into multiple regions according to some homogeneity criterion. This article is primarily

Thue number (702 words) [view diff] no match in snippet view article find links to article

In the mathematical area of graph theory, the Thue number of a graph is a variation of the chromatic index, defined by Alon et al. (2002) and named after

Metric k-center (1,748 words) [view diff] no match in snippet view article find links to article

In graph theory, the metric k-center problem is a combinatorial optimization problem studied in theoretical computer science. Given n cities with specified

Bramble (graph theory) (937 words) [view diff] no match in snippet view article

In graph theory, a bramble for an undirected graph G is a family of connected subgraphs of G that all touch each other: for every pair of disjoint subgraphs

Radio coloring (638 words) [view diff] no match in snippet view article find links to article

In graph theory, a branch of mathematics, a radio coloring of an undirected graph is a form of graph coloring in which one assigns positive integer labels

Christopher Cherniak (1,597 words) [view diff] exact match in snippet view article find links to article

idealizations. This is part of the philosophical significance of computational complexity. This research program proceeds from a holistic rather than compartmentalized

Map graph (778 words) [view diff] no match in snippet view article find links to article

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

Hadwiger number (1,231 words) [view diff] no match in snippet view article find links to article

In graph theory, the Hadwiger number of an undirected graph G is the size of the largest complete graph that can be obtained by contracting edges of G