New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:23, 15 February 2023 Ray Tracing (hist | edit) [1,257 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Ray Tracing (Ray Tracing)}} == Description == Ray tracing is an image rendering technique in which rays are cast from the viewpoint and followed as they reflect off of objects in the scene. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Dürer rendering algorithm ( Ray Tracin...")
- 10:23, 15 February 2023 Constructing Suffix Trees (hist | edit) [3,185 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Constructing Suffix Trees (Constructing Suffix Trees)}} == Description == Let $T = t_1 t_2 \cdots t_n, be a string over an alphabet $\Sigma$. Each string $x$ such that $T = uxv$ for some (possibly empty) strings $u$ and $v$ is a substring of $T$, and each string $T_i = t_i \cdots t_n$, where $1 \leq i \leq n + 1$ is a suffix of $T$; in particular, $T_{n+1} = \epsilon$ is the empty suffix. The set of all suffixes of $T$ is denoted $\sigma(T)$. The suffix...")
- 10:23, 15 February 2023 Maximum Square Subarray (hist | edit) [931 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum Square Subarray (Maximum Subarray Problem)}} == Description == Given an $n \times n$ matrix find a maximum subarray with sides of equal length. == Related Problems == Generalizations: Maximum Subarray Related: 1D Maximum Subarray, 2D Maximum Subarray == Parameters == <pre>n: dimension of array</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| cl...")
- 10:23, 15 February 2023 2D Maximum Subarray (hist | edit) [1,454 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2D Maximum Subarray (Maximum Subarray Problem)}} == Description == Given an $n \times n$ matrix $A$ of integers, find $i, j, k,l \in (n)$ with $i \leq j, k \leq l$ maximizing $\sum^j_{x=i}\sum^l_{y=k}A(x,y)$, that is, find a contiguous subarray of $A$ of maximum sum == Related Problems == Generalizations: Maximum Subarray Related: 1D Maximum Subarray, Maximum Square Subarray == Parameters == <pre>n: dimension of array</pre> == Table o...")
- 10:23, 15 February 2023 1D Maximum Subarray (hist | edit) [2,453 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:1D Maximum Subarray (Maximum Subarray Problem)}} == Description == Given an array $A$ of length $n$, find $i, j$ with $1\leq i \leq j \leq n$ maximizing $\sum^j_{x=i} A(x)$, that is, find a contiguous subarray of $A$ of maximum sum == Related Problems == Generalizations: Maximum Subarray Related: 2D Maximum Subarray, Maximum Square Subarray == Parameters == <pre>n: length of array</pre> == Table of Algorithms == {| class="wikitable...")
- 10:23, 15 February 2023 Maximum Subarray (hist | edit) [3,820 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum Subarray (Maximum Subarray Problem)}} == Description == Given a $d$-dimensional array $M$ with $n^d$ real-valued entries, find the $d$-dimensional subarray of $M$ which maximizes the sum of the elements it contains. == Related Problems == Subproblem: 1D Maximum Subarray, 2D Maximum Subarray, Maximum Square Subarray Related: 2D Maximum Subarray, Maximum Square Subarray == Parameters == <pre>n: length of array d: dimens...")
- 10:23, 15 February 2023 Longest Path on Interval Graphs (hist | edit) [1,175 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Longest Path on Interval Graphs (Longest Path Problem)}} == Description == The longest path problem is the problem of finding a path of maximum length in a graph. A graph $G$ is called interval graph if its vertices can be put in a one-to-one correspondence with a family $F$ of intervals on the real line such that two vertices are adjacent in $G$ if and only if the corresponding intervals intersect; $F$ is called an intersection model for $G$. == Param...")
- 10:23, 15 February 2023 Stable Pair Checking (hist | edit) [2,059 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Stable Pair Checking (Stable Matching Problem)}} == Description == Verify that a given pairing is stable, given the preferences == Related Problems == Generalizations: Stable Marriage Problem Related: Almost Stable Marriage Problem, Stable Roommates Problem, Boolean d-Attribute Stable Matching, Stable Matching Verification == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database...")
- 10:23, 15 February 2023 Stable Matching Verification (hist | edit) [1,096 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Stable Matching Verification (Stable Matching Problem)}} == Description == Verify that a given matching is stable, given the preferences == Related Problems == Generalizations: Stable Marriage Problem Related: Almost Stable Marriage Problem, Stable Roommates Problem, Boolean d-Attribute Stable Matching, Stable Pair Checking == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our databas...")
- 10:23, 15 February 2023 Boolean d-Attribute Stable Matching (hist | edit) [1,582 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Boolean d-Attribute Stable Matching (Stable Matching Problem)}} == Description == SMP in the d-attribute model. In the d-attribute model, we assume that there are d different attributes (e.g. income, height, sense of humor, etc.) with a fixed, possibly objective, ranking of the men for each attribute. Each woman’s preference list is based on a linear combination of the attributes of the men, where each woman can have different weights for each attribut...")
- 10:23, 15 February 2023 Stable Roommates Problem (hist | edit) [1,504 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Stable Roommates Problem (Stable Matching Problem)}} == Description == Given $2n$ participants, each of participant ranks the others in strict order of preference. A matching is a set of $n$ disjoint pairs of participants. A matching $M$ in an instance of SRP is stable if there are no two participants $x$ and $y$, each of whom prefers the other to their partner in $M$. Such a pair is said to block $M$, or to be a blocking pair with respect to $M$. == Re...")
- 10:23, 15 February 2023 Almost Stable Marriage Problem (hist | edit) [971 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Almost Stable Marriage Problem (Stable Matching Problem)}} == Description == The task in the Almost Stable Marriage Problem is to find a matching that minimises the number of unstable edges, but the matching does not have to be a maximum matching. == Related Problems == Generalizations: Stable Marriage Problem Related: Stable Roommates Problem, Boolean d-Attribute Stable Matching, Stable Matching Verification, Stable Pair Checking...")
- 10:23, 15 February 2023 Stable Marriage Problem (hist | edit) [3,036 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Stable Marriage Problem (Stable Matching Problem)}} == Description == Given $n$ men and $n$ women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable. == Related Problems == Generalizations: ...")
- 10:23, 15 February 2023 Factorization of Polynomials Over Finite Fields (hist | edit) [864 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Factorization of Polynomials Over Finite Fields (Factorization of Polynomials Over Finite Fields)}} == Description == Factor a given polynomial over a finite field into a product of irreducible polynomials. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Schubert's algorithm (...")
- 10:23, 15 February 2023 Lossless Compression (hist | edit) [591 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Lossless Compression (Data Compression)}} == Description == The reduction or ideally elimination of redundancies in the original data to result in smaller required storage space is the goal of every compression scheme. There are two categories of data compression: lossy and lossless. Lossless compression is fully information-preserving and fully reversible. == Related Problems == Related: Lossy Compression == Parameters == No parameters found....")
- 10:23, 15 February 2023 Lossy Compression (hist | edit) [3,479 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Lossy Compression (Data Compression)}} == Description == The reduction or ideally elimination of redundancies in the original data to result in smaller required storage space is the goal of every compression scheme. There are two categories of data compression: lossy and lossless. Lossy compression is achieved by only discarding the redundancies and out of human perception information and getting rid of those extra bits. == Related Problems == Relat...")
- 10:23, 15 February 2023 Finding Frequent Itemsets (hist | edit) [1,631 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Finding Frequent Itemsets (Finding Frequent Itemsets)}} == Description == We assume there is a number $s$, called the support threshold. If $I$ is a set of items, the support for $I$ is the number of baskets for which $I$ is a subset. We say $I$ is frequent if its support is $s$ or more == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Sp...")
- 10:23, 15 February 2023 CFG Recognition (hist | edit) [1,934 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:CFG Recognition (CFG Problems)}} == Description == Given a grammar $G$ and a string $s$, determine if the string $s$ can be derived by the grammar $G$. == Related Problems == Related: CFG Parsing == Parameters == <pre>n: length of the given string</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Cocke...")
- 10:23, 15 February 2023 CFG Parsing (hist | edit) [2,174 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:CFG Parsing (CFG Problems)}} == Description == Given a grammar $G$ and a string $s$, find the parse structure, or analysis, assigned to the string $s$ by the grammar $G$. == Related Problems == Related: CFG Recognition == Parameters == <pre>n: length of the given string</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Re...")
- 10:23, 15 February 2023 The Vertex Cover Problem, Degrees Bounded By 3 (hist | edit) [1,254 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:The Vertex Cover Problem, Degrees Bounded By 3 (The Vertex Cover Problem)}} == Description == A vertex cover of a graph $G$ is a set $C$ of vertices such that every edge of $G$ has at least one endpoint in $C$. The vertex cover problem is to find a minimum-size vertex cover in a given graph $G$. This version of the problem is such that the input graph $G$ has all vertices' degree bounded by 3. == Related Problems == Generalizations: The Vertex Cover...")
- 10:23, 15 February 2023 The Vertex Cover Problem (hist | edit) [5,138 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:The Vertex Cover Problem (The Vertex Cover Problem)}} == Description == A vertex cover of a graph $G$ is a set $C$ of vertices such that every edge of $G$ has at least one endpoint in $C$. The vertex cover problem is to find a minimum-size vertex cover in a given graph $G$. == Related Problems == Subproblem: The Vertex Cover Problem, Degrees Bounded By 3 == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sort...")
- 10:23, 15 February 2023 4NF Decomposition for Conflict-Free Dependency Sets (hist | edit) [2,820 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:4NF Decomposition for Conflict-Free Dependency Sets (4NF Decomposition)}} == Description == 4NF Decomposition is the problem of decomposing a relation schema into fourth normal form (4NF). This variation specifies that the input dependency set is conflict-free. 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 \r...")
- 10:23, 15 February 2023 4NF Decomposition for Functional and Multivalued Dependency Sets (hist | edit) [3,069 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:4NF Decomposition for Functional and Multivalued Dependency Sets (4NF Decomposition)}} == Description == 4NF Decomposition is the problem of decomposing a relation schema into fourth normal form (4NF). This variation specifies that the input dependency set has only functional and multivalued dependencies. A relation schema $R^*$ is in fourth normal form (4NF) if, whenever a nontrivial multivalued dependency $X \rightarrow \rightarrow Y$ holds for $R^*$,...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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 |- | ...")
- 10: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....")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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.")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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 $...")
- 10: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...")
- 10: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...")
- 10: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, ...")
- 10: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...")
- 10: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...")
- 10: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...")