All public logs

Combined display of all available logs of Algorithm Wiki. You can narrow down the view by selecting a log type, the username (case-sensitive), or the affected page (also case-sensitive).

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)

• 10:20, 15 February 2023 Admin talk contribs created page Inexact Laplacian Solver (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...")
• 10:20, 15 February 2023 Admin talk contribs created page Symmetric Diagonally Dominant System Solvers (Redirected page to Exact Laplacian Solver) Tag: New redirect
• 10:20, 15 February 2023 Admin talk contribs created page Exact Laplacian Solver (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...")
• 10:20, 15 February 2023 Admin talk contribs created page Key Exchange (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...")
• 10:20, 15 February 2023 Admin talk contribs created page Planar Bipartite Graph Perfect Matching (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...")
• 10:20, 15 February 2023 Admin talk contribs created page General Graph MCM (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...")
• 10:20, 15 February 2023 Admin talk contribs created page Bipartite Graph MCM (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>...")
• 10:20, 15 February 2023 Admin talk contribs created page Convex Polyhedral Window (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...")
• 10:20, 15 February 2023 Admin talk contribs created page Convex Polygonal Window (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...")
• 10:20, 15 February 2023 Admin talk contribs created page Rectangular Window (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...")
• 10:20, 15 February 2023 Admin talk contribs created page Edit Sequence, constant-size alphabet (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"...")
• 10:20, 15 February 2023 Admin talk contribs created page Edit Distance, constant-size alphabet (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...")
• 10:20, 15 February 2023 Admin talk contribs created page Multiple String Search (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...")
• 10:20, 15 February 2023 Admin talk contribs created page Single String Search (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%"...")
• 10:20, 15 February 2023 Admin talk contribs created page Square Matrix LU Decomposition (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...")
• 10:20, 15 February 2023 Admin talk contribs created page Rectangular Matrix LU Decomposition (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...")
• 10:20, 15 February 2023 Admin talk contribs created page Second Category Integer Factoring (Redirected page to Smallest Factor) Tag: New redirect
• 10:20, 15 February 2023 Admin talk contribs created page Smallest Factor (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...")
• 10:20, 15 February 2023 Admin talk contribs created page First Category Integer Factoring (Redirected page to Integer Factoring) Tag: New redirect
• 10:20, 15 February 2023 Admin talk contribs created page Integer Factoring (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 =...")
• 10:20, 15 February 2023 Admin talk contribs created page (5/3)-approximate ap-shortest paths (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...")
• 10:20, 15 February 2023 Admin talk contribs created page APSP on Sparse Undirected Unweighted Graphs (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...")
• 10:20, 15 February 2023 Admin talk contribs created page APSP on Sparse Directed Unweighted Graphs (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...")
• 10:20, 15 February 2023 Admin talk contribs created page APSP on Dense Undirected Unweighted Graphs (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...")
• 10:20, 15 February 2023 Admin talk contribs created page APSP on Dense Directed Unweighted Graphs (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...")
• 10:20, 15 February 2023 Admin talk contribs created page APSP on Sparse Undirected Graphs with Arbitrary Weights (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...")
• 10:20, 15 February 2023 Admin talk contribs created page APSP on Sparse Undirected Graphs with Positive Integer Weights (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...")
• 10:20, 15 February 2023 Admin talk contribs created page APSP on Sparse Directed Graphs with Arbitrary Weights (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...")
• 10:20, 15 February 2023 Admin talk contribs created page APSP on Dense Undirected Graphs with Positive Integer Weights (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...")
• 10:20, 15 February 2023 Admin talk contribs created page APSP on Geometrically Weighted Graphs (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...")
• 10:20, 15 February 2023 Admin talk contribs created page APSP on Dense Undirected Graphs with Arbitrary Weights (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, [...")
• 10:20, 15 February 2023 Admin talk contribs created page APSP on Dense Directed Graphs with Arbitrary Weights (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...")
• 10:19, 15 February 2023 Admin talk contribs created page All-Pairs Shortest Paths (Redirected page to APSP) Tag: New redirect
• 10:19, 15 February 2023 Admin talk contribs created page APSP (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...")
• 10:19, 15 February 2023 Admin talk contribs created page RPP (Redirected page to Replacement Paths Problem) Tag: New redirect
• 10:19, 15 February 2023 Admin talk contribs created page Replacement Paths Problem (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-...")
• 10:19, 15 February 2023 Admin talk contribs created page 2-sensitive decremental st-shortest paths (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...")
• 10:19, 15 February 2023 Admin talk contribs created page 1-sensitive decremental st-shortest paths (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...")
• 10:19, 15 February 2023 Admin talk contribs created page 2-sensitive (7/5)-approximate st-shortest paths (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...")
• 10:19, 15 February 2023 Admin talk contribs created page 1-sensitive (3/2)-approximate ss-shortest paths (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...")
• 10:19, 15 February 2023 Admin talk contribs created page St-Shortest Path (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...")
• 10:19, 15 February 2023 Admin talk contribs created page Second Shortest Simple Path (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...")
• 10:19, 15 February 2023 Admin talk contribs created page Nonnegative Integer Weights (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...")
• 10:19, 15 February 2023 Admin talk contribs created page Nonnegative Weights (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...")
• 10:19, 15 February 2023 Admin talk contribs created page General Weights (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...")
• 10:19, 15 February 2023 Admin talk contribs created page 2-dimensional array representation (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 ==...")
• 10:19, 15 February 2023 Admin talk contribs created page 2-dimensional space, Euclidean metric (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...")
• 10:19, 15 February 2023 Admin talk contribs created page 2-dimensional space, $l m$ (or $l \infty$) norm (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...")
• 10:19, 15 February 2023 Admin talk contribs created page K-dimensional space, $l m$ (or $l \infty$) norm (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...")
• 10:19, 15 February 2023 Admin talk contribs created page Directed (Optimum Branchings), Super Dense MST (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...")

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)