New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 250 | older 250) (20 | 50 | 100 | 250 | 500)
- 11:23, 15 February 2023 4NF Decomposition (hist | edit) [3,239 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:4NF Decomposition (4NF Decomposition)}} == Description == 4NF Decomposition is the problem of decomposing a relation schema into fourth normal form (4NF). A relation schema $R^*$ is in fourth normal form (4NF) if, whenever a nontrivial multivalued dependency $X \rightarrow \rightarrow Y$ holds for $R^*$, then so does the functiunal dependency $X \rightarrow A$ for every column name $A$ of $R^*$. Intuitively all dependencies are the result of keys. In pa...")
- 11:23, 15 February 2023 Decisional BCNF (hist | edit) [1,227 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Decisional BCNF (BCNF Decomposition)}} == Description == Decisional BCNF is the problem of deciding whether or not a relation schema can be turned into Boyce-Codd normal form (BCNF). A relation schema $R$ is in Boyce Codd Normal Form (abbr. BCNF) if for all non-trivial FDs $X \rightarrow Y$ in $F^+$, $X$ is a superkey. In extending this notion to database schemas, we must be conscious of the UR-assumption. We say that $R_i = <ATTR_i,F_i>$ is in BCNF if...")
- 11:22, 15 February 2023 Multivalued Dependency Inference Problem (hist | edit) [2,220 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Multivalued Dependency Inference Problem (Dependency Inference Problem)}} == Description == The multivalued dependency inference problem is to find a cover for the set of multivalued dependencies that hold in a given relation. A multivalued dependency (abbr. MVD), $g$, on a set of attributes $U$ is a statement $g: X \rightarrow \rightarrow Y$, where $X$ and $Y$ are subsets of $U$. Let $Z$ be the complement of the union of $X$ and $Y$ in $U$. A relation...")
- 11:22, 15 February 2023 Functional Dependency Inference Problem (hist | edit) [2,051 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Functional Dependency Inference Problem (Dependency Inference Problem)}} == Description == The functional dependency inference problem is to find a cover for the set of functional dependencies that hold in a given relation. A functional dependency (abbr. FD), $f$, is a statement $f: X \rightarrow Y$ where $X$ and $Y$ are sets of attributes. If $R(X, Y, \ldots)$ is a relation on a set of attributes that contains $X$ and $Y$, then $R$ obeys the FD $f$ if...")
- 11:22, 15 February 2023 Subset Sum (hist | edit) [4,859 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Subset Sum (The Subset-Sum Problem)}} == Description == Given a set $S$ of integers and a target sum $t$, determine whether there is a subset of $S$ that sum to $t$. == Parameters == <pre>S: the set of integers n: the number of integers in the set n': the number of distinct elements in the set t: the target sum σ: sum of elements in the set</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Na...")
- 11:22, 15 February 2023 De Novo Genome Assembly (hist | edit) [2,036 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:De Novo Genome Assembly (De Novo Genome Assembly)}} == Description == De novo sequencing refers to sequencing a novel genome where there is no reference sequence available for alignment. Sequence reads are assembled as contigs, and the coverage quality of de novo sequence data depends on the size and continuity of the contigs (ie, the number of gaps in the data). == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable so...")
- 11:22, 15 February 2023 Delaunay Triangulation (hist | edit) [3,906 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Delaunay Triangulation (Delaunay Triangulation)}} == Description == Given a set of points, the Delaunay Triangulation problem is to triangulate the points using the following notion of triangulation. $AB$ is an edge of the Delaunay triangulation iff there is a circle passing through $A$ and $B$ so that all other points in the point set, $C$, where $C$ is not equal to $A$ or $B$, lie outside the circle. Equivalently, all triangles in the Delaunay triangu...")
- 11:22, 15 February 2023 3-Dimensional Poisson Problem (hist | edit) [2,865 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3-Dimensional Poisson Problem (Poisson Problem)}} == Description == Given $f$, solve for $u$ in the 3-dimensional Poisson equation: $u_{xx} + u_{yy} + u_{zz} = f(x,y,z)$ == Related Problems == Related: 2-Dimensional Poisson Problem == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Referenc...")
- 11:22, 15 February 2023 2-Dimensional Poisson Problem (hist | edit) [2,854 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-Dimensional Poisson Problem (Poisson Problem)}} == Description == Given $f$, solve for $u$ in the 2-dimensional Poisson equation: $u_{xx} + u_{yy} = f(x,y)$ == Related Problems == Related: 3-Dimensional Poisson Problem == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | ...")
- 11:22, 15 February 2023 Approximate TSP (hist | edit) [2,382 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Approximate TSP (The Traveling-Salesman Problem)}} == Description == Approximate TSP is the problem of finding an approximate answer to Minimum TSP. In Minimum TSP, you are given a set $C$ of cities and distances between each distinct pair of cities. The goal is to find an ordering or tour of the cities, such that you visit each city exactly once and return to the origin city, that minimizes the length of the tour. This is the typical variation of TSP....")
- 11:22, 15 February 2023 Maximum TSP (hist | edit) [1,562 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum TSP (The Traveling-Salesman Problem)}} == Description == In Maximum TSP, you are given a set $C$ of cities and distances between each distinct pair of cities. The goal is to find an ordering or tour of the cities, such that you visit each city exactly once and return to the origin city, that maximizes the length of the tour. == Related Problems == Related: Minimum TSP, Approximate TSP == Parameters == <pre>V: number of cities (nodes...")
- 11:22, 15 February 2023 Minimum TSP (hist | edit) [2,636 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Minimum TSP (The Traveling-Salesman Problem)}} == Description == In Minimum TSP, you are given a set $C$ of cities and distances between each distinct pair of cities. The goal is to find an ordering or tour of the cities, such that you visit each city exactly once and return to the origin city, that minimizes the length of the tour. This is the typical variation of TSP. == Related Problems == Related: Maximum TSP, Approximate TSP == Parameter...")
- 11:22, 15 February 2023 Max-Weight k-Clique (hist | edit) [1,360 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Max-Weight k-Clique (Clique Problems)}} == Description == Given a graph $G = (V, E)$, find the $k$-clique of maximum weight. == Related Problems == Generalizations: k-Clique Related: Enumerating Maximal Cliques, arbitrary graph, Exact k-Clique, Min-Weight k-Clique == Parameters == <pre>n: number of vertices k: size of clique</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reduct...")
- 11:22, 15 February 2023 Min-Weight k-Clique (hist | edit) [1,119 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Min-Weight k-Clique (Clique Problems)}} == Description == Given a graph $G = (V, E)$, find the $k$-clique of minimum weight. == Related Problems == Generalizations: k-Clique Related: Enumerating Maximal Cliques, arbitrary graph, Exact k-Clique, Max-Weight k-Clique == Parameters == <pre>n: number of vertices k: size of clique</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reduct...")
- 11:22, 15 February 2023 Exact k-Clique (hist | edit) [472 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Exact k-Clique (Clique Problems)}} == Description == Given a graph $G = (V, E)$, find a $k$-clique of weight 0. == Related Problems == Generalizations: k-Clique Related: Enumerating Maximal Cliques, arbitrary graph, Min-Weight k-Clique, Max-Weight k-Clique == Parameters == <pre>n: number of vertices k: size of clique</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem.")
- 11:22, 15 February 2023 K-Clique (hist | edit) [2,236 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:k-Clique (Clique Problems)}} == Description == For a constant $k \geq 3$, the $k$-Clique problem is as follows: given a graph $G = (V, E)$ on $n$ vertices, does $G$ contain $k$ distinct vertices $a_1, \ldots, a_k$ so that for every $(i, j)$, $i \neq j$, $(a_i, a_j ) \in E$? Such a $k$ node graph is called a $k$-clique. == Related Problems == Subproblem: Exact k-Clique, Min-Weight k-Clique, Max-Weight k-Clique Related: Enumerating Maxi...")
- 11:22, 15 February 2023 Enumerating Maximal Cliques, arbitrary graph (hist | edit) [3,728 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Enumerating Maximal Cliques, arbitrary graph (Clique Problems)}} == Description == A maximal clique (complete subgraph) is a clique that is not contained in any other clique. The goal here is to enumerate such maximal cliques in a given graph. == Related Problems == Related: k-Clique, Exact k-Clique, Min-Weight k-Clique, Max-Weight k-Clique == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms...")
- 11:22, 15 February 2023 Inexact GED (hist | edit) [2,584 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Inexact GED (Graph Edit Distance Computation)}} == Description == The GED of two graphs is defined as the minimum cost of an edit path between them, where an edit path is a sequence of edit operations (inserting, deleting, and relabeling vertices or edges) that transforms one graph into another. Inexact GED computes an answer that is not gauranteed to be the exact GED. == Related Problems == Related: Exact GED == Parameters == <pre>V: number of...")
- 11:22, 15 February 2023 Exact GED (hist | edit) [1,601 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Exact GED (Graph Edit Distance Computation)}} == Description == The GED of two graphs is defined as the minimum cost of an edit path between them, where an edit path is a sequence of edit operations (inserting, deleting, and relabeling vertices or edges) that transforms one graph into another. Exact GED computes the GED exactly. == Related Problems == Related: Inexact GED == Parameters == <pre>V: number of vertices in the larger of the two grap...")
- 11:22, 15 February 2023 Lowest Common Ancestors with Linking and Cutting (hist | edit) [1,258 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Lowest Common Ancestors with Linking and Cutting (Lowest Common Ancestor)}} == Description == Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" In this version of the problem, the queries are on-line. Interspersed with the queries are on-line commands of two types: $link(x, y)$, where $y$ but not necessarily $x$ is a tree root, and $cut (x)$, where $x$ is not a root. The effect...")
- 11:22, 15 February 2023 Lowest Common Ancestor with Linking (hist | edit) [2,841 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Lowest Common Ancestor with Linking (Lowest Common Ancestor)}} == Description == Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" In this version of the problem, the queries are on-line. Interspersed with the queries are on-line commands $link(x, y)$ such that $y$, but not necessarily $x$, is a tree root. The effect of a command $link(x, y)$ is to combine the trees containing $...")
- 11:22, 15 February 2023 Lowest Common Ancestor with Linking Roots (hist | edit) [1,815 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Lowest Common Ancestor with Linking Roots (Lowest Common Ancestor)}} == Description == Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" In this version of the problem, The queries are given on-line. Interspersed with the queries are on-line commands of the form $link(x, y)$ where $x$ and $y$ are tree roots. The effect of a command $link(x, y)$ is to combine the trees containing...")
- 11:22, 15 February 2023 Lowest Common Ancestor with Static Trees (hist | edit) [3,979 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Lowest Common Ancestor with Static Trees (Lowest Common Ancestor)}} == Description == Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" In this version of the problem, the collection of trees is static but the queries are given on-line. That is, each query must be answered before the next one is known. == Related Problems == Generalizations: Lowest Common Ancestor Relate...")
- 11:22, 15 February 2023 Off-Line Lowest Common Ancestor (hist | edit) [1,783 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Off-Line Lowest Common Ancestor (Lowest Common Ancestor)}} == Description == Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" In this version of the problem, the collection of trees is static and the entire sequence of queries is specified in advance. == Related Problems == Generalizations: Lowest Common Ancestor Related: Lowest Common Ancestor with Static Trees, ...")
- 11:22, 15 February 2023 Lowest Common Ancestor (hist | edit) [6,468 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Lowest Common Ancestor (Lowest Common Ancestor)}} == Description == Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" == Related Problems == Subproblem: Off-Line Lowest Common Ancestor, Lowest Common Ancestor with Static Trees, Lowest Common Ancestor with Linking Roots, Lowest Common Ancestor with Linking, Lowest Common Ancestors with Linking and Cutting...")
- 11:22, 15 February 2023 Cyclic Nontrivial SCCs DFA Minimization (hist | edit) [1,030 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Cyclic Nontrivial SCCs DFA Minimization (DFA Minimization)}} == Description == Given an finite deterministic automaton (DFA) from a class $C$ of DFAs, whose nontrivial SCCs are cyclic, determine its minimal automaton given by the equivalence relation on states. == Related Problems == Generalizations: DFA Minimization Related: Acyclic DFA Minimization == Parameters == <pre>$n$: number of states $d$: number of transitions $k$: size of alphab...")
- 11:22, 15 February 2023 Acyclic DFA Minimization (hist | edit) [1,043 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Acyclic DFA Minimization (DFA Minimization)}} == Description == Given an acyclic finite deterministic automaton (DFA) from a class $C$ of DFAs, determine its minimal automaton given by the equivalence relation on states. == Related Problems == Generalizations: DFA Minimization Related: Cyclic Nontrivial SCCs DFA Minimization == Parameters == <pre>$n$: number of states $d$: number of transitions $k$: size of alphabet</pre> == Table of Algo...")
- 11:22, 15 February 2023 Variance Calculations (hist | edit) [1,510 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Variance Calculations (Variance Calculations)}} == Description == Given a set of n (real/integer) numbers, compute the variance (sample or population). Of interest is streaming algorithms and numerical stability. == Parameters == <pre>n: number of values</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Naïve...")
- 11:22, 15 February 2023 Voronoi Diagrams (hist | edit) [1,237 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Voronoi Diagrams (Voronoi Diagrams)}} == Description == Given a set of n points in 2-dimensional space, compute the Voronoi diagram with the n points as seeds. == Parameters == <pre>n: number of points</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Fortune's algorithm (Voronoi Diagrams Voronoi Diagrams)|For...")
- 11:22, 15 February 2023 Global Register Allocation (hist | edit) [2,685 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Global Register Allocation (Register Allocation)}} == Description == Register allocation is the process of mapping the unlimited number of symbolic registers assumed in the intermediate language into the limited real machine registers. Global register allocation deals with the allocation of registers in code containing branches (http://www.cs.ucr.edu/~gupta/research/Publications/Comp/p370-gupta.pdf). == Related Problems == Related: Local Register A...")
- 11:22, 15 February 2023 Local Register Allocation (hist | edit) [1,011 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Local Register Allocation (Register Allocation)}} == Description == Register allocation is the process of mapping the unlimited number of symbolic registers assumed in the intermediate language into the limited real machine registers. Local register allocation deals with the allocation of registers in straight-line code segments (http://www.cs.ucr.edu/~gupta/research/Publications/Comp/p370-gupta.pdf). == Related Problems == Related: Global Register...")
- 11:22, 15 February 2023 Cardinality Estimation (hist | edit) [1,750 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Cardinality Estimation (Cardinality Estimation)}} == Description == Given a multiset of (possibly hashed) values, estimate the number of distinct elements of the multiset. Of interest is minimizing storage usage. == Parameters == <pre>N: number of values in multiset n: cardinality of multiset (not known)</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approxi...")
- 11:21, 15 February 2023 Maximum Likelihood Parameters (hist | edit) [1,986 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum Likelihood Parameters (Maximum Likelihood Parameters)}} == Description == In these algorithms, the goal is to estimate hyperparameters using maximum likelihood. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Expectation–maximization (EM) algorithm ( Maximum Likeliho...")
- 11:21, 15 February 2023 K Approximate Nearest Neighbors Search (hist | edit) [513 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:k Approximate Nearest Neighbors Search (Nearest Neighbor Search)}} == Description == Within a dataset of $n$ points, find approximately the $k$ closest points to a specified point. == Related Problems == Generalizations: k Nearest Neighbors Search == Parameters == <pre>n: number of points in dataset k: number of neighbors to find</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem.")
- 11:21, 15 February 2023 K Nearest Neighbors Search (hist | edit) [491 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:k Nearest Neighbors Search (Nearest Neighbor Search)}} == Description == Within a dataset of $n$ points, find the $k$ closest points to a specified point. == Related Problems == Subproblem: k Approximate Nearest Neighbors Search == Parameters == <pre>n: number of points in dataset k: number of neighbors to find</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem.")
- 11:21, 15 February 2023 Root Computation (hist | edit) [3,105 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Root Computation (Root Computation)}} == Description == Given a real continuous function, compute one of the roots. == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem.")
- 11:21, 15 February 2023 Eigenpair closest to mu (hist | edit) [1,834 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Eigenpair closest to mu (Eigenvalues (Iterative Methods))}} == Description == Given an $n \times n$ matrix $A$, find the eigenpair (eigenvalue and associated eigenvector) of $A$ with the eigenvalue closest to $\mu$. == Related Problems == Generalizations: Any Eigenpair Related: All Eigenvalues, Any Eigenvalue, All Eigenpairs, Eigenpair with the Largest Eigenvalue == Parameters == No parameters found. == Table of Algorithms ==...")
- 11:21, 15 February 2023 Eigenpair with the Largest Eigenvalue (hist | edit) [1,114 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Eigenpair with the Largest Eigenvalue (Eigenvalues (Iterative Methods))}} == Description == Given an $n \times n$ matrix $A$, find the eigenpair (eigenvalue and associated eigenvector) of $A$ with the largest eigenvalue. == Related Problems == Generalizations: Any Eigenpair Related: All Eigenvalues, Any Eigenvalue, All Eigenpairs, Eigenpair closest to mu == Parameters == No parameters found. == Table of Algorithms == {| clas...")
- 11:21, 15 February 2023 Any Eigenpair (hist | edit) [596 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Any Eigenpair (Eigenvalues (Iterative Methods))}} == Description == Given an $n \times n$ matrix $A$, find any eigenpair (eigenvalue and associated eigenvector) of $A$. == Related Problems == Subproblem: Any Eigenvalue, All Eigenpairs, Eigenpair with the Largest Eigenvalue, Eigenpair closest to mu Related: All Eigenvalues, All Eigenpairs, Eigenpair with the Largest Eigenvalue, Eigenpair closest to mu == Parameters...")
- 11:21, 15 February 2023 All Eigenpairs (hist | edit) [509 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:All Eigenpairs (Eigenvalues (Iterative Methods))}} == Description == Given an $n \times n$ matrix $A$, find all eigenpairs (eigenvalues and associated eigenvectors) of $A$. == Related Problems == Generalizations: Any Eigenpair Related: All Eigenvalues, Any Eigenvalue, Eigenpair with the Largest Eigenvalue, Eigenpair closest to mu == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our d...")
- 11:21, 15 February 2023 Any Eigenvalue (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Any Eigenvalue (Eigenvalues (Iterative Methods))}} == Description == Given an $n \times n$ matrix $A$, find any eigenvalue of $A$. == Related Problems == Generalizations: Any Eigenpair Subproblem: All Eigenvalues Related: All Eigenpairs, Eigenpair with the Largest Eigenvalue, Eigenpair closest to mu == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem.")
- 11:21, 15 February 2023 All Eigenvalues (hist | edit) [468 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:All Eigenvalues (Eigenvalues (Iterative Methods))}} == Description == Given an $n \times n$ matrix $A$, find all eigenvalues of $A$. == Related Problems == Generalizations: Any Eigenvalue Related: All Eigenpairs, Any Eigenpair, Eigenpair with the Largest Eigenvalue, Eigenpair closest to mu == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem.")
- 11:21, 15 February 2023 Line Simplification (hist | edit) [1,586 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Line Simplification (Line Simplification)}} == Description == Line simplification is the process of taking a line/curve as represented by a list of points and reducing the number of points needed to accurately represent the given line. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |...")
- 11:21, 15 February 2023 (3-Dimensional, i.e. project onto a 2D plane) (hist | edit) [2,113 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:(3-Dimensional, i.e. project onto a 2D plane) (Shown Surface Determination)}} == Description == This is the process of identifying what surfaces and parts of surfaces can be seen from a particular viewing angle. Given a set of obstacles in the Euclidean space, two points in the space are said to be visible to each other, if the line segment that joins them does not intersect any obstacles. == Parameters == <pre>n: number of polygons p: number of pixel...")
- 11:21, 15 February 2023 Polygon Clipping with Convex Clipping Polygon (hist | edit) [855 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Polygon Clipping with Convex Clipping Polygon (Polygon Clipping)}} == Description == Here, the clipping polygon is restricted to being convex. == Related Problems == Generalizations: Polygon Clipping with Arbitrary Clipping Polygon == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference...")
- 11:21, 15 February 2023 Polygon Clipping with Arbitrary Clipping Polygon (hist | edit) [1,909 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Polygon Clipping with Arbitrary Clipping Polygon (Polygon Clipping)}} == Description == Clipping is an essential part of image synthesis. Traditionally, polygon clipping has been used to clip out the portions of a polygon that lie outside the window of the output device to prevent undesirable effects. In the recent past polygon clipping is used to render 3D images through hidden surface removal and to produce high-quality surface details using techniques...")
- 11:21, 15 February 2023 Line Drawing (hist | edit) [1,609 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Line Drawing (Line Drawing)}} == Description == Given a line segment with endpoints $(x_0, y_0), (x_1, y_1)$ and a discrete graphical medium (like pixel-based displays and printers), draw/approximate the line segment on the medium, potentially with antialiasing. == Parameters == <pre>n: number of pixels the line goes through</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Tim...")
- 11:21, 15 February 2023 Constructing Eulerian Trails in a Graph (hist | edit) [1,550 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Constructing Eulerian Trails in a Graph (Constructing Eulerian Trails in a Graph)}} == Description == In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable...")
- 11:21, 15 February 2023 Bipartite Maximum-Weight Matching (hist | edit) [1,383 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Bipartite Maximum-Weight Matching (Maximum-Weight Matching)}} == Description == In computer science, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized. Here, the graph must be bipartite. == Related Problems == Generalizations: Maximum-Weight Matching == Parameters == <pre>n: number of vertices m: number of edges N: largest weight magnitude</pre> == Table of A...")
- 11:21, 15 February 2023 Maximum-Weight Matching (hist | edit) [1,590 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum-Weight Matching (Maximum-Weight Matching)}} == Description == In computer science, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized. Here, the graph is unrestricted; i.e. can be any general graph. == Related Problems == Subproblem: Bipartite Maximum-Weight Matching == Parameters == <pre>n: number of vertices m: number of edges N: largest weight magnit...")
- 11:21, 15 February 2023 N-Player (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:n-Player (Nash Equilibria)}} == Description == Here, given the payoff matrices for an $n$-player game, determine a Nash equilibrium. == Related Problems == Subproblem: 2-Player == Parameters == <pre>n: number of players</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem.")
- 11:21, 15 February 2023 2-Player (hist | edit) [723 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-Player (Nash Equilibria)}} == Description == In game theory, the Nash equilibrium, named after the mathematician John Forbes Nash Jr., is a proposed solution of a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy. As an algorithmic problem, given the payoff matrices for a bimatrix game, determine...")
- 11:21, 15 February 2023 Alphabetic Tree Problem (hist | edit) [1,454 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Alphabetic Tree Problem (Optimal Binary Search Trees)}} == Description == A variant of the OBST problem is when only the gaps have nonzero access probabilities, and is called the optimal alphabetic tree problem. == Related Problems == Generalizations: Optimal Binary Search Tree Problem Related: Approximate OBST, Huffman Encoding == Parameters == <pre>n: number of elements</pre> == Table of Algorithms == {| class="wikitable sortable"...")
- 11:21, 15 February 2023 Approximate OBST (hist | edit) [2,086 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Approximate OBST (Optimal Binary Search Trees)}} == Description == Suppose we are given $n$ keys and the probabilities of accessing each key and those occurring in the gap between two successive keys. The approximate optimal binary search tree problem is to construct a binary search tree on these $n$ keys, whose expected access time is within an approximation factor of the optimal time. == Related Problems == Generalizations: Optimal Binary Search T...")
- 11:21, 15 February 2023 Optimal Binary Search Tree Problem (hist | edit) [678 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Optimal Binary Search Tree Problem (Optimal Binary Search Trees)}} == Description == Suppose we are given $n$ keys and the probabilities of accessing each key and those occurring in the gap between two successive keys. The optimal binary search tree problem is to construct a binary search tree on these $n$ keys that minimizes the expected access time. == Related Problems == Subproblem: Approximate OBST, Huffman Encoding, Alphabetic Tree Pr...")
- 11:21, 15 February 2023 All Permutations (hist | edit) [1,207 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:All Permutations (All Permutations)}} == Description == Generate all permuttaions of the characters/elements in a string/array. == Parameters == <pre>n: number of elements</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Steinhaus–Johnson–Trotter algorithm (All Permutations All Permutations)|Steinhaus–J...")
- 11:21, 15 February 2023 Minimum value in each row of an implicitly-defined totally monotone matrix (hist | edit) [1,585 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Minimum value in each row of an implicitly-defined totally monotone matrix (Minimum value in each row of an implicitly-defined totally monotone matrix)}} == Description == Given a totally monotone matrix $A$ whose entries $A(i, j)$ are implicitly defined by some function $f(i, j)$ (assume $f$ takes constant time to evaluate for all relevant $(i, j)$), determine the minimum value in each row. == Parameters == <pre>n, m: dimensions of matrix; assume m...")
- 11:21, 15 February 2023 Gröbner Bases (hist | edit) [1,658 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Gröbner Bases (Gröbner Bases)}} == Description == In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring $K(x_1, \ldots ,x_n)$ over a field $K$. As an algorithmic problem, given a set of polynomials in $K(x_1, \ldots,x_n)$, determine a Gröbner basis. == Parameters == <pre>n: number of...")
- 11:21, 15 February 2023 Convex Optimization (Non-linear) (hist | edit) [528 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Convex Optimization (Non-linear) (Convex Optimization (Non-linear))}} == Description == Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem. == Time Complexity graph == 1000px == Space...")
- 11:21, 15 February 2023 Cyclic Permutations (hist | edit) [849 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Cyclic Permutations (Generating Random Permutations)}} == Description == Given an input string/array, generate a single random cyclic permutation of the characters/elements of the string/array. == Related Problems == Related: General Permutations == Parameters == <pre>n: number of elements</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation...")
- 11:21, 15 February 2023 General Permutations (hist | edit) [1,294 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:General Permutations (Generating Random Permutations)}} == Description == Given an input string/array, generate a single random permutation of the characters/elements of the string/array. == Related Problems == Related: Cyclic Permutations == Parameters == <pre>n: number of elements</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor...")
- 11:20, 15 February 2023 Inexact Laplacian Solver (hist | edit) [3,888 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Inexact Laplacian Solver (SDD Systems Solvers)}} == Description == This problem refers to solving equations of the form $Lx = b$ where $L$ is a Laplacian of a graph. In other words, this is solving equations of the form $Ax = b$ for a SDD matrix $A$. This variation of the problem permits some error. == Related Problems == Related: Exact Laplacian Solver == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sort...")
- 11:20, 15 February 2023 Exact Laplacian Solver (hist | edit) [1,294 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Exact Laplacian Solver (SDD Systems Solvers)}} == Description == This problem refers to solving equations of the form $Lx = b$ where $L$ is a Laplacian of a graph. In other words, this is solving equations of the form $Ax = b$ for a SDD matrix $A$. This variation of the problem requires an exact solution with no error. == Related Problems == Related: Inexact Laplacian Solver == Parameters == <pre>n: dimension of matrix</pre> == Table of Algor...")
- 11:20, 15 February 2023 Key Exchange (hist | edit) [1,168 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Key Exchange (Key Exchange)}} == Description == Key exchange (also key establishment) is a method in cryptography by which cryptographic keys are exchanged between two parties, allowing use of a cryptographic algorithm. == Parameters == <pre>n: maximum size of numbers (prime, parameters, keys), in bits</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approxima...")
- 11:20, 15 February 2023 Planar Bipartite Graph Perfect Matching (hist | edit) [1,333 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Planar Bipartite Graph Perfect Matching (Maximum Cardinality Matching)}} == Description == The goal of maximum cardinality matching is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible). Here, the graph is a planar bipartite graph. == Related Problems == Generalizations: Bipartite Graph MCM Related: General Graph MCM == Parameters == <pre>V: number of vertices E: number of...")
- 11:20, 15 February 2023 General Graph MCM (hist | edit) [1,737 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:General Graph MCM (Maximum Cardinality Matching)}} == Description == The goal of maximum cardinality matching is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible). Here, the graph can be any general graph. == Related Problems == Subproblem: Bipartite Graph MCM Related: Planar Bipartite Graph Perfect Matching == Parameters == <pre>V: number of vertices E: number of edges</p...")
- 11:20, 15 February 2023 Bipartite Graph MCM (hist | edit) [2,906 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Bipartite Graph MCM (Maximum Cardinality Matching)}} == Description == The goal of maximum cardinality matching is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible). Here, the graph is bipartite. == Related Problems == Generalizations: General Graph MCM Subproblem: Planar Bipartite Graph Perfect Matching == Parameters == <pre>V: number of vertices E: number of edges</pre>...")
- 11:20, 15 February 2023 Convex Polyhedral Window (hist | edit) [669 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Convex Polyhedral Window (Line Clipping)}} == Description == Line clipping is the process of removing lines or portions of lines outside an area of interest. Typically; any line or part thereof which is outside of the viewing area is removed. Here, the viewing area is a convex polyhedron. == Related Problems == Subproblem: Convex Polygonal Window Related: Rectangular Window == Parameters == <pre>n: number of lines p: number of faces on pol...")
- 11:20, 15 February 2023 Convex Polygonal Window (hist | edit) [1,178 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Convex Polygonal Window (Line Clipping)}} == Description == Line clipping is the process of removing lines or portions of lines outside an area of interest. Typically; any line or part thereof which is outside of the viewing area is removed. Here, the viewing area is a convex polygon. == Related Problems == Generalizations: Convex Polyhedral Window Subproblem: Rectangular Window == Parameters == <pre>n: number of lines p: number of edges o...")
- 11:20, 15 February 2023 Rectangular Window (hist | edit) [1,635 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Rectangular Window (Line Clipping)}} == Description == Line clipping is the process of removing lines or portions of lines outside an area of interest. Typically; any line or part thereof which is outside of the viewing area is removed. Here, the viewing area is rectangular. == Related Problems == Generalizations: Convex Polygonal Window Related: Convex Polyhedral Window == Parameters == <pre>n: number of lines</pre> == Table of Algorithm...")
- 11:20, 15 February 2023 Edit Sequence, constant-size alphabet (hist | edit) [1,287 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Edit Sequence, constant-size alphabet (Sequence Alignment)}} == Description == Given two strings, determine the shortest sequence of edits required to transform one of the strings into the other. Assume we have a constant-size alphabet. == Related Problems == Generalizations: Edit Distance, constant-size alphabet == Parameters == <pre>n, m: lengths of input strings; assume n≥m</pre> == Table of Algorithms == {| class="wikitable sortable"...")
- 11:20, 15 February 2023 Edit Distance, constant-size alphabet (hist | edit) [599 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Edit Distance, constant-size alphabet (Sequence Alignment)}} == Description == Given two strings, determine the minimum number of edits required to transform one of the strings into the other. Assume we have a constant-size alphabet. == Related Problems == Subproblem: Edit Sequence, constant-size alphabet == Parameters == <pre>n, m: lengths of input strings; assume n≥m</pre> == Table of Algorithms == Currently no algorithms in our database...")
- 11:20, 15 February 2023 Multiple String Search (hist | edit) [1,523 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Multiple String Search (String Search)}} == Description == Multiple string search algorithms try to find a place where one or several strings (also called patterns) are found within a larger string or text. == Related Problems == Related: Single String Search == Parameters == <pre>$m$: longest pattern length $n$: length of searchable text $s$: size of the alphabet $k$: number of patterns to search for $z$: number of matches</pre> == Table of A...")
- 11:20, 15 February 2023 Single String Search (hist | edit) [4,574 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Single String Search (String Search)}} == Description == Single string search algorithms try to find a place where a string (also called a pattern) is found within a larger string or text. == Related Problems == Related: Multiple String Search == Parameters == <pre>$m$: pattern length $n$: length of searchable text $s$: size of the alphabet</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%"...")
- 11:20, 15 February 2023 Square Matrix LU Decomposition (hist | edit) [2,138 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Square Matrix LU Decomposition (LU Decomposition)}} == Description == Lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. In this specific case, the input is a square $n \times n$ matrix == Related Problems == Generalizations: Rectangular Matrix LU Decomposition == Parameters == <pre>$n$: dimension of square matrix</pre> == Table of Algorithms == {| cl...")
- 11:20, 15 February 2023 Rectangular Matrix LU Decomposition (hist | edit) [1,067 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Rectangular Matrix LU Decomposition (LU Decomposition)}} == Description == Lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. In the general case, the input is an $m \times n$ matrix. == Related Problems == Subproblem: Square Matrix LU Decomposition == Parameters == <pre>$m$: number of rows in input matrix $n$: number of columns in input matrix $l$: numb...")
- 11:20, 15 February 2023 Smallest Factor (hist | edit) [513 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Smallest Factor (Integer Factoring)}} == Description == Given an $n$-bit integer $N$, find a non-trivial factorization $N=pq$ (where $p, q>1$ are integers) or return that $N$ is prime. For "second category" algorithms, the running time depends solely on the size of the integer to be factored == Related Problems == Related: Integer Factoring == Parameters == <pre>n: number of bits in the integer</pre> == Table of Algorithms == Currently no al...")
- 11:20, 15 February 2023 Integer Factoring (hist | edit) [5,101 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Integer Factoring (Integer Factoring)}} == Description == Given an $n$-bit integer $N$, find a non-trivial factorization $N=pq$ (where $p, q>1$ are integers) or return that $N$ is prime. For "first category" algorithms, the running time depends on the size of smallest prime factor. == Related Problems == Related: Smallest Factor == Parameters == <pre>n: number of bits in the integer B: bound parameter (if needed)</pre> == Table of Algorithms =...")
- 11:20, 15 February 2023 (5/3)-approximate ap-shortest paths (hist | edit) [1,489 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:(5/3)-approximate ap-shortest paths (All-Pairs Shortest Paths (APSP))}} == Description == Approximate APSP within a factor of 5/3. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirected Graphs with Positive Integer Weights, APSP on Sparse Directed Graphs with...")
- 11:20, 15 February 2023 APSP on Sparse Undirected Unweighted Graphs (hist | edit) [1,634 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Sparse Undirected Unweighted Graphs (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is undirected, and is unweighted (or equivalently, has all unit weights). == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighte...")
- 11:20, 15 February 2023 APSP on Sparse Directed Unweighted Graphs (hist | edit) [1,078 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Sparse Directed Unweighted Graphs (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is directed, and is unweighted (or equivalently, has all unit weights). == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Gr...")
- 11:20, 15 February 2023 APSP on Dense Undirected Unweighted Graphs (hist | edit) [1,634 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Undirected Unweighted Graphs (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is undirected, and is unweighted (or equivalently, has all unit weights). == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighte...")
- 11:20, 15 February 2023 APSP on Dense Directed Unweighted Graphs (hist | edit) [1,079 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Directed Unweighted Graphs (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is directed, and is unweighted (or equivalently, has all unit weights). == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Gr...")
- 11:20, 15 February 2023 APSP on Sparse Undirected Graphs with Arbitrary Weights (hist | edit) [1,608 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Sparse Undirected Graphs with Arbitrary Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is undirected, and has arbitrary weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP o...")
- 11:20, 15 February 2023 APSP on Sparse Undirected Graphs with Positive Integer Weights (hist | edit) [1,731 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Sparse Undirected Graphs with Positive Integer Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is undirected, and has positive integer weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Grap...")
- 11:20, 15 February 2023 APSP on Sparse Directed Graphs with Arbitrary Weights (hist | edit) [1,046 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Sparse Directed Graphs with Arbitrary Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is directed, and has arbitrary weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on De...")
- 11:20, 15 February 2023 APSP on Dense Undirected Graphs with Positive Integer Weights (hist | edit) [1,731 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Undirected Graphs with Positive Integer Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is undirected, and has positive integer weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Grap...")
- 11:20, 15 February 2023 APSP on Geometrically Weighted Graphs (hist | edit) [1,608 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Geometrically Weighted Graphs (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider may be dense or sparse, may be directed or undirected, and has weights from a fixed set of $c$ values. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Dense Undirected Graph...")
- 11:20, 15 February 2023 APSP on Dense Undirected Graphs with Arbitrary Weights (hist | edit) [1,917 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Undirected Graphs with Arbitrary Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is undirected, and has arbitrary weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirected Graphs with Positive Integer Weights, [...")
- 11:20, 15 February 2023 APSP on Dense Directed Graphs with Arbitrary Weights (hist | edit) [2,104 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Directed Graphs with Arbitrary Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is directed, and has arbitrary weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirected Graphs with Positive Integer Weights, A...")
- 11:19, 15 February 2023 APSP (hist | edit) [4,258 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP (All-Pairs Shortest Paths (APSP))}} == Description == The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. == Related Problems == Subproblem: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirec...")
- 11:19, 15 February 2023 Replacement Paths Problem (hist | edit) [869 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Replacement Paths Problem (Shortest Path (Directed Graphs))}} == Description == Given nodes $s$ and $t$ in a weighted directed graph and a shortest path $P$ from $s$ to $t$, compute the length of the shortest simple path that avoids edge $e$, for all edges $e$ on $P$ == Related Problems == Generalizations: st-Shortest Path Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, Second Shortest Simple Path, 1-...")
- 11:19, 15 February 2023 2-sensitive decremental st-shortest paths (hist | edit) [1,349 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-sensitive decremental st-shortest paths (Shortest Path (Directed Graphs))}} == Description == Determine the st-shortest path with a sensitivity of 2 using decremental techniques. == Related Problems == Generalizations: st-Shortest Path Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, Second Shortest Simple Path, 1-sensitive (3/2)-approximate ss-shortest paths, 2-sensitive (7/5)-approximate st-sho...")
- 11:19, 15 February 2023 1-sensitive decremental st-shortest paths (hist | edit) [1,748 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:1-sensitive decremental st-shortest paths (Shortest Path (Directed Graphs))}} == Description == Determine the st-shortest path with a sensitivity of 1 using decremental techniques. == Related Problems == Generalizations: st-Shortest Path Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, Second Shortest Simple Path, 1-sensitive (3/2)-approximate ss-shortest paths, 2-sensitive (7/5)-approximate st-sho...")
- 11:19, 15 February 2023 2-sensitive (7/5)-approximate st-shortest paths (hist | edit) [1,332 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-sensitive (7/5)-approximate st-shortest paths (Shortest Path (Directed Graphs))}} == Description == Approximate the st-shortest paths problem within a factor of 7/5 with a sensitivity of 2. == Related Problems == Generalizations: st-Shortest Path Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, Second Shortest Simple Path, 1-sensitive (3/2)-approximate ss-shortest paths, 1-sensitive decremental s...")
- 11:19, 15 February 2023 1-sensitive (3/2)-approximate ss-shortest paths (hist | edit) [1,326 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:1-sensitive (3/2)-approximate ss-shortest paths (Shortest Path (Directed Graphs))}} == Description == Approximate the single source shortest paths problem within a factor of 3/2 with a sensitivity of 1. == Related Problems == Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, Second Shortest Simple Path, st-Shortest Path, 2-sensitive (7/5)-approximate st-shortest paths, 1-sensitive decremental st-shor...")
- 11:19, 15 February 2023 St-Shortest Path (hist | edit) [957 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:st-Shortest Path (Shortest Path (Directed Graphs))}} == Description == Given a weighted digraph $G=(V,E)$, find the shortest path between two given vertices $s$ and $t$. == Related Problems == Subproblem: Second Shortest Simple Path, 2-sensitive (7/5)-approximate st-shortest paths, 1-sensitive decremental st-shortest paths, 2-sensitive decremental st-shortest paths, Replacement Paths Problem Related: General Weights, Non...")
- 11:19, 15 February 2023 Second Shortest Simple Path (hist | edit) [2,123 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Second Shortest Simple Path (Shortest Path (Directed Graphs))}} == Description == Given a weighted digraph $G=(V,E)$, find the second shortest path between two given vertices $s$ and $t$. == Related Problems == Generalizations: st-Shortest Path Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, 1-sensitive (3/2)-approximate ss-shortest paths, 2-sensitive (7/5)-approximate st-shortest paths, 1-sensiti...")
- 11:19, 15 February 2023 Nonnegative Integer Weights (hist | edit) [2,175 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Nonnegative Integer Weights (Shortest Path (Directed Graphs))}} == Description == The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. Here, the weights are restricted to be nonnegative integers. == Related Problems == Generalizations: nonnegative weights Related: General Weights, Nonnegative Weights, Second Shortest...")
- 11:19, 15 February 2023 Nonnegative Weights (hist | edit) [2,754 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Nonnegative Weights (Shortest Path (Directed Graphs))}} == Description == The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. Here, the weights are restricted to be nonnegative. == Related Problems == Generalizations: general weights Subproblem: Nonnegative Integer Weights Related: General Weights, Second Shortest S...")
- 11:19, 15 February 2023 General Weights (hist | edit) [892 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:General Weights (Shortest Path (Directed Graphs))}} == Description == The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. Here, the weights can be any real number. == Related Problems == Subproblem: Nonnegative Weights Related: Nonnegative Integer Weights, Second Shortest Simple Path, st-Shortest Path, 1-sensitiv...")
- 11:19, 15 February 2023 2-dimensional array representation (hist | edit) [1,207 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-dimensional array representation (Closest Pair Problem)}} == Description == Given $n$ points in 2-dimensional space in array representation, find a pair of points with the smallest distance between them. == Related Problems == Related: k-dimensional space, $l_m$ (or $l_\infty$) norm, 2-dimensional space, $l_m$ (or $l_\infty$) norm, 2-dimensional space, Euclidean metric == Parameters == No parameters found. == Table of Algorithms ==...")
- 11:19, 15 February 2023 2-dimensional space, Euclidean metric (hist | edit) [1,306 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-dimensional space, Euclidean metric (Closest Pair Problem)}} == Description == Given $n$ points in 2-dimensional space equipped with the Eucildean metric, find a pair of points with the smallest distance between them. == Related Problems == Related: k-dimensional space, $l_m$ (or $l_\infty$) norm, 2-dimensional space, $l_m$ (or $l_\infty$) norm, 2-dimensional array representation == Parameters == No parameters found. == Table of Alg...")
- 11:19, 15 February 2023 2-dimensional space, $l m$ (or $l \infty$) norm (hist | edit) [1,002 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-dimensional space, $l_m$ (or $l_\infty$) norm (Closest Pair Problem)}} == Description == Given $n$ points in 2-dimensional space equipped with the $l_m$ (or $l_\infty$) norm, find a pair of points with the smallest distance between them. == Related Problems == Generalizations: k-dimensional space, $l_m$ (or $l_\infty$) norm Related: 2-dimensional space, Euclidean metric, 2-dimensional array representation == Parameters == No paramet...")
- 11:19, 15 February 2023 K-dimensional space, $l m$ (or $l \infty$) norm (hist | edit) [1,019 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:k-dimensional space, $l_m$ (or $l_\infty$) norm (Closest Pair Problem)}} == Description == Given $n$ points in metric space, typically $k$-dimensional space equipped with $l_m$ (or $l_\infty$) norm, find a pair of points with the smallest distance between them. == Related Problems == Subproblem: 2-dimensional space, $l_m$ (or $l_\infty$) norm Related: 2-dimensional space, Euclidean metric, 2-dimensional array representation == Parameter...")
- 11:19, 15 February 2023 Directed (Optimum Branchings), Super Dense MST (hist | edit) [1,378 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Directed (Optimum Branchings), Super Dense MST (Minimum Spanning Tree (MST))}} == Description == A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, we're given a directed graph with a root and $E=\Omega(V^2)$ edges, and we wish to find a spanning arborescence...")
- 11:19, 15 February 2023 Directed (Optimum Branchings), General MST (hist | edit) [2,137 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Directed (Optimum Branchings), General MST (Minimum Spanning Tree (MST))}} == Description == A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, we're given a directed graph with a root, and we wish to find a spanning arborescence of minimum weight that is root...")
- 11:19, 15 February 2023 Undirected, Integer Weights MST (hist | edit) [1,285 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Undirected, Integer Weights MST (Minimum Spanning Tree (MST))}} == Description == A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, we assume that the edges have integer weights, represented in binary. == Related Problems == Generalizations: Undirected,...")
- 11:19, 15 February 2023 Undirected, Planar MST (hist | edit) [1,206 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Undirected, Planar MST (Minimum Spanning Tree (MST))}} == Description == A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, we assume that the graph is planar. == Related Problems == Generalizations: Undirected, General MST Related: Undirected, Dense...")
- 11:19, 15 February 2023 Undirected, Dense MST (hist | edit) [1,226 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Undirected, Dense MST (Minimum Spanning Tree (MST))}} == Description == A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, we assume that the graph is dense (i.e. $E = \Omega(V)$). == Related Problems == Generalizations: Undirected, General MST Related...")
- 11:19, 15 February 2023 Undirected, General MST (hist | edit) [5,489 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Undirected, General MST (Minimum Spanning Tree (MST))}} == Description == A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, there are no restrictions on edge weights or graph density. == Related Problems == Subproblem: Undirected, Dense MST, Undirec...")
- 11:19, 15 February 2023 Connected Subgraph (hist | edit) [744 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Connected Subgraph (Strongly Connected Components)}} == Description == Subgraph connectivity asks us to maintainan understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by "on" vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.) == Related Problems == Related: Strongly Connected Components, Transitive Closure,...")
- 11:19, 15 February 2023 2 Strong Components (dynamic) (hist | edit) [1,193 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2 Strong Components (dynamic) (Strongly Connected Components)}} == Description == maintain: a directed graph, under: edge insertion/deletions, answer: are there more than 2 strongly connected components? == Related Problems == Related: Strongly Connected Components, Transitive Closure, Maximum Strongly Connected Component, Strong Connectivity (dynamic), Connected Subgraph == Parameters == No parameters found. == Table of Algori...")
- 11:19, 15 February 2023 Strong Connectivity (dynamic) (hist | edit) [1,263 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Strong Connectivity (dynamic) (Strongly Connected Components)}} == Description == maintain: a directed graph, under edge insertions/deletions, answer: is the graph strongly connected? == Related Problems == Related: Strongly Connected Components, Transitive Closure, Maximum Strongly Connected Component, 2 Strong Components (dynamic), Connected Subgraph == Parameters == No parameters found. == Table of Algorithms == Currently...")
- 11:19, 15 February 2023 Maximum Strongly Connected Component (hist | edit) [557 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum Strongly Connected Component (Strongly Connected Components)}} == Description == maintain: a directed graph, under: edge insertions/deletions, answer: what is the size of the largest SCC? == Related Problems == Related: Strongly Connected Components, Transitive Closure, Strong Connectivity (dynamic), 2 Strong Components (dynamic), Connected Subgraph == Parameters == No parameters found. == Table of Algorithms == Curre...")
- 11:19, 15 February 2023 Transitive Closure (hist | edit) [1,060 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Transitive Closure (Strongly Connected Components)}} == Description == In this problem, we also want to compute the transitive closure of a graph. (Perhaps this should be a separate problem?) == Related Problems == Related: Strongly Connected Components, Maximum Strongly Connected Component, Strong Connectivity (dynamic), 2 Strong Components (dynamic), Connected Subgraph == Parameters == <pre>V: number of vertices E: number of e...")
- 11:19, 15 February 2023 2-dimensional Convex Hull, Dynamic (hist | edit) [1,411 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-dimensional Convex Hull, Dynamic (Convex Hull)}} == Description == Here, the input points may be sequentially inserted or deleted, and the convex hull must be updated after each insert/delete operation. == Related Problems == Generalizations: 2-dimensional Convex Hull Related: 3-dimensional Convex Hull, d-dimensional Convex Hull, 2-dimensional Convex Hull, Online == Parameters == <pre>n: number of line segments h: number of point...")
- 11:19, 15 February 2023 2-dimensional Convex Hull, Online (hist | edit) [1,340 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-dimensional Convex Hull, Online (Convex Hull)}} == Description == Here, we are given the input points one by one, and must maintain the current convex hull after each input point. == Related Problems == Generalizations: 2-dimensional Convex Hull Related: 3-dimensional Convex Hull, d-dimensional Convex Hull, 2-dimensional Convex Hull, Dynamic == Parameters == <pre>n: number of line segments h: number of points on the convex hull</...")
- 11:19, 15 February 2023 D-dimensional Convex Hull (hist | edit) [1,690 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:d-dimensional Convex Hull (Convex Hull)}} == Description == Here, we are looking at the general d-dimensional case. == Related Problems == Subproblem: 2-dimensional Convex Hull, 3-dimensional Convex Hull Related: 3-dimensional Convex Hull, 2-dimensional Convex Hull, Online, 2-dimensional Convex Hull, Dynamic == Parameters == <pre>n: number of line segments h: number of points on the convex hull f_1: number of facets on the con...")
- 11:19, 15 February 2023 3-dimensional Convex Hull (hist | edit) [932 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3-dimensional Convex Hull (Convex Hull)}} == Description == Here, we are looking at the 3-dimensional case. == Related Problems == Generalizations: d-dimensional Convex Hull Related: 2-dimensional Convex Hull, 2-dimensional Convex Hull, Online, 2-dimensional Convex Hull, Dynamic == Parameters == <pre>n: number of line segments h: number of points on the convex hull</pre> == Table of Algorithms == {| class="wikitable sortable" s...")
- 11:19, 15 February 2023 2-dimensional Convex Hull (hist | edit) [1,996 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-dimensional Convex Hull (Convex Hull)}} == Description == The convex hull or convex envelope or convex closure of a set X of points in the Euclidean plane or in a Euclidean space (or; more generally; in an affine space over the reals) is the smallest convex set that contains X. Here, we are looking at the 2-dimensional case. == Related Problems == Generalizations: d-dimensional Convex Hull Subproblem: 2-dimensional Convex Hull, Online, 2...")
- 11:19, 15 February 2023 Counting number of intersection points, line segments (hist | edit) [792 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Counting number of intersection points, line segments (Line segment intersection)}} == Description == In this case, we are supplied with a list of line segments, and we wish to count the number of points of intersection. == Related Problems == Generalizations: Reporting all intersection points, line segments Related: Reporting all intersection points, generalized segments, Reporting all intersection points, convex polygons, Reporting al...")
- 11:18, 15 February 2023 Reporting all intersection points, general polygons (hist | edit) [811 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Reporting all intersection points, general polygons (Line segment intersection)}} == Description == In this case, we are supplied with a list of polygons (not necessarily convex), and we wish to report all regions of intersection. == Related Problems == Subproblem: Reporting all intersection points, convex polygons Related: Reporting all intersection points, line segments, Reporting all intersection points, generalized segments, Countin...")
- 11:18, 15 February 2023 Reporting all intersection points, convex polygons (hist | edit) [1,428 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Reporting all intersection points, convex polygons (Line segment intersection)}} == Description == In this case, we are supplied with a list of convex polygons, and we wish to report all regions of intersection. == Related Problems == Generalizations: Reporting all intersection points, general polygons Related: Reporting all intersection points, line segments, Reporting all intersection points, generalized segments, Counting number of i...")
- 11:18, 15 February 2023 Reporting all intersection points, generalized segments (hist | edit) [1,961 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Reporting all intersection points, generalized segments (Line segment intersection)}} == Description == In this case, the segments are generalized (i.e. have algebraic degree ≥1); we still wish to report all points of intersection. == Related Problems == Subproblem: Reporting all intersection points, line segments Related: Reporting all intersection points, convex polygons, Reporting all intersection points, general polygons, Counting...")
- 11:18, 15 February 2023 Reporting all intersection points, line segments (hist | edit) [2,457 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Reporting all intersection points, line segments (Line segment intersection)}} == Description == The line segment intersection problem supplies a list of line segments in the Euclidean plane and asks about the points where they intersect (cross), if any. In this case, we wish to report all points of intersection. == Related Problems == Generalizations: Reporting all intersection points, generalized segments Subproblem: Counting number of inters...")
- 11:18, 15 February 2023 0-1 Linear Programming (hist | edit) [3,138 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:0-1 Linear Programming (Linear Programming)}} == Description == In this case, we require all of the variables to be either 0 or 1. == Related Problems == Generalizations: Integer Linear Programming Related: General Linear Programming, Linear Programming with Reals == Parameters == <pre>n: number of variables m: number of constraints L: length of input, in bits</pre> == Table of Algorithms == {| class="wikitable sortable" style="tex...")
- 11:18, 15 February 2023 Integer Linear Programming (hist | edit) [3,145 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Integer Linear Programming (Linear Programming)}} == Description == In this case, we require all of the variables to be integers. == Related Problems == Generalizations: Linear Programming with Reals Subproblem: 0-1 Linear Programming Related: General Linear Programming == Parameters == <pre>n: number of variables m: number of constraints L: length of input, in bits</pre> == Table of Algorithms == {| class="wikitable sortable" sty...")
- 11:18, 15 February 2023 Linear Programming with Reals (hist | edit) [3,212 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Linear Programming with Reals (Linear Programming)}} == Description == In this case, we allow all of the variables to be any real number. == Related Problems == Generalizations: General Linear Programming Subproblem: Integer Linear Programming Related: 0-1 Linear Programming == Parameters == <pre>n: number of variables m: number of constraints L: length of input, in bits</pre> == Table of Algorithms == {| class="wikitable sortable"...")
- 11:18, 15 February 2023 General Linear Programming (hist | edit) [3,395 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:General Linear Programming (Linear Programming)}} == Description == Linear programming (LP; also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). == Related Problems == Subproblem: Linear Programming wi...")
- 11:18, 15 February 2023 Vandermonde Matrix (hist | edit) [1,246 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Vandermonde Matrix (Linear System)}} == Description == In this case, we restrict $A$ to be a Vandermonde matrix. == Related Problems == Generalizations: General Linear System Related: Sparse Linear System, Positive Definite, Hermitian Matrix, Non-Definite, Symmetric Matrix, Toeplitz Matrix == Parameters == <pre>n: number of variables and number of equations m: number of nonzero entries in matrix k: ratio between largest and sma...")
- 11:18, 15 February 2023 Toeplitz Matrix (hist | edit) [1,569 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Toeplitz Matrix (Linear System)}} == Description == In this case, we restrict $A$ to be a Toeplitz matrix. == Related Problems == Generalizations: General Linear System Related: Sparse Linear System, Positive Definite, Hermitian Matrix, Non-Definite, Symmetric Matrix, Vandermonde Matrix == Parameters == <pre>n: number of variables and number of equations m: number of nonzero entries in matrix k: ratio between largest and smalle...")
- 11:18, 15 February 2023 Non-Definite, Symmetric Matrix (hist | edit) [1,286 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Non-Definite, Symmetric Matrix (Linear System)}} == Description == In this case, we restrict $A$ to be non-definite and symmetric. == Related Problems == Generalizations: General Linear System Related: Sparse Linear System, Positive Definite, Hermitian Matrix, Toeplitz Matrix, Vandermonde Matrix == Parameters == <pre>n: number of variables and number of equations m: number of nonzero entries in matrix k: ratio between largest a...")
- 11:18, 15 February 2023 Positive Definite, Hermitian Matrix (hist | edit) [1,494 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Positive Definite, Hermitian Matrix (Linear System)}} == Description == In this case, we restrict $A$ to be positive definite and hermitian (or symmetric, if $A$ is real-valued). == Related Problems == Generalizations: General Linear System Related: Sparse Linear System, Non-Definite, Symmetric Matrix, Toeplitz Matrix, Vandermonde Matrix == Parameters == <pre>n: number of variables and number of equations m: number of nonzero e...")
- 11:18, 15 February 2023 Sparse Linear System (hist | edit) [1,042 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Sparse Linear System (Linear System)}} == Description == In this case, we restrict $A$ to be sparse (i.e. $A$ only has $O(n)$ nonzero entries). == Related Problems == Generalizations: General Linear System Related: Positive Definite, Hermitian Matrix, Non-Definite, Symmetric Matrix, Toeplitz Matrix, Vandermonde Matrix == Parameters == <pre>n: number of variables and number of equations m: number of nonzero entries in matrix k:...")
- 11:18, 15 February 2023 General Linear System (hist | edit) [1,592 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:General Linear System (Linear System)}} == Description == A system of linear equations (or linear system) is a collection of one or more linear equations involving the same set of variables. This is typically written in the form $Ax=b$ where $A$ is a matrix and $x, b$ are vectors. In this case, we impose no restrictions on $A$. == Related Problems == Subproblem: Sparse Linear System, Positive Definite, Hermitian Matrix, Non-Definite, Symme...")
- 11:18, 15 February 2023 $(\min, \leq)$ Product (hist | edit) [954 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:$(\min, \leq)$ Product (Matrix Product)}} == Description == Matrix product over the $(\min, \leq)$-semiring == Related Problems == Related: Matrix Multiplication, Boolean Matrix Multiplication, Boolean Matrix Multiplication (Combinatorial), Matrix Product Verification, Distance Product == Parameters == <pre>n: dimension of square matrix</pre> == Table of Algorithms == Currently no algorithms in our database for the given prob...")
- 11:18, 15 February 2023 Distance Product (hist | edit) [1,495 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Distance Product (Matrix Product)}} == Description == Matrix product over the $(\min, +)$-semiring == Related Problems == Related: Matrix Multiplication, Boolean Matrix Multiplication, Boolean Matrix Multiplication (Combinatorial), Matrix Product Verification, $(\min, \leq)$ Product == Parameters == <pre>n: dimension of square matrix</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem...")
- 11:18, 15 February 2023 Matrix Product Verification (hist | edit) [990 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Matrix Product Verification (Matrix Product)}} == Description == Given three matrices $A, B, C$, verify that $AB = C$, i.e. that $C$ is the matrix product of $A$ and $B$ == Related Problems == Generalizations: Matrix Multiplication Related: Boolean Matrix Multiplication, Boolean Matrix Multiplication (Combinatorial), Distance Product, $(\min, \leq)$ Product == Parameters == <pre>n: dimension of square matrix</pre> == Table of...")
- 11:18, 15 February 2023 Boolean Matrix Multiplication (Combinatorial) (hist | edit) [2,533 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Boolean Matrix Multiplication (Combinatorial) (Matrix Product)}} == Description == Matrix multiplication of two boolean matrices (i.e. where all entries are in $F_2$ and addition is mod 2). Here, only "combinatorial" algorithms are considered. == Related Problems == Generalizations: Boolean Matrix Multiplication Related: Matrix Multiplication, Matrix Product Verification, Distance Product, $(\min, \leq)$ Product == Parameters ==...")
- 11:18, 15 February 2023 Boolean Matrix Multiplication (hist | edit) [7,916 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Boolean Matrix Multiplication (Matrix Product)}} == Description == Matrix multiplication of two boolean matrices (i.e. where all entries are in $F_2$ and addition is mod 2) == Related Problems == Generalizations: Matrix Multiplication Subproblem: Boolean Matrix Multiplication (Combinatorial) Related: Matrix Product Verification, Distance Product, $(\min, \leq)$ Product == Parameters == <pre>n: dimension of square matrix</pre>...")
- 11:18, 15 February 2023 Maximum Local Edge Connectivity (hist | edit) [6,062 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum Local Edge Connectivity (Maximum Flow)}} == Description == Find the pair of nodes with the maximum number of edge-disjoint paths between them == Related Problems == Related: st-Maximum Flow, Integer Maximum Flow, Unweighted Maximum Flow, Non-integer Maximum Flow, Minimum-Cost Flow, All-Pairs Maximum Flow == Parameters == <pre>V: number of vertices E: number of edges</pre> == Table of Algorithms == {| class="wikita...")
- 11:18, 15 February 2023 All-Pairs Maximum Flow (hist | edit) [6,440 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:All-Pairs Maximum Flow (Maximum Flow)}} == Description == Find the maximum flow between all pairs of nodes == Related Problems == Related: st-Maximum Flow, Integer Maximum Flow, Unweighted Maximum Flow, Non-integer Maximum Flow, Minimum-Cost Flow, Maximum Local Edge Connectivity == Parameters == <pre>V: number of vertices E: number of edges</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:c...")
- 11:18, 15 February 2023 Minimum-Cost Flow (hist | edit) [5,740 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Minimum-Cost Flow (Maximum Flow)}} == Description == Maximum flow problems involve finding a feasible flow through a flow network that is maximum. In this variant, each edge is given a cost coefficient, and we wish to minimize total cost while reaching a threshold flow. == Related Problems == Related: st-Maximum Flow, Integer Maximum Flow, Unweighted Maximum Flow, Non-integer Maximum Flow, All-Pairs Maximum Flow, Maximum Local Ed...")
- 11:18, 15 February 2023 Non-integer Maximum Flow (hist | edit) [5,591 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Non-integer Maximum Flow (Maximum Flow)}} == Description == Maximum flow problems involve finding a feasible flow through a flow network that is maximum. In this variant, the capacities may be non-integers. == Related Problems == Subproblem: Integer Maximum Flow Related: st-Maximum Flow, Unweighted Maximum Flow, Minimum-Cost Flow, All-Pairs Maximum Flow, Maximum Local Edge Connectivity == Parameters == <pre>V: number of ver...")
- 11:18, 15 February 2023 Unweighted Maximum Flow (hist | edit) [5,622 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Unweighted Maximum Flow (Maximum Flow)}} == Description == Maximum flow problems involve finding a feasible flow through a flow network that is maximum. In this variant, all edges have unit weight. == Related Problems == Generalizations: Integer Maximum Flow Related: st-Maximum Flow, Non-integer Maximum Flow, Minimum-Cost Flow, All-Pairs Maximum Flow, Maximum Local Edge Connectivity == Parameters == <pre>V: number of vertic...")
- 11:18, 15 February 2023 Integer Maximum Flow (hist | edit) [6,683 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Integer Maximum Flow (Maximum Flow)}} == Description == Maximum flow problems involve finding a feasible flow through a flow network that is maximum. In this variant, the capacities must be integers. == Related Problems == Generalizations: Non-Integer Maximum Flow Subproblem: Unweighted Maximum Flow Related: st-Maximum Flow, Non-integer Maximum Flow, Minimum-Cost Flow, All-Pairs Maximum Flow, Maximum Local Edge Connectivity...")
- 11:18, 15 February 2023 St-Maximum Flow (hist | edit) [7,829 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:st-Maximum Flow (Maximum Flow)}} == Description == Find the maximum flow from $s$ to $t$ == Related Problems == Related: Integer Maximum Flow, Unweighted Maximum Flow, Non-integer Maximum Flow, Minimum-Cost Flow, All-Pairs Maximum Flow, Maximum Local Edge Connectivity == Parameters == <pre>V: number of vertices E: number of edges U: maximum edge capacity</pre> == Table of Algorithms == {| class="wikitable sortable" style...")
- 11:18, 15 February 2023 Longest Common Substring with don't cares (hist | edit) [1,356 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Longest Common Substring with don't cares (Longest Common Subsequence)}} == Description == Find the length of the longest common substring of two strings S and T, where S is a binary string and T is is a binary string and additional * characters that can match either 0 or 1. == Related Problems == Generalizations: Longest Common Subsequence == Parameters == <pre>$n$: length of the longer input string $m$: length of the shorter input string $r$:...")
- 11:18, 15 February 2023 Longest Common Subsequence (hist | edit) [1,377 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Longest Common Subsequence (Longest Common Subsequence)}} == Description == 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). == Related Problems == Subproblem: Longest Common Substring with don't cares == Parameters == <pre>$n$: length of the longer input string $m$: length of the shorter input string $r$: length of the LCS $s...")
- 11:17, 15 February 2023 Approximate MCSP (hist | edit) [1,377 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Approximate MCSP (Matrix Chain Multiplication)}} == Description == The Matrix Chain Scheduling Problem (or MCSP) is an optimization problem� where the goal is to find the product sequence for evaluating a chain of matrix products and the processor schedule for the sequence such that the evaluation time is minimized on a parallel system. In the approximation problem, the matrix multiplication carried out with the output result will use a number of opera...")
- 11:17, 15 February 2023 Matrix Chain Scheduling Problem (hist | edit) [1,194 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Matrix Chain Scheduling Problem (Matrix Chain Multiplication)}} == Description == The Matrix Chain Scheduling Problem (or MCSP) is an optimization problem� where the goal is to find the product sequence for evaluating a chain of matrix products and the processor schedule for the sequence such that the evaluation time is minimized on a parallel system. == Related Problems == Generalizations: Matrix Chain Ordering Problem Subproblem: Approximat...")
- 11:17, 15 February 2023 Approximate MCOP (hist | edit) [2,012 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Approximate MCOP (Matrix Chain Multiplication)}} == Description == Matrix chain multiplication (or Matrix Chain Ordering Problem; MCOP) is an optimization problem. Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. In the approximation problem, the matrix multiplication carried out with the output result will use a number of operations that has some sort of upper bound based on the optimal solution. == R...")
- 11:17, 15 February 2023 Matrix Chain Ordering Problem (hist | edit) [1,541 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Matrix Chain Ordering Problem (Matrix Chain Multiplication)}} == Description == Matrix chain multiplication (or Matrix Chain Ordering Problem; MCOP) is an optimization problem. Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. == Related Problems == Subproblem: Approximate MCOP, Matrix Chain Scheduling Problem Related: Matrix Chain Scheduling Problem, Approximate MCSP == Parameters...")
- 11:17, 15 February 2023 Kth Order Statistic (hist | edit) [1,166 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:kth Order Statistic (kth Order Statistic)}} == Description == An algorithm seeks to find the $k^{th}$ order statistic of a statistical sample, or the $k^{th}$-smallest value in a list or array. == Parameters == <pre>n: size of list</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Naive Selection (kth Order St...")
- 11:17, 15 February 2023 Non-Comparison Sorting (hist | edit) [2,528 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Non-Comparison Sorting (Sorting)}} == Description == A sorting algorithm is an algorithm that puts elements of a list in a certain order, not using comparisons between elements (so elements are typically integers or real numbers). == Related Problems == Generalizations: Sorting Related: Comparison Sorting == Parameters == <pre>n: size of list</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width...")
- 11:17, 15 February 2023 Comparison Sorting (hist | edit) [5,958 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Comparison Sorting (Sorting)}} == Description == A sorting algorithm is an algorithm that puts elements of a list in a certain order, using comparisons between elements. == Related Problems == Generalizations: Sorting Related: Non-Comparison Sorting == Parameters == <pre>n: size of list</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation...")
- 11:17, 15 February 2023 Sorting (hist | edit) [5,924 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Sorting (Sorting)}} == Description == A sorting algorithm is an algorithm that puts elements of a list in a certain order == Related Problems == Subproblem: Comparison Sorting, Non-Comparison Sorting Related: Non-Comparison Sorting == Parameters == <pre>n: size of list</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Time Complexity graph == 1000px ==...")
- 11:17, 15 February 2023 Family:3SUM (hist | edit) [193 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3SUM}}== Description == Currently no description in our database for the given family. == Problems Variations == * 3SUM * 3SUM' * All-Integers 3SUM * Real 3SUM")
- 11:17, 15 February 2023 Family:Dihedral Rotation Queries (hist | edit) [230 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Dihedral Rotation Queries}}== Description == Currently no description in our database for the given family. == Problems Variations == * Dynamic Dihedral Rotation Queries * Static Dihedral Rotation Queries")
- 11:17, 15 February 2023 Family:Model-Checking Problem (hist | edit) [510 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Model-Checking Problem}}== Description == Currently no description in our database for the given family. == Problems Variations == * Conjunctive Reachability Queries in MDPs * Conjunctive Safety Queries in MDPs * Disjunctive Queries of Safety in Graphs * Disjunctive Reachability Queries in MDPs * Disjunctive Safety Queries in MDPs * Disjunctive coBüchi Objectives * Generalized Büchi Games * Reachability in MDPs * Safe...")
- 11:17, 15 February 2023 Family:Vertex Reachability (hist | edit) [360 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Vertex Reachability}}== Description == Currently no description in our database for the given family. == Problems Variations == * #SSR * 1-sensitive incremental ss-reach * 2-sensitive incremental st-reach * ST-Reach * ap-reach * constant sensitivity incremental ST-Reach * sensitive incremental #SSR * st-Reach")
- 11:17, 15 February 2023 Family:Matrix-Vector Multiplication (hist | edit) [245 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Matrix-Vector Multiplication}}== Description == Currently no description in our database for the given family. == Problems Variations == * Online Matrix-Vector Multiplication * Online Vector-Matrix-Vector Multiplication")
- 11:17, 15 February 2023 Family:Graph Cycles (hist | edit) [182 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Graph Cycles}}== Description == Currently no description in our database for the given family. == Problems Variations == * Shortest Cycle * Shortest k-Cycle")
- 11:17, 15 February 2023 Family:Minimum Witness (hist | edit) [203 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Minimum Witness}}== Description == Currently no description in our database for the given family. == Problems Variations == * All Pairs Minimum Witness * Minimum Witness Finding")
- 11:17, 15 February 2023 Family:Local Alignment (hist | edit) [194 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Local Alignment}}== Description == Currently no description in our database for the given family. == Problems Variations == * Local Alignment * Multiple Local Alignment")
- 11:17, 15 February 2023 Family:Motion Planning Problems (hist | edit) [204 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Motion Planning Problems}}== Description == Currently no description in our database for the given family. == Problems Variations == * 3D Motion Planning * Planar Motion Planning")
- 11:17, 15 February 2023 Family:Geometric Visibility Problems (hist | edit) [243 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Geometric Visibility Problems}}== Description == Currently no description in our database for the given family. == Problems Variations == * Visibility Between Segments * Visibility From Infinity * Visible Triangle")
- 11:17, 15 February 2023 Family:Geometric Covering Problems (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Geometric Covering Problems}}== Description == Currently no description in our database for the given family. == Problems Variations == * Hole in Union * Max-Weight Rectangle * Point Covering * Strips Cover Box * Triangle Measure * Triangles Cover Triangle * Weighted Depth")
- 11:17, 15 February 2023 Family:Geometric Separator Problems (hist | edit) [188 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Geometric Separator Problems}}== Description == Currently no description in our database for the given family. == Problems Variations == * Separator1 * Separator2")
- 11:17, 15 February 2023 Family:Geometric Incidence Problems (hist | edit) [200 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Geometric Incidence Problems}}== Description == Currently no description in our database for the given family. == Problems Variations == * 3 Points on Line * Point on 3 Lines")
- 11:17, 15 February 2023 Family:Graph Triangle Problems (hist | edit) [385 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Graph Triangle Problems}}== Description == Currently no description in our database for the given family. == Problems Variations == * Minimum Triangle * Negative Triangle Detection * Negative Triangle Listing * Negative Triangle Search * Nondecreasing Triangle * Triangle Collection* * Triangle Detection * Triangle in Unweighted Graph")
- 11:17, 15 February 2023 Family:Vertex Centrality (hist | edit) [560 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Vertex Centrality}}== Description == Currently no description in our database for the given family. == Problems Variations == * All-Nodes Median Parity * Approximate Betweenness Centrality * Approximate Reach Centrality * Betweenness Centrality * Directed All-Nodes Positive Betweenness Centrality * Directed All-Nodes Reach Centrality * Eccentricity * Positive Betweenness Centrality * Reach Centrality * Undirected Al...")
- 11:17, 15 February 2023 Family:Graph Metrics (hist | edit) [501 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Graph Metrics}}== Description == Currently no description in our database for the given family. == Problems Variations == * 1-sensitive (4/3)-approximate decremental diameter * 1-sensitive (4/3)-approximate decremental eccentricity * 1-sensitive decremental diameter * Approximate Diameter * Decremental Diameter * Diameter * Diameter 2 vs 3 * Diameter 3 vs 7 * Median * Radius * constant sensitivity (4/3)-approxim...")
- 11:17, 15 February 2023 Family:Orthogonal Vectors (hist | edit) [195 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Orthogonal Vectors}}== Description == Currently no description in our database for the given family. == Problems Variations == * 3-OV * OV * Unbalanced OV * k-OV")
- 11:17, 15 February 2023 Family:Boolean Satisfiability (hist | edit) [577 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Boolean Satisfiability}}== Description == Currently no description in our database for the given family. == Problems Variations == * 1-in-3SAT * 2SAT * 3SAT * 3SAT-5 * 4SAT * All-Equal-SAT * Conjunctive Normal Form SAT * Disjunctive Normal Form SAT * Dual-Horn SAT * Horn SAT * MaxSAT * Monotone 1-in-3SAT * Monotone 3SAT * Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT) * Monotone Not-Exactly-1-i...")
- 11:17, 15 February 2023 Family:Graph Coloring (hist | edit) [398 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Graph Coloring}}== Description == Currently no description in our database for the given family. == Problems Variations == * #2-Graph Coloring * #3-Graph Coloring * #4-Graph Coloring * #5-Graph Coloring * #k-Graph Coloring * 2-Graph Coloring * 3-Graph Coloring * 4-Graph Coloring * 5-Graph Coloring * Chromatic Number * k-Graph Coloring")
- 11:16, 15 February 2023 Family:Recovery (hist | edit) [178 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Recovery}}== Description == Currently no description in our database for the given family. == Problems Variations == * No-Steal/Force * Steal/No-Force")
- 11:16, 15 February 2023 Family:Page Replacements (hist | edit) [170 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Page Replacements}}== Description == Currently no description in our database for the given family. == Problems Variations == * Offline * Online")
- 11:16, 15 February 2023 Family:Deadlock Avoidance (hist | edit) [203 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Deadlock Avoidance}}== Description == Currently no description in our database for the given family. == Problems Variations == * Deadlock Avoidance * Dining Philosophers Problem")
- 11:16, 15 February 2023 Family:Interval Scheduling (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Interval Scheduling}}== Description == Currently no description in our database for the given family. == Problems Variations == * Unweighted Interval Scheduling * Weighted Interval Schedule Maximization Problem (ISMP)")
- 11:16, 15 February 2023 Family:One-Way Hash Functions (hist | edit) [204 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:One-Way Hash Functions}}== Description == Currently no description in our database for the given family. == Problems Variations == * Keyed Hash Functions * Unkeyed Hash Functions")
- 11:16, 15 February 2023 Family:Integral Equations (hist | edit) [194 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Integral Equations}}== Description == Currently no description in our database for the given family. == Problems Variations == * Fredholm Equations * Volterra Equations")
- 11:16, 15 February 2023 Family:Median String Problem (hist | edit) [301 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Median String Problem}}== Description == Currently no description in our database for the given family. == Problems Variations == * Median String Problem with Binary Alphabets * Median String Problem with Bounded Alphabets * Median String Problem with Unbounded Alphabets")
- 11:16, 15 February 2023 Family:n-Queens Problem (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:n-Queens Problem}}== Description == Currently no description in our database for the given family. == Problems Variations == * Constructing Solutions * Counting Solutions * n-Queens Completion")
- 11:16, 15 February 2023 Family:Integer Relation (hist | edit) [215 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Integer Relation}}== Description == Currently no description in our database for the given family. == Problems Variations == * Integer Relation Among Integers * Integer Relation Among Reals")
- 11:16, 15 February 2023 Family:Wiener Index (hist | edit) [207 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Wiener Index}}== Description == Currently no description in our database for the given family. == Problems Variations == * Minimum Wiener Connector Problem * Undirected Wiener Index")
- 11:16, 15 February 2023 Family:Texture Mapping (hist | edit) [218 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Texture Mapping}}== Description == Currently no description in our database for the given family. == Problems Variations == * Diffuse Reflection * Environment Mapping * Specular Reflection")
- 11:15, 15 February 2023 Family:Link Analysis (hist | edit) [183 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Link Analysis}}== Description == Currently no description in our database for the given family. == Problems Variations == * InDegree Analysis * Link Analysis")
- 11:15, 15 February 2023 Family:The Set-Covering Problem (hist | edit) [208 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:The Set-Covering Problem}}== Description == Currently no description in our database for the given family. == Problems Variations == * Unweighted Set-Covering * Weighted Set-Covering")
- 11:15, 15 February 2023 Family:Feature Detection (hist | edit) [187 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Feature Detection}}== Description == Currently no description in our database for the given family. == Problems Variations == * Blob Detection * Corner Detection")
- 11:15, 15 February 2023 Family:Graph Realization Problems (hist | edit) [216 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Graph Realization Problems}}== Description == Currently no description in our database for the given family. == Problems Variations == * DAG Realization Problem * Digraph Realization Problem")
- 11:15, 15 February 2023 Family:Graph Isomorphism Problem (hist | edit) [403 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Graph Isomorphism Problem}}== Description == Currently no description in our database for the given family. == Problems Variations == * Graph Isomorphism, Bounded Number of Vertices of Each Color * Graph Isomorphism, Bounded Vertex Valences * Graph Isomorphism, General Graphs * Graph Isomorphism, Trivalent Graphs * Largest Common Subtree * Subtree Isomorphism")
- 11:15, 15 February 2023 Family:AST to Code Translation (hist | edit) [219 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:AST to Code Translation}}== Description == Currently no description in our database for the given family. == Problems Variations == * AST to Code Translation * Arithmetic Expression Binary Tree")
- 11:15, 15 February 2023 Family:Maximum Subarray Problem (hist | edit) [255 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum Subarray Problem}}== Description == Currently no description in our database for the given family. == Problems Variations == * 1D Maximum Subarray * 2D Maximum Subarray * Maximum Square Subarray * Maximum Subarray")
- 11:15, 15 February 2023 Family:Stable Matching Problem (hist | edit) [351 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Stable Matching Problem}}== Description == Currently no description in our database for the given family. == Problems Variations == * Almost Stable Marriage Problem * Boolean d-Attribute Stable Matching * Stable Marriage Problem * Stable Matching Verification * Stable Pair Checking * Stable Roommates Problem")
- 11:15, 15 February 2023 Family:Data Compression (hist | edit) [193 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Data Compression}}== Description == Currently no description in our database for the given family. == Problems Variations == * Lossless Compression * Lossy Compression")
- 11:15, 15 February 2023 Family:CFG Problems (hist | edit) [178 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:CFG Problems}}== Description == Currently no description in our database for the given family. == Problems Variations == * CFG Parsing * CFG Recognition")
- 11:15, 15 February 2023 Family:The Vertex Cover Problem (hist | edit) [234 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:The Vertex Cover Problem}}== Description == Currently no description in our database for the given family. == Problems Variations == * The Vertex Cover Problem * The Vertex Cover Problem, Degrees Bounded By 3")
- 11:15, 15 February 2023 Family:4NF Decomposition (hist | edit) [296 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:4NF Decomposition}}== Description == Currently no description in our database for the given family. == Problems Variations == * 4NF Decomposition * 4NF Decomposition for Conflict-Free Dependency Sets * 4NF Decomposition for Functional and Multivalued Dependency Sets")
- 11:15, 15 February 2023 Family:BCNF Decomposition (hist | edit) [191 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:BCNF Decomposition}}== Description == Currently no description in our database for the given family. == Problems Variations == * BCNF Decomposition * Decisional BCNF")
- 11:15, 15 February 2023 Family:Dependency Inference Problem (hist | edit) [247 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Dependency Inference Problem}}== Description == Currently no description in our database for the given family. == Problems Variations == * Functional Dependency Inference Problem * Multivalued Dependency Inference Problem")
- 11:15, 15 February 2023 Family:Poisson Problem (hist | edit) [213 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Poisson Problem}}== Description == Currently no description in our database for the given family. == Problems Variations == * 2-Dimensional Poisson Problem * 3-Dimensional Poisson Problem")
- 11:14, 15 February 2023 Family:The Traveling-Salesman Problem (hist | edit) [214 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:The Traveling-Salesman Problem}}== Description == Currently no description in our database for the given family. == Problems Variations == * Approximate TSP * Maximum TSP * Minimum TSP")
- 11:14, 15 February 2023 Family:Clique Problems (hist | edit) [280 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Clique Problems}}== Description == Currently no description in our database for the given family. == Problems Variations == * Enumerating Maximal Cliques, arbitrary graph * Exact k-Clique * Max-Weight k-Clique * Min-Weight k-Clique * k-Clique")
- 11:14, 15 February 2023 Family:Graph Edit Distance Computation (hist | edit) [191 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Graph Edit Distance Computation}}== Description == Currently no description in our database for the given family. == Problems Variations == * Exact GED * Inexact GED")
- 11:14, 15 February 2023 Family:Lowest Common Ancestor (hist | edit) [407 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Lowest Common Ancestor}}== Description == Currently no description in our database for the given family. == Problems Variations == * Lowest Common Ancestor * Lowest Common Ancestor with Linking * Lowest Common Ancestor with Linking Roots * Lowest Common Ancestor with Static Trees * Lowest Common Ancestors with Linking and Cutting * Off-Line Lowest Common Ancestor")
- 11:14, 15 February 2023 Family:DFA Minimization (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:DFA Minimization}}== Description == Currently no description in our database for the given family. == Problems Variations == * Acyclic DFA Minimization * Cyclic Nontrivial SCCs DFA Minimization * DFA Minimization")
- 11:14, 15 February 2023 Family:Register Allocation (hist | edit) [210 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Register Allocation}}== Description == Currently no description in our database for the given family. == Problems Variations == * Global Register Allocation * Local Register Allocation")
- 11:14, 15 February 2023 Family:Nearest Neighbor Search (hist | edit) [279 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Nearest Neighbor Search}}== Description == Currently no description in our database for the given family. == Problems Variations == * k Approximate Nearest Neighbors Search * k Nearest Neighbors Search")
- 11:14, 15 February 2023 Family:Root Computation (hist | edit) [229 bytes] Admin (talk | contribs) (Redirected page to Root Computation) Tag: New redirect
- 11:14, 15 February 2023 Family:Eigenvalues (Iterative Methods) (hist | edit) [315 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Eigenvalues (Iterative Methods)}}== Description == Currently no description in our database for the given family. == Problems Variations == * All Eigenpairs * All Eigenvalues * Any Eigenpair * Any Eigenvalue * Eigenpair closest to mu * Eigenpair with the Largest Eigenvalue")
- 11:14, 15 February 2023 Family:Polygon Clipping (hist | edit) [249 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Polygon Clipping}}== Description == Currently no description in our database for the given family. == Problems Variations == * Polygon Clipping with Arbitrary Clipping Polygon * Polygon Clipping with Convex Clipping Polygon")
- 11:14, 15 February 2023 Family:Maximum-Weight Matching (hist | edit) [219 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum-Weight Matching}}== Description == Currently no description in our database for the given family. == Problems Variations == * Bipartite Maximum-Weight Matching * Maximum-Weight Matching")
- 11:14, 15 February 2023 Family:Nash Equilibria (hist | edit) [171 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Nash Equilibria}}== Description == Currently no description in our database for the given family. == Problems Variations == * 2-Player * n-Player")
- 11:14, 15 February 2023 Family:Optimal Binary Search Trees (hist | edit) [270 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Optimal Binary Search Trees}}== Description == Currently no description in our database for the given family. == Problems Variations == * Alphabetic Tree Problem * Approximate OBST * Huffman Encoding * Optimal Binary Search Tree Problem")
- 11:14, 15 February 2023 Family:Generating Random Permutations (hist | edit) [209 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Generating Random Permutations}}== Description == Currently no description in our database for the given family. == Problems Variations == * Cyclic Permutations * General Permutations")
- 11:14, 15 February 2023 Family:SDD Systems Solvers (hist | edit) [205 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:SDD Systems Solvers}}== Description == Currently no description in our database for the given family. == Problems Variations == * Exact Laplacian Solver * Inexact Laplacian Solver")
- 11:14, 15 February 2023 Family:Maximum Cardinality Matching (hist | edit) [250 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum Cardinality Matching}}== Description == Currently no description in our database for the given family. == Problems Variations == * Bipartite Graph MCM * General Graph MCM * Planar Bipartite Graph Perfect Matching")
- 11:14, 15 February 2023 Family:Line Clipping (hist | edit) [225 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Line Clipping}}== Description == Currently no description in our database for the given family. == Problems Variations == * Convex Polygonal Window * Convex Polyhedral Window * Rectangular Window")
- 11:14, 15 February 2023 Family:Sequence Alignment (hist | edit) [232 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Sequence Alignment}}== Description == Currently no description in our database for the given family. == Problems Variations == * Edit Distance, constant-size alphabet * Edit Sequence, constant-size alphabet")
- 11:14, 15 February 2023 Family:String Search (hist | edit) [195 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:String Search}}== Description == Currently no description in our database for the given family. == Problems Variations == * Multiple String Search * Single String Search")
- 11:13, 15 February 2023 Family:LU Decomposition (hist | edit) [221 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:LU Decomposition}}== Description == Currently no description in our database for the given family. == Problems Variations == * Rectangular Matrix LU Decomposition * Square Matrix LU Decomposition")
- 11:13, 15 February 2023 Family:Integer Factoring (hist | edit) [189 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Integer Factoring}}== Description == Currently no description in our database for the given family. == Problems Variations == * Integer Factoring * Smallest Factor")
- 11:13, 15 February 2023 Family:All-Pairs Shortest Paths (APSP) (hist | edit) [827 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:All-Pairs Shortest Paths (APSP)}}== Description == Currently no description in our database for the given family. == Problems Variations == * (5/3)-approximate ap-shortest paths * APSP * APSP on Dense Directed Graphs with Arbitrary Weights * APSP on Dense Directed Unweighted Graphs * APSP on Dense Undirected Graphs with Arbitrary Weights * APSP on Dense Undirected Graphs with Positive Integer Weights * APSP on Dense Undirected...")
- 11:13, 15 February 2023 Family:Shortest Path (Directed Graphs) (hist | edit) [532 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Shortest Path (Directed Graphs)}}== Description == Currently no description in our database for the given family. == Problems Variations == * 1-sensitive (3/2)-approximate ss-shortest paths * 1-sensitive decremental st-shortest paths * 2-sensitive (7/5)-approximate st-shortest paths * 2-sensitive decremental st-shortest paths * General Weights * Nonnegative Integer Weights * Nonnegative Weights * Replacement Paths Problem...")
- 11:13, 15 February 2023 Family:Closest Pair Problem (hist | edit) [339 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Closest Pair Problem}}== Description == Currently no description in our database for the given family. == Problems Variations == * 2-dimensional array representation * 2-dimensional space, $l_m$ (or $l_\infty$) norm * 2-dimensional space, Euclidean metric * k-dimensional space, $l_m$ (or $l_\infty$) norm")
- 11:12, 15 February 2023 Family:Minimum Spanning Tree (MST) (hist | edit) [380 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Minimum Spanning Tree (MST)}}== Description == Currently no description in our database for the given family. == Problems Variations == * Directed (Optimum Branchings), General MST * Directed (Optimum Branchings), Super Dense MST * Undirected, Dense MST * Undirected, General MST * Undirected, Integer Weights MST * Undirected, Planar MST")
- 11:12, 15 February 2023 Family:Strongly Connected Components (hist | edit) [356 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Strongly Connected Components}}== Description == Currently no description in our database for the given family. == Problems Variations == * 2 Strong Components (dynamic) * Connected Subgraph * Maximum Strongly Connected Component * Strong Connectivity (dynamic) * Strongly Connected Components * Transitive Closure")
- 11:12, 15 February 2023 Family:Convex Hull (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Convex Hull}}== Description == Currently no description in our database for the given family. == Problems Variations == * 2-dimensional Convex Hull * 2-dimensional Convex Hull, Dynamic * 2-dimensional Convex Hull, Online * 3-dimensional Convex Hull * d-dimensional Convex Hull")
- 11:12, 15 February 2023 Family:Line segment intersection (hist | edit) [443 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Line segment intersection}}== Description == Currently no description in our database for the given family. == Problems Variations == * Counting number of intersection points, line segments * Reporting all intersection points, convex polygons * Reporting all intersection points, general polygons * Reporting all intersection points, generalized segments * Reporting all intersection points, line segments")
- 11:12, 15 February 2023 Family:Linear Programming (hist | edit) [275 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Linear Programming}}== Description == Currently no description in our database for the given family. == Problems Variations == * 0-1 Linear Programming * General Linear Programming * Integer Linear Programming * Linear Programming with Reals")
- 11:12, 15 February 2023 Family:Linear System (hist | edit) [320 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Linear System}}== Description == Currently no description in our database for the given family. == Problems Variations == * General Linear System * Non-Definite, Symmetric Matrix * Positive Definite, Hermitian Matrix * Sparse Linear System * Toeplitz Matrix * Vandermonde Matrix")
- 11:12, 15 February 2023 Family:Matrix Product (hist | edit) [342 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Matrix Product}}== Description == Currently no description in our database for the given family. == Problems Variations == * $(\min, \leq)$ Product * Boolean Matrix Multiplication * Boolean Matrix Multiplication (Combinatorial) * Distance Product * Matrix Multiplication * Matrix Product Verification")
- 11:12, 15 February 2023 Family:Maximum Flow (hist | edit) [339 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum Flow}}== Description == Currently no description in our database for the given family. == Problems Variations == * All-Pairs Maximum Flow * Integer Maximum Flow * Maximum Local Edge Connectivity * Minimum-Cost Flow * Non-integer Maximum Flow * Unweighted Maximum Flow * st-Maximum Flow")
- 11:12, 15 February 2023 Family:Longest Common Subsequence (hist | edit) [233 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Longest Common Subsequence}}== Description == Currently no description in our database for the given family. == Problems Variations == * Longest Common Subsequence * Longest Common Substring with don't cares")
- 11:12, 15 February 2023 Family:Matrix Chain Multiplication (hist | edit) [273 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Matrix Chain Multiplication}}== Description == Currently no description in our database for the given family. == Problems Variations == * Approximate MCOP * Approximate MCSP * Matrix Chain Ordering Problem * Matrix Chain Scheduling Problem")
- 11:11, 15 February 2023 Family:Sorting (hist | edit) [201 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Sorting}}== Description == Currently no description in our database for the given family. == Problems Variations == * Comparison Sorting * Non-Comparison Sorting * Sorting")
- 11:11, 15 February 2023 Domain:Cryptography (hist | edit) [3,125 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Cryptography}}== Description == Cryptography is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages; various aspects in information security such as data confidentiality, data integrity, authentication, and non-repudiation are central to modern cryptography. Mod...")
- 11:11, 15 February 2023 Domain:Statistics (hist | edit) [1,551 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Statistics}}== Description == Machine learning (ML) is the study of computer algorithms that can improve automatically through experience and by the use of data. It is seen as a part of artificial intelligence. Machine learning algorithms build a model based on sample data, known as "training data", in order to make predictions or decisions without being explicitly programmed to do so. Machine learning algorithms are used in a wide variety of applications...")
- 11:11, 15 February 2023 Domain:Robotics (hist | edit) [2,546 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Robotics}}== Description == Robotics is an interdisciplinary field that integrates computer science and engineering. Robotics involves design, construction, operation, and use of robots. The goal of robotics is to design machines that can help and assist humans. Robotics integrates fields of mechanical engineering, electrical engineering, information engineering, mechatronics, electronics, bioengineering, computer engineering, control engineering, softwar...")
- 11:11, 15 February 2023 Domain:Operating Systems (hist | edit) [2,630 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Operating Systems}}== Description == An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs. Time-sharing operating systems schedule tasks for efficient use of the system and may also include accounting software for cost allocation of processor time, mass storage, printing, and other resources. For hardware functions such as input and output and memory allocation...")
- 11:11, 15 February 2023 Domain:Numerical Analysis (hist | edit) [3,113 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Numerical Analysis}}== Description == Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). Numerical analysis finds application in all fields of engineering and the physical sciences, and in the 21st century also the life and social sciences, medicine, business and even the arts. Current growth in computi...")
- 11:11, 15 February 2023 Domain:Image Processing (hist | edit) [2,251 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Image Processing}}== Description == Digital image processing is the use of a digital computer to process digital images through an algorithm. As a subcategory or field of digital signal processing, digital image processing has many advantages over analog image processing. It allows a much wider range of algorithms to be applied to the input data and can avoid problems such as the build-up of noise and distortion during processing. Since images are defined...")
- 11:11, 15 February 2023 Domain:Databases (hist | edit) [1,423 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Databases}}== Description == In computing, a database is an organized collection of data stored and accessed electronically from a computer system. Where databases are more complex they are often developed using formal design and modeling techniques. The database management system (DBMS) is the software that interacts with end users, applications, and the database itself to capture and analyze the data. The DBMS software additionally encompasses the core...")
- 11:11, 15 February 2023 Domain:Combinatorics (hist | edit) [5,333 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Combinatorics}}== Description == == Problems Within Domain == * #2-Graph Coloring * #3-Graph Coloring * #4-Graph Coloring * #5-Graph Coloring * #k-Graph Coloring * $(\min, \leq)$ Product * (5/3)-approximate ap-shortest paths * 1-sensitive (3/2)-approximate ss-shortest paths * 1-sensitive decremental st-shortest paths * 1D Maximum Subarray * 2 Strong Components (dynamic) * 2-Graph Coloring * 2-sensitive...")
- 11:11, 15 February 2023 Domain:Bioinformatics (hist | edit) [1,524 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Bioinformatics}}== Description == Bioinfromatics an interdisciplinary field that develops methods and software tools for understanding biological data, in particular when the data sets are large and complex. As an interdisciplinary field of science, bioinformatics combines biology, computer science, information engineering, mathematics and statistics to analyze and interpret the biological data. Bioinformatics has been used for in silico analyses of biolo...")
- 11:11, 15 February 2023 List:Domains (hist | edit) [437 bytes] Admin (talk | contribs) (Created page with "* Bioinformatics * Combinatorics * Databases * Image Processing * Numerical Analysis * Operating Systems * Robotics * Signal Processing * Statistics * Cryptography")
- 11:11, 15 February 2023 List:Hypotheses (hist | edit) [1,697 bytes] Admin (talk | contribs) (Created page with "* Exponential Time Hypothesis (ETH) * Strong Exponential Time Hypothesis (SETH) * Orthogonal Vectors Hypothesis (OVH) * Unbalanced Orthogonal Vectors Hypothesis (UOVH) * k-OV Hypothesis * k-Clique Hypothesis * 3SUM Hypothesis (3-SUM Hypothes...")
- 11:11, 15 February 2023 List:Problem Families (hist | edit) [10,798 bytes] Admin (talk | contribs) (Created page with "== Bioinformatics == <ul style="display: grid; grid-template-columns: repeat(2, minmax(0, 1fr));"> <li> All Maximal Non-Branching Paths in a Graph</li> <li> Cyclic Peptide Sequencing Problem</li> <li> De Novo Genome Assembly</li> <li> Motif Search</li> <li>Family:Sequence Alignme...")