New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:29, 15 February 2023 Visible Triangle (hist | edit) [1,457 bytes] Admin (talk | contribs) (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:29, 15 February 2023 Visibility From Infinity (hist | edit) [1,088 bytes] Admin (talk | contribs) (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:29, 15 February 2023 Visibility Between Segments (hist | edit) [1,088 bytes] Admin (talk | contribs) (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:29, 15 February 2023 Weighted Depth (hist | edit) [1,239 bytes] Admin (talk | contribs) (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:29, 15 February 2023 Max-Weight Rectangle (hist | edit) [1,216 bytes] Admin (talk | contribs) (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:29, 15 February 2023 Point Covering (hist | edit) [997 bytes] Admin (talk | contribs) (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:29, 15 February 2023 Triangle Measure (hist | edit) [951 bytes] Admin (talk | contribs) (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:29, 15 February 2023 Hole in Union (hist | edit) [1,425 bytes] Admin (talk | contribs) (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:29, 15 February 2023 Triangles Cover Triangle (hist | edit) [2,953 bytes] Admin (talk | contribs) (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:29, 15 February 2023 Strips Cover Box (hist | edit) [1,712 bytes] Admin (talk | contribs) (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:29, 15 February 2023 Separator2 (hist | edit) [831 bytes] Admin (talk | contribs) (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:29, 15 February 2023 Separator1 (hist | edit) [1,068 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Point on 3 Lines (hist | edit) [1,298 bytes] Admin (talk | contribs) (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:28, 15 February 2023 3 Points on Line (hist | edit) [1,580 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Partial Match (hist | edit) [1,585 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Dynamic Time Warping (hist | edit) [1,191 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Frechet Distance (hist | edit) [981 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Metricity (hist | edit) [1,534 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Triangle Collection* (hist | edit) [2,241 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Triangle Detection (hist | edit) [4,387 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Triangle in Unweighted Graph (hist | edit) [1,312 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Minimum Triangle (hist | edit) [1,092 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Nondecreasing Triangle (hist | edit) [1,133 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Negative Triangle Listing (hist | edit) [1,343 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Negative Triangle Search (hist | edit) [1,166 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Negative Triangle Detection (hist | edit) [8,122 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Approximate Reach Centrality (hist | edit) [1,693 bytes] Admin (talk | contribs) (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:28, 15 February 2023 Undirected All-Nodes Reach Centrality (hist | edit) [1,469 bytes] Admin (talk | contribs) (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...")
- 10:28, 15 February 2023 Directed All-Nodes Reach Centrality (hist | edit) [1,458 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Directed 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$. Directed All-Nodes Reach Centrality is the version of the problem in a directed graph where you must calculate the reach centrality of each node. == Related Problems == Generalizations: Reach Centra...")
- 10:28, 15 February 2023 Reach Centrality (hist | edit) [2,611 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE: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$. == Related Problems == Subproblem: Directed All-Nodes Reach Centrality, Undirected All-Nodes Reach Centrality, Approximate Reach Centrality Related: Eccentricity, All-Nodes Median Parity, Between...")
- 10:28, 15 February 2023 Undirected All-Nodes Positive Betweenness Centrality (hist | edit) [1,252 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Undirected All-Nodes Positive Betweenness Centrality (Vertex Centrality)}} == Description == Given an undirected graph, determine whether the betweenness centrality of all nodes is positive. == Related Problems == Generalizations: Positive Betweenness Centrality Related: Eccentricity, All-Nodes Median Parity, Betweenness Centrality, Approximate Betweenness Centrality, Directed All-Nodes Positive Betweenness Centrality, Reach...")
- 10:28, 15 February 2023 Directed All-Nodes Positive Betweenness Centrality (hist | edit) [1,243 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Directed All-Nodes Positive Betweenness Centrality (Vertex Centrality)}} == Description == Given a directed graph, determine whether the betweenness centrality of all nodes is positive. == Related Problems == Generalizations: Positive Betweenness Centrality Related: Eccentricity, All-Nodes Median Parity, Betweenness Centrality, Approximate Betweenness Centrality, Undirected All-Nodes Positive Betweenness Centrality, Reach Ce...")
- 10:28, 15 February 2023 Positive Betweenness Centrality (hist | edit) [2,749 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Positive Betweenness Centrality (Vertex Centrality)}} == Description == Given a graph $G=(V,E)$ and a vertex $v \in V$, determine whether the betweenness centrality of $v$ is positive. == Related Problems == Generalizations: Betweenness Centrality Subproblem: Directed All-Nodes Positive Betweenness Centrality, Undirected All-Nodes Positive Betweenness Centrality Related: Eccentricity, All-Nodes Median Parity, Approximate Betwe...")
- 10:28, 15 February 2023 Approximate Betweenness Centrality (hist | edit) [1,845 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Approximate Betweenness Centrality (Vertex Centrality)}} == Description == Given a graph $G = (V, E)$ and a vertex $v \in V$, approximate the betweenness centrality of vertex $v$ == Related Problems == Generalizations: Betweenness Centrality Related: Eccentricity, All-Nodes Median Parity, Positive Betweenness Centrality, Directed All-Nodes Positive Betweenness Centrality, Undirected All-Nodes Positive Betweenness Centrality, [...")
- 10:28, 15 February 2023 Betweenness Centrality (hist | edit) [1,101 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Betweenness Centrality (Vertex Centrality)}} == Description == Given a graph $G = (V, E)$ and a vertex $v \in V$, calculate the betweenness centrality of vertex $v$ (or the proportion of shortest paths that go through $v$), i.e. $BC(v) := \sum\limits_{s\neq t \neq v \in V} \frac{\sigma_{st}(v)}{\sigma_{st}}$ where $\sigma_{st}(v)$ is the number of shortest paths from $s$ to $t$ that go through $v$ and $\sigma_{st}$ is the number of shortest paths from $s...")
- 10:28, 15 February 2023 All-Nodes Median Parity (hist | edit) [1,876 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:All-Nodes Median Parity (Vertex Centrality)}} == Description == Given a graph $G = (V, E)$, compute $Med(v) (\mod 2)$ for all $v\in V$, where $Med(v) := \sum\limits_{w\in V} d(v, w)$ == Related Problems == Related: Eccentricity, Betweenness Centrality, Approximate Betweenness Centrality, Positive Betweenness Centrality, Directed All-Nodes Positive Betweenness Centrality, Undirected All-Nodes Positive Betweenness Centrality, R...")
- 10:28, 15 February 2023 Eccentricity (hist | edit) [871 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Eccentricity (Vertex Centrality)}} == Description == Given a graph $G = (V, E)$ and a vertex $v \in V$, calculate the eccentricity $\epsilon(v) := \max \limits_{u\in V} d(u, v)$ == Related Problems == Subproblem: Radius, Diameter, 1-sensitive (4/3)-approximate decremental eccentricity Related: All-Nodes Median Parity, Betweenness Centrality, Approximate Betweenness Centrality, Positive Betweenness Centrality, Directed...")
- 10:28, 15 February 2023 1-sensitive (4/3)-approximate decremental eccentricity (hist | edit) [1,297 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:1-sensitive (4/3)-approximate decremental eccentricity (Graph Metrics)}} == Description == Approximate the eccentricity of a graph decrementally within a factor of 4/3, with a sensativity of 1, i.e. when a single edge is removed. == Related Problems == Generalizations: Eccentricity Related: Median, Radius, Diameter, Diameter 2 vs 3, Diameter 3 vs 7, Approximate Diameter, Decremental Diameter, 1-sensitive (4/3)-approx...")
- 10:28, 15 February 2023 Constant sensitivity (4/3)-approximate incremental diameter (hist | edit) [1,407 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:constant sensitivity (4/3)-approximate incremental diameter (Graph Metrics)}} == Description == Approximate the diameter of a graph decrementally within a factor of 4/3, with a constant sensitivity of $K(\epsilon, t)$, i.e. when a $K(\epsilon, t)$ edges are removed. == Related Problems == Generalizations: Decremental Diameter Related: Median, Radius, Diameter, Diameter 2 vs 3, Diameter 3 vs 7, Approximate Diameter, 1-sen...")
- 10:28, 15 February 2023 1-sensitive decremental diameter (hist | edit) [1,300 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:1-sensitive decremental diameter (Graph Metrics)}} == Description == Determine the diameter of a graph decrementally, with a sensativity of 1, i.e. when a single edge is removed. == Related Problems == Generalizations: Decremental Diameter Subproblem: 1-sensitive (4/3)-approximate decremental diameter Related: Median, Radius, Diameter, Diameter 2 vs 3, Diameter 3 vs 7, Approximate Diameter, constant sensitivity (4/3...")
- 10:28, 15 February 2023 1-sensitive (4/3)-approximate decremental diameter (hist | edit) [1,303 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:1-sensitive (4/3)-approximate decremental diameter (Graph Metrics)}} == Description == Approximate the diameter of a graph decrementally within a factor of 4/3, with a sensativity of 1, i.e. when a single edge is removed. == Related Problems == Generalizations: 1-sensitive decremental diameter Related: Median, Radius, Diameter, Diameter 2 vs 3, Diameter 3 vs 7, Approximate Diameter, Decremental Diameter, constant sen...")
- 10:28, 15 February 2023 Decremental Diameter (hist | edit) [788 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Decremental Diameter (Graph Metrics)}} == Description == Determine the diameter of a graph decrementally, i.e. by removing edges and querying the resulting graph. == Related Problems == Generalizations: Diameter Subproblem: 1-sensitive decremental diameter, constant sensitivity (4/3)-approximate incremental diameter Related: Median, Radius, Diameter 2 vs 3, Diameter 3 vs 7, Approximate Diameter, 1-sensitive (4/3)-a...")
- 10:28, 15 February 2023 Approximate Diameter (hist | edit) [1,219 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Approximate Diameter (Graph Metrics)}} == Description == Given a graph $G = (V, E)$, approximate the diameter within a given factor. == Related Problems == Generalizations: Diameter Subproblem: Diameter 2 vs 3, Diameter 3 vs 7 Related: Median, Radius, Diameter 3 vs 7, Decremental Diameter, 1-sensitive (4/3)-approximate decremental diameter, 1-sensitive decremental diameter, constant sensitivity (4/3)-approximat...")
- 10:28, 15 February 2023 Diameter 3 vs 7 (hist | edit) [1,212 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Diameter 3 vs 7 (Graph Metrics)}} == Description == Given a graph $G = (V, E)$, distinguish between diameter 3 and diameter 7. In other words, approximate diameter within a factor of $9/4-\epsilon$. == Related Problems == Generalizations: Approximate Diameter Related: Median, Radius, Diameter, Diameter 2 vs 3, Decremental Diameter, 1-sensitive (4/3)-approximate decremental diameter, 1-sensitive decremental diameter, ...")
- 10:28, 15 February 2023 Diameter 2 vs 3 (hist | edit) [1,264 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Diameter 2 vs 3 (Graph Metrics)}} == Description == Given a graph $G = (V, E)$, distinguish between diameter 2 and diameter 3. In other words, approximate diameter within a factor of $4/3-\epsilon$. == Related Problems == Generalizations: Approximate Diameter Related: Median, Radius, Diameter, Diameter 3 vs 7, Decremental Diameter, 1-sensitive (4/3)-approximate decremental diameter, 1-sensitive decremental diameter, ...")
- 10:28, 15 February 2023 Diameter (hist | edit) [3,741 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Diameter (Graph Metrics)}} == Description == Given a graph $G = (V, E)$, determine the diameter $d$ of the graph, i.e. the maximum eccentricity over all of the vertices of the graph == Related Problems == Generalizations: Eccentricity Subproblem: Approximate Diameter, Decremental Diameter Related: Median, Radius, Diameter 2 vs 3, Diameter 3 vs 7, Decremental Diameter, 1-sensitive (4/3)-approximate decremental diame...")
- 10:28, 15 February 2023 Radius (hist | edit) [1,280 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Radius (Graph Metrics)}} == Description == Given a graph $G = (V, E)$, determine the radius $r$ of the graph, i.e. the minimum eccentricity over all of the vertices of the graph == Related Problems == Generalizations: Eccentricity Related: Median, Diameter, Diameter 2 vs 3, Diameter 3 vs 7, Approximate Diameter, Decremental Diameter, 1-sensitive (4/3)-approximate decremental diameter, 1-sensitive decremental diameter...")
- 10:27, 15 February 2023 Median (hist | edit) [1,236 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Median (Graph Metrics)}} == Description == Given a graph $G = (V, E)$, determine the median $m$ of the graph, where $m := \min\limits_{v\in V} \sum\limits_{u\in V} d(u, v)$ == Related Problems == Related: Radius, Diameter, Diameter 2 vs 3, Diameter 3 vs 7, Approximate Diameter, Decremental Diameter, 1-sensitive (4/3)-approximate decremental diameter, 1-sensitive decremental diameter, constant sensitivity (4/3)-approxi...")
- 10:27, 15 February 2023 Unbalanced OV (hist | edit) [1,257 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Unbalanced OV (Orthogonal Vectors)}} == Description == Let $0 < \alpha \leq 1$. UOV is the OV problem with the specifications that $A$ is of size $n$ and $B$ is of size $m=\Theta(n^\alpha)$ and $d\leq n^{o(1)}$. == Related Problems == Generalizations: OV Related: k-OV, 3-OV == Parameters == <pre>$n$: size of $A$ $m$: size of $B$ $d$: dimensionality of vectors</pre> == Table of Algorithms == Currently no algorithms in our database fo...")
- 10:27, 15 February 2023 3-OV (hist | edit) [1,200 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3-OV (Orthogonal Vectors)}} == Description == Given 3 sets of $d$-dimensional vectors $A_1, A_2, A_3$, each of size $n$, does there exist $a_1 \in A_1, a_2 \in A_2, a_3 \in A_3$ such that $a_1 * a_2 * a_3 = 0$? == Related Problems == Generalizations: k-OV Related: OV, Unbalanced OV == Parameters == <pre>$n$: number of vectors per set $d$: dimension of each vector; $d = omega(log(n))$</pre> == Table of Algorithms == Currently no algo...")