New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 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...")
- 10:21, 15 February 2023 N-Player (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:n-Player (Nash Equilibria)}} == Description == Here, given the payoff matrices for an $n$-player game, determine a Nash equilibrium. == Related Problems == Subproblem: 2-Player == Parameters == <pre>n: number of players</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem.")
- 10:21, 15 February 2023 2-Player (hist | edit) [723 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-Player (Nash Equilibria)}} == Description == In game theory, the Nash equilibrium, named after the mathematician John Forbes Nash Jr., is a proposed solution of a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy. As an algorithmic problem, given the payoff matrices for a bimatrix game, determine...")
- 10:21, 15 February 2023 Alphabetic Tree Problem (hist | edit) [1,454 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Alphabetic Tree Problem (Optimal Binary Search Trees)}} == Description == A variant of the OBST problem is when only the gaps have nonzero access probabilities, and is called the optimal alphabetic tree problem. == Related Problems == Generalizations: Optimal Binary Search Tree Problem Related: Approximate OBST, Huffman Encoding == Parameters == <pre>n: number of elements</pre> == Table of Algorithms == {| class="wikitable sortable"...")
- 10:21, 15 February 2023 Approximate OBST (hist | edit) [2,086 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Approximate OBST (Optimal Binary Search Trees)}} == Description == Suppose we are given $n$ keys and the probabilities of accessing each key and those occurring in the gap between two successive keys. The approximate optimal binary search tree problem is to construct a binary search tree on these $n$ keys, whose expected access time is within an approximation factor of the optimal time. == Related Problems == Generalizations: Optimal Binary Search T...")
- 10:21, 15 February 2023 Optimal Binary Search Tree Problem (hist | edit) [678 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Optimal Binary Search Tree Problem (Optimal Binary Search Trees)}} == Description == Suppose we are given $n$ keys and the probabilities of accessing each key and those occurring in the gap between two successive keys. The optimal binary search tree problem is to construct a binary search tree on these $n$ keys that minimizes the expected access time. == Related Problems == Subproblem: Approximate OBST, Huffman Encoding, Alphabetic Tree Pr...")
- 10:21, 15 February 2023 All Permutations (hist | edit) [1,207 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:All Permutations (All Permutations)}} == Description == Generate all permuttaions of the characters/elements in a string/array. == Parameters == <pre>n: number of elements</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Steinhaus–Johnson–Trotter algorithm (All Permutations All Permutations)|Steinhaus–J...")
- 10:21, 15 February 2023 Minimum value in each row of an implicitly-defined totally monotone matrix (hist | edit) [1,585 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Minimum value in each row of an implicitly-defined totally monotone matrix (Minimum value in each row of an implicitly-defined totally monotone matrix)}} == Description == Given a totally monotone matrix $A$ whose entries $A(i, j)$ are implicitly defined by some function $f(i, j)$ (assume $f$ takes constant time to evaluate for all relevant $(i, j)$), determine the minimum value in each row. == Parameters == <pre>n, m: dimensions of matrix; assume m...")
- 10:21, 15 February 2023 Gröbner Bases (hist | edit) [1,658 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Gröbner Bases (Gröbner Bases)}} == Description == In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring $K(x_1, \ldots ,x_n)$ over a field $K$. As an algorithmic problem, given a set of polynomials in $K(x_1, \ldots,x_n)$, determine a Gröbner basis. == Parameters == <pre>n: number of...")
- 10:21, 15 February 2023 Convex Optimization (Non-linear) (hist | edit) [528 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Convex Optimization (Non-linear) (Convex Optimization (Non-linear))}} == Description == Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem. == Time Complexity graph == 1000px == Space...")
- 10:21, 15 February 2023 Cyclic Permutations (hist | edit) [849 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Cyclic Permutations (Generating Random Permutations)}} == Description == Given an input string/array, generate a single random cyclic permutation of the characters/elements of the string/array. == Related Problems == Related: General Permutations == Parameters == <pre>n: number of elements</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation...")
- 10:21, 15 February 2023 General Permutations (hist | edit) [1,294 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:General Permutations (Generating Random Permutations)}} == Description == Given an input string/array, generate a single random permutation of the characters/elements of the string/array. == Related Problems == Related: Cyclic Permutations == Parameters == <pre>n: number of elements</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor...")
- 10:20, 15 February 2023 Inexact Laplacian Solver (hist | edit) [3,888 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Inexact Laplacian Solver (SDD Systems Solvers)}} == Description == This problem refers to solving equations of the form $Lx = b$ where $L$ is a Laplacian of a graph. In other words, this is solving equations of the form $Ax = b$ for a SDD matrix $A$. This variation of the problem permits some error. == Related Problems == Related: Exact Laplacian Solver == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sort...")
- 10:20, 15 February 2023 Exact Laplacian Solver (hist | edit) [1,294 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Exact Laplacian Solver (SDD Systems Solvers)}} == Description == This problem refers to solving equations of the form $Lx = b$ where $L$ is a Laplacian of a graph. In other words, this is solving equations of the form $Ax = b$ for a SDD matrix $A$. This variation of the problem requires an exact solution with no error. == Related Problems == Related: Inexact Laplacian Solver == Parameters == <pre>n: dimension of matrix</pre> == Table of Algor...")
- 10:20, 15 February 2023 Key Exchange (hist | edit) [1,168 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Key Exchange (Key Exchange)}} == Description == Key exchange (also key establishment) is a method in cryptography by which cryptographic keys are exchanged between two parties, allowing use of a cryptographic algorithm. == Parameters == <pre>n: maximum size of numbers (prime, parameters, keys), in bits</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approxima...")
- 10:20, 15 February 2023 Planar Bipartite Graph Perfect Matching (hist | edit) [1,333 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Planar Bipartite Graph Perfect Matching (Maximum Cardinality Matching)}} == Description == The goal of maximum cardinality matching is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible). Here, the graph is a planar bipartite graph. == Related Problems == Generalizations: Bipartite Graph MCM Related: General Graph MCM == Parameters == <pre>V: number of vertices E: number of...")
- 10:20, 15 February 2023 General Graph MCM (hist | edit) [1,737 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:General Graph MCM (Maximum Cardinality Matching)}} == Description == The goal of maximum cardinality matching is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible). Here, the graph can be any general graph. == Related Problems == Subproblem: Bipartite Graph MCM Related: Planar Bipartite Graph Perfect Matching == Parameters == <pre>V: number of vertices E: number of edges</p...")
- 10:20, 15 February 2023 Bipartite Graph MCM (hist | edit) [2,906 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Bipartite Graph MCM (Maximum Cardinality Matching)}} == Description == The goal of maximum cardinality matching is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible). Here, the graph is bipartite. == Related Problems == Generalizations: General Graph MCM Subproblem: Planar Bipartite Graph Perfect Matching == Parameters == <pre>V: number of vertices E: number of edges</pre>...")
- 10:20, 15 February 2023 Convex Polyhedral Window (hist | edit) [669 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Convex Polyhedral Window (Line Clipping)}} == Description == Line clipping is the process of removing lines or portions of lines outside an area of interest. Typically; any line or part thereof which is outside of the viewing area is removed. Here, the viewing area is a convex polyhedron. == Related Problems == Subproblem: Convex Polygonal Window Related: Rectangular Window == Parameters == <pre>n: number of lines p: number of faces on pol...")
- 10:20, 15 February 2023 Convex Polygonal Window (hist | edit) [1,178 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Convex Polygonal Window (Line Clipping)}} == Description == Line clipping is the process of removing lines or portions of lines outside an area of interest. Typically; any line or part thereof which is outside of the viewing area is removed. Here, the viewing area is a convex polygon. == Related Problems == Generalizations: Convex Polyhedral Window Subproblem: Rectangular Window == Parameters == <pre>n: number of lines p: number of edges o...")
- 10:20, 15 February 2023 Rectangular Window (hist | edit) [1,635 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Rectangular Window (Line Clipping)}} == Description == Line clipping is the process of removing lines or portions of lines outside an area of interest. Typically; any line or part thereof which is outside of the viewing area is removed. Here, the viewing area is rectangular. == Related Problems == Generalizations: Convex Polygonal Window Related: Convex Polyhedral Window == Parameters == <pre>n: number of lines</pre> == Table of Algorithm...")
- 10:20, 15 February 2023 Edit Sequence, constant-size alphabet (hist | edit) [1,287 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Edit Sequence, constant-size alphabet (Sequence Alignment)}} == Description == Given two strings, determine the shortest sequence of edits required to transform one of the strings into the other. Assume we have a constant-size alphabet. == Related Problems == Generalizations: Edit Distance, constant-size alphabet == Parameters == <pre>n, m: lengths of input strings; assume n≥m</pre> == Table of Algorithms == {| class="wikitable sortable"...")
- 10:20, 15 February 2023 Edit Distance, constant-size alphabet (hist | edit) [599 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Edit Distance, constant-size alphabet (Sequence Alignment)}} == Description == Given two strings, determine the minimum number of edits required to transform one of the strings into the other. Assume we have a constant-size alphabet. == Related Problems == Subproblem: Edit Sequence, constant-size alphabet == Parameters == <pre>n, m: lengths of input strings; assume n≥m</pre> == Table of Algorithms == Currently no algorithms in our database...")
- 10:20, 15 February 2023 Multiple String Search (hist | edit) [1,523 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Multiple String Search (String Search)}} == Description == Multiple string search algorithms try to find a place where one or several strings (also called patterns) are found within a larger string or text. == Related Problems == Related: Single String Search == Parameters == <pre>$m$: longest pattern length $n$: length of searchable text $s$: size of the alphabet $k$: number of patterns to search for $z$: number of matches</pre> == Table of A...")
- 10:20, 15 February 2023 Single String Search (hist | edit) [4,574 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Single String Search (String Search)}} == Description == Single string search algorithms try to find a place where a string (also called a pattern) is found within a larger string or text. == Related Problems == Related: Multiple String Search == Parameters == <pre>$m$: pattern length $n$: length of searchable text $s$: size of the alphabet</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%"...")
- 10:20, 15 February 2023 Square Matrix LU Decomposition (hist | edit) [2,138 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Square Matrix LU Decomposition (LU Decomposition)}} == Description == Lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. In this specific case, the input is a square $n \times n$ matrix == Related Problems == Generalizations: Rectangular Matrix LU Decomposition == Parameters == <pre>$n$: dimension of square matrix</pre> == Table of Algorithms == {| cl...")
- 10:20, 15 February 2023 Rectangular Matrix LU Decomposition (hist | edit) [1,067 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Rectangular Matrix LU Decomposition (LU Decomposition)}} == Description == Lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. In the general case, the input is an $m \times n$ matrix. == Related Problems == Subproblem: Square Matrix LU Decomposition == Parameters == <pre>$m$: number of rows in input matrix $n$: number of columns in input matrix $l$: numb...")
- 10:20, 15 February 2023 Smallest Factor (hist | edit) [513 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Smallest Factor (Integer Factoring)}} == Description == Given an $n$-bit integer $N$, find a non-trivial factorization $N=pq$ (where $p, q>1$ are integers) or return that $N$ is prime. For "second category" algorithms, the running time depends solely on the size of the integer to be factored == Related Problems == Related: Integer Factoring == Parameters == <pre>n: number of bits in the integer</pre> == Table of Algorithms == Currently no al...")
- 10:20, 15 February 2023 Integer Factoring (hist | edit) [5,101 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Integer Factoring (Integer Factoring)}} == Description == Given an $n$-bit integer $N$, find a non-trivial factorization $N=pq$ (where $p, q>1$ are integers) or return that $N$ is prime. For "first category" algorithms, the running time depends on the size of smallest prime factor. == Related Problems == Related: Smallest Factor == Parameters == <pre>n: number of bits in the integer B: bound parameter (if needed)</pre> == Table of Algorithms =...")
- 10:20, 15 February 2023 (5/3)-approximate ap-shortest paths (hist | edit) [1,489 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:(5/3)-approximate ap-shortest paths (All-Pairs Shortest Paths (APSP))}} == Description == Approximate APSP within a factor of 5/3. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirected Graphs with Positive Integer Weights, APSP on Sparse Directed Graphs with...")
- 10:20, 15 February 2023 APSP on Sparse Undirected Unweighted Graphs (hist | edit) [1,634 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Sparse Undirected Unweighted Graphs (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is undirected, and is unweighted (or equivalently, has all unit weights). == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighte...")
- 10:20, 15 February 2023 APSP on Sparse Directed Unweighted Graphs (hist | edit) [1,078 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Sparse Directed Unweighted Graphs (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is directed, and is unweighted (or equivalently, has all unit weights). == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Gr...")
- 10:20, 15 February 2023 APSP on Dense Undirected Unweighted Graphs (hist | edit) [1,634 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Undirected Unweighted Graphs (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is undirected, and is unweighted (or equivalently, has all unit weights). == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighte...")
- 10:20, 15 February 2023 APSP on Dense Directed Unweighted Graphs (hist | edit) [1,079 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Directed Unweighted Graphs (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is directed, and is unweighted (or equivalently, has all unit weights). == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Gr...")
- 10:20, 15 February 2023 APSP on Sparse Undirected Graphs with Arbitrary Weights (hist | edit) [1,608 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Sparse Undirected Graphs with Arbitrary Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is undirected, and has arbitrary weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP o...")
- 10:20, 15 February 2023 APSP on Sparse Undirected Graphs with Positive Integer Weights (hist | edit) [1,731 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Sparse Undirected Graphs with Positive Integer Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is undirected, and has positive integer weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Grap...")
- 10:20, 15 February 2023 APSP on Sparse Directed Graphs with Arbitrary Weights (hist | edit) [1,046 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Sparse Directed Graphs with Arbitrary Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is directed, and has arbitrary weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on De...")
- 10:20, 15 February 2023 APSP on Dense Undirected Graphs with Positive Integer Weights (hist | edit) [1,731 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Undirected Graphs with Positive Integer Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is undirected, and has positive integer weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Grap...")
- 10:20, 15 February 2023 APSP on Geometrically Weighted Graphs (hist | edit) [1,608 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Geometrically Weighted Graphs (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider may be dense or sparse, may be directed or undirected, and has weights from a fixed set of $c$ values. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Dense Undirected Graph...")
- 10:20, 15 February 2023 APSP on Dense Undirected Graphs with Arbitrary Weights (hist | edit) [1,917 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Undirected Graphs with Arbitrary Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is undirected, and has arbitrary weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirected Graphs with Positive Integer Weights, [...")
- 10:20, 15 February 2023 APSP on Dense Directed Graphs with Arbitrary Weights (hist | edit) [2,104 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP on Dense Directed Graphs with Arbitrary Weights (All-Pairs Shortest Paths (APSP))}} == Description == In this case, the graph $G=(V,E)$ that we consider is dense ($m = O(n^2)$), is directed, and has arbitrary weights. == Related Problems == Generalizations: APSP Related: APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirected Graphs with Positive Integer Weights, A...")
- 10:19, 15 February 2023 APSP (hist | edit) [4,258 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:APSP (All-Pairs Shortest Paths (APSP))}} == Description == The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. == Related Problems == Subproblem: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirec...")
- 10:19, 15 February 2023 Replacement Paths Problem (hist | edit) [869 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Replacement Paths Problem (Shortest Path (Directed Graphs))}} == Description == Given nodes $s$ and $t$ in a weighted directed graph and a shortest path $P$ from $s$ to $t$, compute the length of the shortest simple path that avoids edge $e$, for all edges $e$ on $P$ == Related Problems == Generalizations: st-Shortest Path Related: General Weights, Nonnegative Weights, Nonnegative Integer Weights, Second Shortest Simple Path, 1-...")
_-_Time.png){kind=link}