User contributions for Admin
Jump to navigation
Jump to search
15 February 2023
- 10:2910:29, 15 February 2023 diff hist +1,755 N Sensitive incremental Created page with "{{DISPLAYTITLE:sensitive incremental #SSR (Vertex Reachability)}} == Description == A data structure with sensitivity $d$ for a problem $P$ has the following properties: It obtains an instance $p$ of $P$ and is allowed polynomial preprocessing time on $p$. After the preprocessing, the data structure must provide the following operations: (Batch) Update: Up to $d$ changes are performed to the initial problem instance $p$, e.g., $d$ edges are added to or removed from $p..."
- 10:2910:29, 15 February 2023 diff hist +56 N OuMv Redirected page to Online Vector-Matrix-Vector Multiplication current Tag: New redirect
- 10:2910:29, 15 February 2023 diff hist +1,297 N Online Vector-Matrix-Vector Multiplication Created page with "{{DISPLAYTITLE:Online Vector-Matrix-Vector Multiplication (Matrix-Vector Multiplication)}} == Description == Let $M$ be a binary $n \times n$ matrix than can be preprocessed. After preprocessing $n$ vector pairs $(u^1, v^1), \ldots, (u^n, v^n)$, arrive one at a time and the task is to compute $(u^i)^T M v^i$ before being presented with the $i+1$th vector pair for every $i$. == Related Problems == Related: Online Matrix-Vector Multiplication == Parameters == <..."
- 10:2910:29, 15 February 2023 diff hist +49 N OMv Redirected page to Online Matrix-Vector Multiplication current Tag: New redirect
- 10:2910:29, 15 February 2023 diff hist +699 N Online Matrix-Vector Multiplication Created page with "{{DISPLAYTITLE:Online Matrix-Vector Multiplication (Matrix-Vector Multiplication)}} == Description == We are given an $n \times n$ matrix $M$ and will receive $n$ column-vectors of size $n$, denoted by $v_1, \ldots , v_n$, one by one. After seeing each vector $v_i$, we have to output the product $Mv_i$ before we can see the next vector. == Related Problems == Related: Online Vector-Matrix-Vector Multiplication == Parameters == <pre>n: dimension of square matr..."
- 10:2910:29, 15 February 2023 diff hist +30 N Minimum Weight k-Cycle Redirected page to Shortest k-Cycle current Tag: New redirect
- 10:2910:29, 15 February 2023 diff hist +1,045 N Shortest k-Cycle Created page with "{{DISPLAYTITLE:Shortest k-Cycle (Graph Cycles)}} == Description == Given a graph $G=(V,E)$ with non-negative weights, find a minimum weight cycle of length $k$. == Related Problems == Generalizations: Shortest Cycle == Parameters == <pre>n: number of vertices m: number of edges k: length of cycle</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sortable" sty..."
- 10:2910:29, 15 February 2023 diff hist +28 N Minimum Weight Cycle Redirected page to Shortest Cycle current Tag: New redirect
- 10:2910:29, 15 February 2023 diff hist +907 N Shortest Cycle Created page with "{{DISPLAYTITLE:Shortest Cycle (Graph Cycles)}} == Description == Given a graph $G=(V,E)$ with non-negative weights, find a minimum weight cycle. == Related Problems == Subproblem: Shortest k-Cycle == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sortable" style="text-align:center;" width="100%"..."
- 10:2910:29, 15 February 2023 diff hist +1,241 N Price Query Created page with "{{DISPLAYTITLE:Price Query (Price Query)}} == Description == For a graph with edge weight function $c : E \rightarrow Z$, a price query is an assignment of node weights $p : V \rightarrow Z$. Such a query has a yes answer if and only if there is a $(u,v) \in E$ such that $p(u) + p(v) > c(u,v)$. (Intuitively, the $p(v)$ are “prices” on the nodes, the $c(u,v)$ are costs of producing $u$ and $v$, and a price query asks if there is an edge we are willing to “sell”..."
- 10:2910:29, 15 February 2023 diff hist +1,364 N Independent Set Queries Created page with "{{DISPLAYTITLE:Independent Set Queries (Independent Set Queries)}} == Description == For a graph $G=(V,E)$ and a given subset of vertices $S\subseteq G$, answer the query of the form "is $S$ an independent set?" == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sortable" style="text-align:center;" width=..."
- 10:2910:29, 15 February 2023 diff hist +39 N APMW Redirected page to All Pairs Minimum Witness current Tag: New redirect
- 10:2910:29, 15 February 2023 diff hist +968 N All Pairs Minimum Witness Created page with "{{DISPLAYTITLE:All Pairs Minimum Witness (Minimum Witness)}} == Description == Fix an instance of negative triangle with node sets $I, J, K$ and weight function $w$. Let $i \in I, j \in J, k \in K$. Recall that the triple $(i, j, k)$ is a negative triangle iff $(w(i, k) \odot w(k, j)) + w(i, j) < 0$. Fix a total ordering $<$ on the nodes in $K$ in the negative triangle instance. For any $i \in I, j \in J$, a node $k \in K$ is called a minimum witness for $(i, j)$ if $(..."
- 10:2910:29, 15 February 2023 diff hist +1,435 N Minimum Witness Finding Created page with "{{DISPLAYTITLE:Minimum Witness Finding (Minimum Witness)}} == Description == Fix an instance of negative triangle with node sets $I, J, K$ and weight function $w$. Let $i \in I, j \in J, k \in K$. Recall that the triple $(i, j, k)$ is a negative triangle iff $(w(i, k) \odot w(k, j)) + w(i, j) < 0$. Fix a total ordering $<$ on the nodes in $K$ in the negative triangle instance. For any $i \in I, j \in J$, a node $k \in K$ is called a minimum witness for $(i, j)$ if $(i,..."
- 10:2910:29, 15 February 2023 diff hist +1,038 N Multiple Local Alignment Created page with "{{DISPLAYTITLE:Multiple Local Alignment (Local Alignment)}} == Description == Given $k$ input strings and a scoring function on pairs of letters, one is asked to find the substrings of the $k$ input strings that are most similar under the scoring function. == Related Problems == Generalizations: Local Alignment == Parameters == <pre>k: number of input strings n: length of input strings?</pre> == Table of Algorithms == Currently no algorithms in our databas..."
- 10:2910:29, 15 February 2023 diff hist +1,358 N Local Alignment Created page with "{{DISPLAYTITLE:Local Alignment (Local Alignment)}} == Description == Given two input strings and a scoring function on pairs of letters, one is asked to find the substrings of the two input strings that are most similar under the scoring function. == Related Problems == Subproblem: Multiple Local Alignment == Parameters == <pre>n: length of input strings?</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Red..."
- 10:2910:29, 15 February 2023 diff hist +28 N GeomBase Redirected page to Geometric Base current Tag: New redirect
- 10:2910:29, 15 February 2023 diff hist +3,043 N Geometric Base Created page with "{{DISPLAYTITLE:Geometric Base (Geometric Base)}} == Description == Given a set of $n$ points with integer coordinates on three horizontal lines $y = 0, y = 1$, and $y = 2$, determine whether there exists a non-horizontal line containing three of the points == Parameters == <pre>n: number of points</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions TO Problem == {| class="wikitable sortable" style="text..."
- 10:2910:29, 15 February 2023 diff hist +1,088 N 3D Motion Planning Created page with "{{DISPLAYTITLE:3D Motion Planning (Motion Planning Problems)}} == Description == Given a set of horizontal (that is, parallel to the xy-plane) non-intersecting, non-touching triangle obstacles in 3-space, and a vertical line segment as a robot, determine whether the robot can be moved, using translations only, from a source to a goal position without colliding with the obstacles. == Related Problems == Related: Planar Motion Planning == Parameters == <pre>n:..."
- 10:2910:29, 15 February 2023 diff hist +1,167 N Planar Motion Planning Created page with "{{DISPLAYTITLE:Planar Motion Planning (Motion Planning Problems)}} == Description == Given a set of non-intersecting, non-touching, axis-parallel line segment obstacles in the plane and a line segment robot (a rod or ladder), determine whether the rod can be moved (allowing both translation and rotation) from a given source to a given goal configuration without colliding with the obstacles. == Related Problems == Related: 3D Motion Planning == Parameters == <..."
- 10:2910:29, 15 February 2023 diff hist +1,466 N Visible Triangle Created page with "{{DISPLAYTITLE:Visible Triangle (Geometric Visibility Problems)}} == Description == Given a set $S$ of opaque horizontal triangles, another horizontal triangle $t$ and a viewpoint $p$, is there a point on $t$ that can be seen from $p$? == Related Problems == Related: Visibility Between Segments, Visibility From Infinity == Parameters == <pre>n: number of opaque horizontal triangles</pre> == Table of Algorithms == Currently no algorithms in our database..."
- 10:2910:29, 15 February 2023 diff hist +1,097 N Visibility From Infinity Created page with "{{DISPLAYTITLE:Visibility From Infinity (Geometric Visibility Problems)}} == Description == Given a set $S$ of axis-parallel line segments in the plane and one particular horizontal segments $s$, determine whether there is a point on $s$ that can be seen from infinity, that is, whether there exists an infinite ray starting at the point on $s$ that does not intersect any segment. == Related Problems == Related: Visibility Between Segments, Visible Triangle =..."
- 10:2910:29, 15 February 2023 diff hist +1,097 N Visibility Between Segments Created page with "{{DISPLAYTITLE:Visibility Between Segments (Geometric Visibility Problems)}} == Description == Given a set $S$ of $n$ horizontal line segments in the plane and two particular horizontal segments $s_1$ and $s_2$, determine whether there are points on $s_1$ and $s_2$ that can see each other, that is, such that the open segment between the points does not intersect any segment in $S$. == Related Problems == Related: Visibility From Infinity, Visible Triangle =..."
- 10:2910:29, 15 February 2023 diff hist +1,245 N Weighted Depth Created page with "{{DISPLAYTITLE:Weighted Depth (Geometric Covering Problems)}} == Description == Given a set of $n$ weighted axis-parallel boxes in $d$-dimensional space $\mathbb{R}^d$, find a point $p \in \mathbb{R}^d$ that maximizes the sum of the weights of the boxes containing $p$. == Related Problems == Related: Strips Cover Box, Triangles Cover Triangle, Hole in Union, Triangle Measure, Point Covering, Max-Weight Rectangle == Parameters == <pre>n: nu..."
- 10:2910:29, 15 February 2023 diff hist +1,222 N Max-Weight Rectangle Created page with "{{DISPLAYTITLE:Max-Weight Rectangle (Geometric Covering Problems)}} == Description == Given $n$ weighted points (positive or negative) in $d \geq 2$ dimensions, what is the axis-aligned box which maximizes the total weight of the points it contains? == Related Problems == Related: Strips Cover Box, Triangles Cover Triangle, Hole in Union, Triangle Measure, Point Covering, Weighted Depth == Parameters == <pre>n: number of points d: dimensio..."
- 10:2910:29, 15 February 2023 diff hist +1,006 N Point Covering Created page with "{{DISPLAYTITLE:Point Covering (Geometric Covering Problems)}} == Description == Given a set of $n$ halfplanes and a number $k$, determine whether there is a point $p$ that is covered by at least $k$ of the halfplanes. == Related Problems == Related: Strips Cover Box, Triangles Cover Triangle, Hole in Union, Triangle Measure, Max-Weight Rectangle, Weighted Depth == Parameters == <pre>n: number of halfplanes</pre> == Table of Algorithms ==..."
- 10:2910:29, 15 February 2023 diff hist +960 N Triangle Measure Created page with "{{DISPLAYTITLE:Triangle Measure (Geometric Covering Problems)}} == Description == Given a set of triangles in the plane, compute the measure of their union. == Related Problems == Related: Strips Cover Box, Triangles Cover Triangle, Hole in Union, Point Covering, Max-Weight Rectangle, Weighted Depth == Parameters == <pre>n: number of triangles</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem...."
- 10:2910:29, 15 February 2023 diff hist +1,434 N Hole in Union Created page with "{{DISPLAYTITLE:Hole in Union (Geometric Covering Problems)}} == Description == Given a set of triangles in the plane, does their union contain a hole? == Related Problems == Related: Strips Cover Box, Triangles Cover Triangle, Triangle Measure, Point Covering, Max-Weight Rectangle, Weighted Depth == Parameters == <pre>n: number of triangles</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. =..."
- 10:2910:29, 15 February 2023 diff hist +2,962 N Triangles Cover Triangle Created page with "{{DISPLAYTITLE:Triangles Cover Triangle (Geometric Covering Problems)}} == Description == Given a set of triangles in the plane, does their union contain another given triangle? == Related Problems == Related: Strips Cover Box, Hole in Union, Triangle Measure, Point Covering, Max-Weight Rectangle, Weighted Depth == Parameters == <pre>n: number of triangles</pre> == Table of Algorithms == Currently no algorithms in our database for the g..."
- 10:2910:29, 15 February 2023 diff hist +1,721 N Strips Cover Box Created page with "{{DISPLAYTITLE:Strips Cover Box (Geometric Covering Problems)}} == Description == Given a set of strips in the plane, does their union contain a given axis-parallel rectangle? == Related Problems == Related: Triangles Cover Triangle, Hole in Union, Triangle Measure, Point Covering, Max-Weight Rectangle, Weighted Depth == Parameters == <pre>n: number of strips</pre> == Table of Algorithms == Currently no algorithms in our database for th..."
- 10:2910:29, 15 February 2023 diff hist +840 N Separator2 Created page with "{{DISPLAYTITLE:Separator2 (Geometric Separator Problems)}} == Description == Given a set $S$ of $n$ closed, non-intersecting (nor touching), axis-parallel line segments, is there a separator? == Related Problems == Related: Separator1 == Parameters == <pre>n: number of line segments</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sortable" style="text-align..."
- 10:2910:29, 15 February 2023 diff hist +1,077 N Separator1 Created page with "{{DISPLAYTITLE:Separator1 (Geometric Separator Problems)}} == Description == Given a set $S$ of $n$ possible half-infinite, closed horizontal line segments, is there a non-horizontal separator? Separator definition: Given a set $S$ of $n$ objects in the plane, we call a line $l$ a separator of $S$ if $l$ does not intersect any object in $S$ and both halfplanes bounded by $l$ contain a non-empty subset of the objects in $S$. == Related Problems == Related: Separat..."
- 10:2810:28, 15 February 2023 diff hist +1,307 N Point on 3 Lines Created page with "{{DISPLAYTITLE:Point on 3 Lines (Geometric Incidence Problems)}} == Description == Given a set of lines in the plane, is there a point that lies on at least three of them? == Related Problems == Related: 3 Points on Line == Parameters == <pre>n: number of lines</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions TO Problem == {| class="wikitable sortable" style="text-align:center;" width="100%"..."
- 10:2810:28, 15 February 2023 diff hist +1,589 N 3 Points on Line Created page with "{{DISPLAYTITLE:3 Points on Line (Geometric Incidence Problems)}} == Description == Given a set of points in the plane, is there a line that contains at least three of the points? == Related Problems == Related: Point on 3 Lines == Parameters == <pre>n: number of points</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions TO Problem == {| class="wikitable sortable" style="text-align:center;" width=..."
- 10:2810:28, 15 February 2023 diff hist +1,591 N Partial Match Created page with "{{DISPLAYTITLE:Partial Match (Partial Match)}} == Description == In the Partial Match problem, we are given a "database" of $n$ binary strings, and a list of $n$ "queries" which are strings in $\{0,1,?\}^*$. (Here, "?" represents a wildcard.) We say that a query $q=q_1,...,q_d$ matches a string $x=x_1,...,x_d$ if for all $i=1,...,d$, if $q_i$ in $\{0,1\}$ then $q_i = x_i$. Output: Determine for all $n$ queries, which of them match some string in the database. == Param..."
- 10:2810:28, 15 February 2023 diff hist +34 N DTW Redirected page to Dynamic Time Warping current Tag: New redirect
- 10:2810:28, 15 February 2023 diff hist +1,197 N Dynamic Time Warping Created page with "{{DISPLAYTITLE:Dynamic Time Warping (Dynamic Time Warping)}} == Description == Fix a metric space $(M, d)$. A sequence of points in $M$ is called a curve. Consider two curves $x, y$ of length $n, m (n \geq m)$. We may traverse $x$ and $y$ by starting in their first entries, in any time step advancing to the next entry in $x$ or $y$ or both, and ending in their last entries. The cost of such a traversal is the sum over all points in time of the distance between the curr..."
- 10:2810:28, 15 February 2023 diff hist +987 N Frechet Distance Created page with "{{DISPLAYTITLE:Frechet Distance (Frechet Distance)}} == Description == Intuitively, the (continuous) Fréchet distance of two curves $P, Q$ is the minimal length of a leash required to connect a dog to its owner, as they walk along $P$ or $Q$, respectively, without backtracking. == Parameters == <pre>n: length of first curve m: length of second curve</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FRO..."
- 10:2810:28, 15 February 2023 diff hist +1,543 N Metricity Created page with "{{DISPLAYTITLE:Metricity (Metricity)}} == Description == Given an $n\times n$ nonnegative matrix $A$, determine whether $A$ defines a metric on $(n)$, that is, that A is symmetric, has 0s on the diagonal, and its entries satisfy the triangle inequality. == Parameters == <pre>n: dimensionality of matrix</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions TO Problem == {| class="wikitable sortable" style=..."
- 10:2810:28, 15 February 2023 diff hist +34 N TC* Redirected page to Triangle Collection* current Tag: New redirect
- 10:2810:28, 15 February 2023 diff hist +2,250 N Triangle Collection* Created page with "{{DISPLAYTITLE:Triangle Collection* (Graph Triangle Problems)}} == Description == See Definition 3 of reference. == Related Problems == Generalizations: Triangle Detection Related: Negative Triangle Detection, Negative Triangle Search, Negative Triangle Listing, Nondecreasing Triangle, Minimum Triangle, Triangle in Unweighted Graph == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms == Curren..."
- 10:2810:28, 15 February 2023 diff hist +4,402 N Triangle Detection Created page with "{{DISPLAYTITLE:Triangle Detection (Graph Triangle Problems)}} == Description == Determine whether or not there is a triangle in a given graph == Related Problems == Subproblem: Negative Triangle Detection, Nondecreasing Triangle, Minimum Triangle, Triangle in Unweighted Graph, Triangle Collection* Related: Negative Triangle Search, Negative Triangle Listing, Nondecreasing Triangle, Minimum Triangle, Triangle in Unweighted G..."
- 10:2810:28, 15 February 2023 diff hist +1,321 N Triangle in Unweighted Graph Created page with "{{DISPLAYTITLE:Triangle in Unweighted Graph (Graph Triangle Problems)}} == Description == Find a triangle in an unweighted graph == Related Problems == Generalizations: Triangle Detection Related: Negative Triangle Detection, Negative Triangle Search, Negative Triangle Listing, Nondecreasing Triangle, Minimum Triangle, Triangle Collection* == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms ==..."
- 10:2810:28, 15 February 2023 diff hist +1,101 N Minimum Triangle Created page with "{{DISPLAYTITLE:Minimum Triangle (Graph Triangle Problems)}} == Description == Find the triangle in a graph with minimum weight == Related Problems == Generalizations: Triangle Detection Related: Negative Triangle Detection, Negative Triangle Search, Negative Triangle Listing, Nondecreasing Triangle, Triangle in Unweighted Graph, Triangle Collection* == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algo..."
- 10:2810:28, 15 February 2023 diff hist +1,142 N Nondecreasing Triangle Created page with "{{DISPLAYTITLE:Nondecreasing Triangle (Graph Triangle Problems)}} == Description == Given a tripartite graph with partitions $I, J, K$ and real edge weights, find a triangle $i \in I, j \in J, k \in K$ such that $w(i, k) \leq w(k, j) \leq w(i, j)$. == Related Problems == Generalizations: Triangle Detection Related: Negative Triangle Detection, Negative Triangle Search, Negative Triangle Listing, Minimum Triangle, Triangle in Unweighted Graph..."
- 10:2810:28, 15 February 2023 diff hist +1,352 N Negative Triangle Listing Created page with "{{DISPLAYTITLE:Negative Triangle Listing (Graph Triangle Problems)}} == Description == Given an $n$ node graph $G = (V, E)$ with edge weights $w: E \rightarrow W$, list the negative triangles, i.e. three vertices that form a triangle with total edge weights summing to a negative number. == Related Problems == Generalizations: Negative Triangle Search Related: Negative Triangle Detection, Nondecreasing Triangle, Minimum Triangle, Triangle in Unweig..."
- 10:2810:28, 15 February 2023 diff hist +1,175 N Negative Triangle Search Created page with "{{DISPLAYTITLE:Negative Triangle Search (Graph Triangle Problems)}} == Description == Given an $n$ node graph $G = (V, E)$ with edge weights $w: E \rightarrow W$, find a negative triangle, i.e. three vertices that form a triangle with total edge weights summing to a negative number. == Related Problems == Generalizations: Negative Triangle Detection Subproblem: Negative Triangle Listing Related: Nondecreasing Triangle, Minimum Triangle, Triangle..."
- 10:2810:28, 15 February 2023 diff hist +8,131 N Negative Triangle Detection Created page with "{{DISPLAYTITLE:Negative Triangle Detection (Graph Triangle Problems)}} == Description == Given an $n$ node graph $G = (V, E)$ with edge weights $w: E \rightarrow W$, determine whether there is a negative triangle, i.e. three vertices that form a triangle with total edge weights summing to a negative number. == Related Problems == Generalizations: Triangle Detection Subproblem: Negative Triangle Search Related: Negative Triangle Listing, Nondecreasing..."
- 10:2810:28, 15 February 2023 diff hist +1,702 N Approximate Reach Centrality Created page with "{{DISPLAYTITLE:Approximate Reach Centrality (Vertex Centrality)}} == Description == The reach centrality of a node $w$ is the smallest distance $r$ such that any $s-t$ shortest path passing through $w$ has either $s$ or $t$ in the ball of radius $r$ around $w$. Approximate reach centrality is the approximation version of the problem. == Related Problems == Generalizations: Reach Centrality Related: Eccentricity, All-Nodes Median Parity, Betweenness C..."
- 10:2810:28, 15 February 2023 diff hist +1,478 N Undirected All-Nodes Reach Centrality Created page with "{{DISPLAYTITLE:Undirected All-Nodes Reach Centrality (Vertex Centrality)}} == Description == The reach centrality of a node $w$ is the smallest distance $r$ such that any $s-t$ shortest path passing through $w$ has either $s$ or $t$ in the ball of radius $r$ around $w$. Undirected All-Nodes Reach Centrality is the version of the problem in an undirected graph where you must calculate the reach centrality of each node. == Related Problems == Generalizations: Reach..."