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 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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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.")
- 10: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.")
- 10: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.")
- 10: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 ==...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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.")
- 10: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.")
- 10: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 |...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")
- 10: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...")