New pages

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

• 10:29, 15 February 2023 ‎Price Query (hist | edit) ‎[1,235 bytes] ‎Admin (talk | contribs) (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:29, 15 February 2023 ‎Independent Set Queries (hist | edit) ‎[1,358 bytes] ‎Admin (talk | contribs) (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:29, 15 February 2023 ‎All Pairs Minimum Witness (hist | edit) ‎[962 bytes] ‎Admin (talk | contribs) (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:29, 15 February 2023 ‎Minimum Witness Finding (hist | edit) ‎[1,429 bytes] ‎Admin (talk | contribs) (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:29, 15 February 2023 ‎Multiple Local Alignment (hist | edit) ‎[1,031 bytes] ‎Admin (talk | contribs) (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:29, 15 February 2023 ‎Local Alignment (hist | edit) ‎[1,348 bytes] ‎Admin (talk | contribs) (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:29, 15 February 2023 ‎Geometric Base (hist | edit) ‎[3,034 bytes] ‎Admin (talk | contribs) (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 ‎3D Motion Planning (hist | edit) ‎[1,079 bytes] ‎Admin (talk | contribs) (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 ‎Planar Motion Planning (hist | edit) ‎[1,158 bytes] ‎Admin (talk | contribs) (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 ‎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...")

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