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:29, 15 February 2023 Admin talk contribs created page GeomBase (Redirected page to Geometric Base) Tag: New redirect
• 10:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:29, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page DTW (Redirected page to Dynamic Time Warping) Tag: New redirect
• 10:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page TC* (Redirected page to Triangle Collection*) Tag: New redirect
• 10:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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:28, 15 February 2023 Admin talk contribs created page 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...")
• 10:28, 15 February 2023 Admin talk contribs created page Directed All-Nodes Reach Centrality (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 Admin talk contribs created page Reach Centrality (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 Admin talk contribs created page Undirected All-Nodes Positive Betweenness Centrality (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 Admin talk contribs created page Directed All-Nodes Positive Betweenness Centrality (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 Admin talk contribs created page Positive Betweenness Centrality (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 Admin talk contribs created page Approximate Betweenness Centrality (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 Admin talk contribs created page BC (Redirected page to Betweenness Centrality) Tag: New redirect
• 10:28, 15 February 2023 Admin talk contribs created page Betweenness Centrality (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 Admin talk contribs created page All-Nodes Median Parity (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 Admin talk contribs created page Eccentricity (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 Admin talk contribs created page 1-sensitive (4/3)-approximate decremental eccentricity (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 Admin talk contribs created page Constant sensitivity (4/3)-approximate incremental diameter (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 Admin talk contribs created page 1-sensitive decremental diameter (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 Admin talk contribs created page 1-sensitive (4/3)-approximate decremental diameter (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 Admin talk contribs created page Decremental Diameter (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 Admin talk contribs created page Approximate Diameter (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...")

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