User contributions for Admin

15 February 2023

• 10:2410:24, 15 February 2023 diff hist +35‎ N Record Linkage ‎ Redirected page to Duplicate Elimination current Tag: New redirect
• 10:2410:24, 15 February 2023 diff hist +1,049‎ Duplicate Elimination ‎No edit summary
• 10:2410:24, 15 February 2023 diff hist +1,170‎ N DAG Realization Problem ‎ Created page with "{{DISPLAYTITLE:DAG Realization Problem (Graph Realization Problems)}} == Description == Given a sequence $S := (a_1, b_1), \ldots, (a_n, b_n)$ with $a_i, b_i \in \mathbb{Z}_0^+$, does there exist a directed acyclic graph (DAG) (no parallel arcs allowed) with labeled vertex set $V := \{v_1, \ldots , v_n\}$ such that for all $v_i \in V$ indegree and outdegree of $v_i$ match exactly the given numbers $a_i$ and $b_i$, respectively? == Related Problems == Generalizations..."
• 10:2410:24, 15 February 2023 diff hist +1,784‎ N Digraph Realization Problem ‎ Created page with "{{DISPLAYTITLE:Digraph Realization Problem (Graph Realization Problems)}} == Description == Given a sequence $S := (a_1, b_1), \ldots, (a_n, b_n)$ with $a_i, b_i \in \mathbb{Z}_0^+$, does there exist a directed graph (no parallel arcs allowed) with labeled vertex set $V := \{v_1, \ldots , v_n\}$ such that for all $v_i \in V$ indegree and outdegree of $v_i$ match exactly the given numbers $a_i$ and $b_i$, respectively? == Related Problems == Subproblem: DAG Realiza..."
• 10:2410:24, 15 February 2023 diff hist +1,796‎ N Subtree Isomorphism ‎ Created page with "{{DISPLAYTITLE:Subtree Isomorphism (Graph Isomorphism Problem)}} == Description == Determine whether a given tree is contained within another tree. == Related Problems == Generalizations: Largest Common Subtree Related: Graph Isomorphism, General Graphs, Graph Isomorphism, Bounded Number of Vertices of Each Color, Graph Isomorphism, Trivalent Graphs, Graph Isomorphism, Bounded Vertex Valences == Parameters == <pre>n: number of vertices in the..."
• 10:2410:24, 15 February 2023 diff hist +36‎ N LCST ‎ Redirected page to Largest Common Subtree current Tag: New redirect
• 10:2410:24, 15 February 2023 diff hist +1,854‎ N Largest Common Subtree ‎ Created page with "{{DISPLAYTITLE:Largest Common Subtree (Graph Isomorphism Problem)}} == Description == Find a largest tree which occurs as a common subgraph in a given collection of trees. == Related Problems == Generalizations: Graph Isomorphism, General Graphs Subproblem: Subtree Isomorphism Related: Graph Isomorphism, Bounded Number of Vertices of Each Color, Graph Isomorphism, Trivalent Graphs, Graph Isomorphism, Bounded Vertex Valences == Parameters ==..."
• 10:2410:24, 15 February 2023 diff hist +1,591‎ N Graph Isomorphism, Bounded Vertex Valences ‎ Created page with "{{DISPLAYTITLE:Graph Isomorphism, Bounded Vertex Valences (Graph Isomorphism Problem)}} == Description == Given two graphs with the degree of each vertex bounded, determine whether they are isomorphic to one another. == Related Problems == Generalizations: Graph Isomorphism, General Graphs Related: Graph Isomorphism, Bounded Number of Vertices of Each Color, Graph Isomorphism, Trivalent Graphs, Largest Common Subtree, Subtree Isomorphism == Par..."
• 10:2410:24, 15 February 2023 diff hist +1,334‎ N Graph Isomorphism, Trivalent Graphs ‎ Created page with "{{DISPLAYTITLE:Graph Isomorphism, Trivalent Graphs (Graph Isomorphism Problem)}} == Description == Given two trivalent graphs (AKA cubic graphs--graphs in which each vertex has degree 3), determine whether they are isomorphic to one another. == Related Problems == Generalizations: Graph Isomorphism, General Graphs Related: Graph Isomorphism, Bounded Number of Vertices of Each Color, Graph Isomorphism, Bounded Vertex Valences, Largest Common Subtree,..."
• 10:2410:24, 15 February 2023 diff hist +1,699‎ N Graph Isomorphism, Bounded Number of Vertices of Each Color ‎ Created page with "{{DISPLAYTITLE:Graph Isomorphism, Bounded Number of Vertices of Each Color (Graph Isomorphism Problem)}} == Description == Given two colored graphs with the number of vertices of each color bounded, determine whether they are isomorphic to one another. == Related Problems == Generalizations: Graph Isomorphism, General Graphs Related: Graph Isomorphism, Trivalent Graphs, Graph Isomorphism, Bounded Vertex Valences, Largest Common Subtree, Subtree Is..."
• 10:2410:24, 15 February 2023 diff hist +1,726‎ N Graph Isomorphism, General Graphs ‎ Created page with "{{DISPLAYTITLE:Graph Isomorphism, General Graphs (Graph Isomorphism Problem)}} == Description == Given two graphs, determine whether they are isomorphic to one another. == Related Problems == Subproblem: Graph Isomorphism, Bounded Number of Vertices of Each Color, Graph Isomorphism, Trivalent Graphs, Graph Isomorphism, Bounded Vertex Valences, Largest Common Subtree Related: Graph Isomorphism, Trivalent Graphs, Graph Isomorphism, Bounded Ve..."
• 10:2410:24, 15 February 2023 diff hist +1,125‎ N Arithmetic Expression Binary Tree ‎ Created page with "{{DISPLAYTITLE:Arithmetic Expression Binary Tree (AST to Code Translation)}} == Description == Translate a given arithmetic expression binary tree into machine-readable code that uses as few registers as possible. == Related Problems == Related: AST to Code Translation == Parameters == <pre>$n$: number of nodes in the tree</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space..."
• 10:2310:23, 15 February 2023 diff hist +685‎ N AST to Code Translation ‎ Created page with "{{DISPLAYTITLE:AST to Code Translation (AST to Code Translation)}} == Description == Translate a given abstract syntax tree (AST) into machine-readable code that uses as few registers as possible. == Related Problems == Related: Arithmetic Expression Binary Tree == Parameters == <pre>$n$: number of nodes in the tree</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Time Complexity graph == File:AST to Co..."
• 10:2310:23, 15 February 2023 diff hist +1,858‎ N Longest Palindromic Substring ‎ Created page with "{{DISPLAYTITLE:Longest Palindromic Substring (Longest Palindromic Substring)}} == Description == Given a string of length $n$, find the palindromic substrings of maximal length. == Parameters == <pre>n: length of given string</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Naive (Longest Palindromic Substring Longest Palin..."
• 10:2310:23, 15 February 2023 diff hist +31‎ N ER ‎ Redirected page to Entity Resolution current Tag: New redirect
• 10:2310:23, 15 February 2023 diff hist +2,438‎ N Entity Resolution ‎ Created page with "{{DISPLAYTITLE:Entity Resolution (Entity Resolution)}} == Description == Entity resolution (ER) is the problem of matching records that represent the same real-world entity and then merging the matching records. ER is a well known problem that arises in many applications. An exhaustive ER process involves comparing all the pairs of records, which can be very expensive for large datasets. == Parameters == No parameters found. == Table of Algorithms == {| class="wi..."
• 10:2310:23, 15 February 2023 diff hist +1,257‎ N Ray Tracing ‎ 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..." current
• 10:2310:23, 15 February 2023 diff hist +3,361‎ N Constructing Suffix Trees ‎ 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:2310:23, 15 February 2023 diff hist +940‎ N Maximum Square Subarray ‎ 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:2310:23, 15 February 2023 diff hist +1,463‎ N 2D Maximum Subarray ‎ 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:2310:23, 15 February 2023 diff hist +33‎ N Maximum Subsequence ‎ Redirected page to 1D Maximum Subarray current Tag: New redirect
• 10:2310:23, 15 February 2023 diff hist +2,708‎ N 1D Maximum Subarray ‎ 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:2310:23, 15 February 2023 diff hist +1,986‎ N Maximum Subarray ‎ 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:2310:23, 15 February 2023 diff hist +1,472‎ N Longest Path on Interval Graphs ‎ 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:2310:23, 15 February 2023 diff hist +2,046‎ N Stable Pair Checking ‎ 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:2310:23, 15 February 2023 diff hist +1,078‎ N Stable Matching Verification ‎ 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:2310:23, 15 February 2023 diff hist +1,537‎ N Boolean d-Attribute Stable Matching ‎ 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:2310:23, 15 February 2023 diff hist +38‎ N SRP ‎ Redirected page to Stable Roommates Problem current Tag: New redirect
• 10:2310:23, 15 February 2023 diff hist +1,743‎ N Stable Roommates Problem ‎ 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:2310:23, 15 February 2023 diff hist +980‎ N Almost Stable Marriage Problem ‎ 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:2310:23, 15 February 2023 diff hist +37‎ N Stable Matching Problem, SMP ‎ Redirected page to Stable Marriage Problem current Tag: New redirect
• 10:2310:23, 15 February 2023 diff hist +3,023‎ N Stable Marriage Problem ‎ 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:2310:23, 15 February 2023 diff hist +428‎ Cryptanalysis of Linear Feedback Shift Registers ‎No edit summary
• 10:2310:23, 15 February 2023 diff hist +1,046‎ N Factorization of Polynomials Over Finite Fields ‎ 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:2310:23, 15 February 2023 diff hist +567‎ N Lossless Compression ‎ 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:2310:23, 15 February 2023 diff hist +3,599‎ N Lossy Compression ‎ 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:2310:23, 15 February 2023 diff hist +39‎ N Finding Association Rules ‎ Redirected page to Finding Frequent Itemsets current Tag: New redirect
• 10:2310:23, 15 February 2023 diff hist +1,779‎ N Finding Frequent Itemsets ‎ 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:2310:23, 15 February 2023 diff hist +2,105‎ N CFG Recognition ‎ 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:2310:23, 15 February 2023 diff hist +2,407‎ N CFG Parsing ‎ 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:2310:23, 15 February 2023 diff hist +60‎ N 3DVC ‎ Redirected page to The Vertex Cover Problem, Degrees Bounded By 3 current Tag: New redirect
• 10:2310:23, 15 February 2023 diff hist +1,070‎ N The Vertex Cover Problem, Degrees Bounded By 3 ‎ 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:2310:23, 15 February 2023 diff hist +38‎ N VC ‎ Redirected page to The Vertex Cover Problem current Tag: New redirect
• 10:2310:23, 15 February 2023 diff hist +4,666‎ N The Vertex Cover Problem ‎ 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:2310:23, 15 February 2023 diff hist +566‎ Disk Scheduling ‎No edit summary
• 10:2310:23, 15 February 2023 diff hist +2,779‎ N 4NF Decomposition for Conflict-Free Dependency Sets ‎ 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:2310:23, 15 February 2023 diff hist +3,028‎ N 4NF Decomposition for Functional and Multivalued Dependency Sets ‎ 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:2310:23, 15 February 2023 diff hist +31‎ N Fourth Normal Form Decomposition ‎ Redirected page to 4NF Decomposition current Tag: New redirect
• 10:2310:23, 15 February 2023 diff hist +2,174‎ N 4NF Decomposition ‎ 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:2310:23, 15 February 2023 diff hist +29‎ N Decisional Boyce-Codd Normal Form ‎ Redirected page to Decisional BCNF current Tag: New redirect