User contributions for Admin

10:3110:31, 15 February 2023 diff hist +458‎ N Melhorn's Approximation algorithm (Approximate OBST Optimal Binary Search Trees) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ (https://people.mpi-inf.mpg.de/~mehlhorn/ftp/mehlhorn3.pdf, storing left/right subtrees' weights) == Description == == Approximate? == Approximate Approximation Factor: 0.63 H \leq P_opt \leq P_balanced \leq 2 + 1.44 H == Randomized? == No, deterministic == Model of Computation == == Year == 1975 == Reference == https://people.mpi-inf.mpg.de/~mehlhorn/ftp/mehlhorn3.pdf" current
10:3110:31, 15 February 2023 diff hist +432‎ N Weak Parametrized Inapproximability Hypothesis (WPIH) ‎ Created page with "== Target Problem == Approximate 2-CSP == Description == There is some constant $\delta > 0$ such that given an instance $\varphi$ of 2-CSP on the Boolean hypercube graph $Q$ over alphabet of size $n$, it is W(1)-hard to distinguish == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == == Proven? == No == Year == == References/Citation == ? CCC '22" current
10:3110:31, 15 February 2023 diff hist +452‎ N Parametrized Inapproximability Hypothesis (PIH) ‎ Created page with "== Target Problem == Approximate 2-CSP == Description == There is some constant $\delta > 0$ such that 2-CSP on $k$ vertices and alphabet size $n$ is W(1)-hard to approximate to a $(1-\delta)$ factor == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == == Proven? == No == Year == 2017 == References/Citation == https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.134" current
10:3110:31, 15 February 2023 diff hist +395‎ N $\delta$-Triangle Conjecture ‎ Created page with "== Target Problem == Triangle Detection == Description == Any Algorithm requires $m^{1+\delta-o(1)}$ time in expectation to detect whether an $m$ edge graph contains a triangle == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-Ram on $\log(n)$ bit words == Proven? == No == Year == == References/Citation ==" current
10:3010:30, 15 February 2023 diff hist +705‎ N Strong Triangle Conjecture ‎ Created page with "== Target Problem == Triangle Detection == Description == Any Algorithm requires $\min(n^{w-o(1)}, m^{2w/(w+1)-o(1)})$ time in expectation to detect whether an $n$ node $m$ edge graph contains a triangle. Moreover, any combinatorial algorithm requires $m^{3/2-o(1)}$ == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-Ram on $\log(n)$ bit words == Proven? == No == Year == 2014 == Referenc..." current
10:3010:30, 15 February 2023 diff hist +567‎ N More Believable Exponential Time Hypothesis (MBETH) ‎ Created page with "== Target Problem == k-SAT == Description == There exists a $k \geq 3$ and a $\delta > 0$ so that $k$-SAT on $n$ variables cannot be solved in $O(2^{\delta n})$ == Implies the following Hypothesis == ETH == Implied by the following Hypothesis == ETH, SETH == Computation Model == Word-Ram on $\log(n)$ bit words == Proven? == No ==..." current
10:3010:30, 15 February 2023 diff hist +491‎ N Nondeterministic Strong Exponential Time Hypothesis (NSETH) ‎ Created page with "== Target Problem == [[]] == Description == Refuting unsatisfiable $k$-CNF formulas on $n$ variables requires nondeterministic $2^{n-o(n)}$ time for unbounded $k$. == Implies the following Hypothesis == SETH == Implied by the following Hypothesis == == Computation Model == == Proven? == No (Variants have been disproved) == Year == == References/Citation == http://people.csail.mit.edu/virgi/eccentri.p..." current
10:3010:30, 15 February 2023 diff hist +541‎ N Online Matrix Vector Multiplication Hypothesis (OMV Hypothesis) ‎ Created page with "== Target Problem == OMV == Description == Every (randomized) algorithm that can process a given $n \times n$ Boolean matrix $A$, and then in an online way can compute the products $Av_i$ for any $n$ vectors $v_1,\ldots,v_n$, must take total time $n^{3-o(1)}$. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-Ram on $\log(n)$ bit words == Proven? == No == Year == == References/Citatio..." current
10:3010:30, 15 February 2023 diff hist +378‎ N Boolean Matrix Multiplication Hypothesis (BMM Hypothesis) ‎ Created page with "== Target Problem == BMM == Description == Any combinatorial BMM algorithm requires $n^{3-o(1)}$ time. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-Ram on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people.csail.mit.edu/virgi/eccentri.pdf Page 17" current
10:3010:30, 15 February 2023 diff hist +521‎ N Exact k-Clique Hypothesis ‎ Created page with "== Target Problem == Exact $k$-Clique == Description == The Exact $k$-Clique problem on $n$ node graphs with edge weights in $\{-n^{100k},\ldots,n^{100k}\}$ requires (randomized) $n^{k-o(1)}$ time. == Implies the following Hypothesis == OVH == Implied by the following Hypothesis == == Computation Model == Word-Ram on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people..." current
10:3010:30, 15 February 2023 diff hist +588‎ N Min-Weight k-Clique Hypothesis ‎ Created page with "== Target Problem == Min-Weight $k$-Clique == Description == The Min-Weight $k$-Clique problem on $n$ node graphs with edge weights in $\{-n^{100k},\ldots, n^{100k}}$ requires (randomized) $n^{k-o(1)}$ time. == Implies the following Hypothesis == Exact k-Clique Hypothesis, OVH == Implied by the following Hypothesis == == Computation Model == Word-Ram on $\log(n)$ bit words == Proven..." current
10:3010:30, 15 February 2023 diff hist +442‎ N Hitting Set Hypothesis (HS Hypothesis) ‎ Created page with "== Target Problem == HS == Description == No randomized algorithm can solve HS on $n$ vectors in $\{0,1\}^d$ in $n^{2-\epsilon}\poly(d)$ time for $\epsilon > 0$. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-RAM on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people.csail.mit.edu/virgi/eccentri.pdf Hypothesis 5" current
10:3010:30, 15 February 2023 diff hist +517‎ N All Pairs Shortest Paths Hypothesis (APSP Hypothesis) ‎ Created page with "== Target Problem == APSP == Description == No randomized algorithm can solve APSP in $O(n^{3-\epsilon})$ time for $\epsilon > 0$ on $n$ node graphs with edge weights in $\{-n^c,\ldots,n^c\}$ and no negative cycles for large enough $c$. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-RAM on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people.csa..." current
10:3010:30, 15 February 2023 diff hist +467‎ N 3SUM Hypothesis (3-SUM Hypothesis) ‎ Created page with "== Target Problem == 3-SUM == Description == 3-SUM on $n$ integers in $\{-n^4,\ldots,n^4\}$ cannot be solved in $O(n^{2-\epsilon})$ time for any $\epsilon > 0$ by a randomized algorithm. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-RAM on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people.csail.mit.edu/virgi/eccentri.pdf Hypothesis 2" current
10:3010:30, 15 February 2023 diff hist +480‎ N K-Clique Hypothesis ‎ Created page with "== Target Problem == [[$k$-Clique for all $k > 0$]] == Description == No randomized algorithm can detect a $k$-Clique in an $n$-node graph in $O(n^{\omega k / 3 - \epsilon})$ time for any $\epsilon > 0$. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-RAM on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people.csail.mit.edu/virgi/eccentri.pdf Hypothe..." current
10:3010:30, 15 February 2023 diff hist +450‎ N K-OV Hypothesis ‎ Created page with "== Target Problem == k-OV == Description == No randomized algorithm can solve k-OV on instances of size $n$ in $n^{k-\epsilon}\poly(d)$ time for constant $\epsilon > 0$. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-RAM on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people.csail.mit.edu/virgi/eccentri.pdf Hypothesis 4" current
10:3010:30, 15 February 2023 diff hist +590‎ N Unbalanced Orthogonal Vectors Hypothesis (UOVH) ‎ Created page with "== Target Problem == UOV == Description == Let $0 < \alpha \leq 1$. For no $\epsilon > 0$ there is an algorithm for OV, restricted to $m = \Theta(n^\alpha)$ and $d \leq n^{o(1)}$, that runs in time $O((nm)^{(1−\epsilon)})$. == Implies the following Hypothesis == SETH, OVH == Implied by the following Hypothesis == OVH == Computati..." current
10:3010:30, 15 February 2023 diff hist +594‎ N Orthogonal Vectors Hypothesis (OVH) ‎ Created page with "== Target Problem == OV == Description == For no $\epsilon > 0$ there is an algorithm for OV, restricted to $n = m$, that runs in time $O(n^{(2−\epsilon)}poly(d))$. == Implies the following Hypothesis == SETH, UOVH == Implied by the following Hypothesis == k-OV Hypothesis, UOVH == Compu..." current
10:3010:30, 15 February 2023 diff hist +629‎ N Strong Exponential Time Hypothesis (SETH) ‎ Created page with "== Target Problem == k-SAT == Description == For every $\epsilon > 0$, there exists an integer $k \geq 3$ such that $k$-SAT cannot be solved in $O(2^{(1-\epsilon) n})$ time. == Implies the following Hypothesis == MBETH, ETH == Implied by the following Hypothesis == OVH, [[Unbalanced Orthogonal Vectors Hypothesis (UOVH)|UOVH]..." current
10:3010:30, 15 February 2023 diff hist +579‎ N Exponential Time Hypothesis (ETH) ‎ Created page with "== Target Problem == 3SAT == Description == There is some constant $\delta > 0$ such that CNF-SAT requires $\Omega(2^{\delta n})$. == Implies the following Hypothesis == MBETH == Implied by the following Hypothesis == SETH, MBETH == Computation Model == Word-RAM on $\log(n)$ bit words == Proven? =..." current
10:3010:30, 15 February 2023 diff hist +1,235‎ N All-Integers 3SUM ‎ Created page with "{{DISPLAYTITLE:All-Integers 3SUM (3SUM)}} == Description == Given three lists $A, B, C$ of $n$ integers each, output the list of all integers $a \in A$ such that there exist $b \in B,c \in C$ with $a + b + c = 0$. == Related Problems == Generalizations: 3SUM Related: Real 3SUM, 3SUM' == Parameters == <pre>n: number of integers in each set</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions..."
10:3010:30, 15 February 2023 diff hist +2,149‎ N 3SUM' ‎ Created page with "{{DISPLAYTITLE:3SUM' (3SUM)}} == Description == Given three sets of integers $A, B, C$ of total size $n$, are there $a\in A, b\in B, c\in C$ such that $a + b = c$? == Related Problems == Generalizations: 3SUM Related: Real 3SUM, All-Integers 3SUM == Parameters == <pre>n: number of integers in each set</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions TO Problem == {| class="wikitable so..."
10:3010:30, 15 February 2023 diff hist +1,350‎ N Real 3SUM ‎ Created page with "{{DISPLAYTITLE:Real 3SUM (3SUM)}} == Description == Given a set $S$ of reals, determine whether there is a subset of $S$ of size 3 that sums to 0. == Related Problems == Subproblem: 3SUM Related: 3SUM', All-Integers 3SUM == Parameters == <pre>S: the set of reals n: the number of real numbers in the set</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approxim..."
10:3010:30, 15 February 2023 diff hist +2,564‎ N 3SUM ‎ Created page with "{{DISPLAYTITLE:3SUM (3SUM)}} == Description == Given a set $S$ of integers, determine whether there is a subset of $S$ of size 3 that sums to 0. == Related Problems == Generalizations: Real 3SUM Subproblem: 3SUM', All-Integers 3SUM Related: All-Integers 3SUM == Parameters == <pre>S: the set of integers n: the number of integers in the set</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reduc..."
10:3010:30, 15 February 2023 diff hist +1,216‎ N Approximate Hard-Margin SVM ‎ Created page with "{{DISPLAYTITLE:Approximate Hard-Margin SVM (Support Vector Machines (SVM))}} == Description == A (primal) hard-margin SVM is an optimization problem of the following form: $\min\limits_{\alpha_1,\ldots,\alpha_n\geq 0} \frac{1}{2} \sum \limits_{i,j = 1}^n \alpha_i \alpha_j y_i y_j k(x_i, x_j)$ subject to $y_i f(x_i) \geq 1, i = 1, \ldots, n$ where $f(x) := \sum_{i=1}^n \alpha_i y_i k(x_i, x)$ == Parameters == No parameters found. == Table of Algorithms == Curre..." current
10:3010:30, 15 February 2023 diff hist +44‎ N BHCP ‎ Redirected page to Bichromatic Hamming Close Pair current Tag: New redirect
10:3010:30, 15 February 2023 diff hist +1,896‎ N Bichromatic Hamming Close Pair ‎ Created page with "{{DISPLAYTITLE:Bichromatic Hamming Close Pair (Bichromatic Hamming Close Pair)}} == Description == Given two sets $A = \{a_1, \ldots, a_n\} \subseteq \{0, 1\}^d$ and $B = \{b_1, \ldots, b_n\} \subseteq \{0, 1\}^d$ of $n$ binary vectors and an integer $t \in \{2, \ldots, d\}$, decide if there exists a pair $a \in A$ and $b \in B$ such that the number of coordinates in which they differ is less than $t$ (formally, $Hamming(a, b) := |a − b|1 < t$). If there is such a pa..."
10:3010:30, 15 February 2023 diff hist +523‎ N Dynamic Dihedral Rotation Queries ‎ Created page with "{{DISPLAYTITLE:Dynamic Dihedral Rotation Queries (Dihedral Rotation Queries)}} == Description == Determine whether a given dihedral rotation is feasible or not, and if it is, modify the chain by performing the rotation. == Related Problems == Related: Static Dihedral Rotation Queries == Parameters == <pre>n: number of edges in the chain</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == References/Citation ==..."
10:3010:30, 15 February 2023 diff hist +957‎ N Static Dihedral Rotation Queries ‎ Created page with "{{DISPLAYTITLE:Static Dihedral Rotation Queries (Dihedral Rotation Queries)}} == Description == Determine whether a given dihedral rotation is feasible or not, without modifying the chain. == Related Problems == Related: Dynamic Dihedral Rotation Queries == Parameters == <pre>n: number of edges in the chain</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sor..."
10:3010:30, 15 February 2023 diff hist +38‎ N Conjunctive Büchi Objectives ‎ Redirected page to Generalized Büchi Games current Tag: New redirect
10:3010:30, 15 February 2023 diff hist +1,892‎ N Generalized Büchi Games ‎ Created page with "{{DISPLAYTITLE:Generalized Büchi Games (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a standard graph, and the objective is Büchi: given a set of target vertices $T\subseteq V$, determine whether or not there is a path that visits the set $T$ an infinite amount of times. Furthermore, in the conjunctive problem, you are giv..."
10:3010:30, 15 February 2023 diff hist +1,929‎ N Disjunctive coBüchi Objectives ‎ Created page with "{{DISPLAYTITLE:Disjunctive coBüchi Objectives (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a standard graph, and the objective is coBüchi: given a set of target vertices $T\subseteq V$, determine whether or not there is a path that visits the set $T$ a finite amount of times. Furthermore, in the disjunctive problem, you a..."
10:3010:30, 15 February 2023 diff hist +2,387‎ N Disjunctive Queries of Safety in Graphs ‎ Created page with "{{DISPLAYTITLE:Disjunctive Queries of Safety in Graphs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a standard graph, and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether or not there is a path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in $T$). Furthe..."
10:3010:30, 15 February 2023 diff hist +1,057‎ N Safety in Graphs ‎ Created page with "{{DISPLAYTITLE:Safety in Graphs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a standard graph, and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether or not there is a path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in $T$). == Related Problems == Subp..."
10:3010:30, 15 February 2023 diff hist +1,338‎ N Conjunctive Safety Queries in MDPs ‎ Created page with "{{DISPLAYTITLE:Conjunctive Safety Queries in MDPs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in..."
10:3010:30, 15 February 2023 diff hist +1,336‎ N Disjunctive Safety Queries in MDPs ‎ Created page with "{{DISPLAYTITLE:Disjunctive Safety Queries in MDPs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in..."
10:3010:30, 15 February 2023 diff hist +1,087‎ N Safety in MDPs ‎ Created page with "{{DISPLAYTITLE:Safety in MDPs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in $T$). == Related Pr..."
10:3010:30, 15 February 2023 diff hist +54‎ N Generalized Reachability in MDPs ‎ Redirected page to Conjunctive Reachability Queries in MDPs current Tag: New redirect
10:3010:30, 15 February 2023 diff hist +1,365‎ N Conjunctive Reachability Queries in MDPs ‎ Created page with "{{DISPLAYTITLE:Conjunctive Reachability Queries in MDPs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is reachability: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that visits a vertex in $T$ at least once (i.e. you want to reach..."
10:3010:30, 15 February 2023 diff hist +1,363‎ N Disjunctive Reachability Queries in MDPs ‎ Created page with "{{DISPLAYTITLE:Disjunctive Reachability Queries in MDPs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is reachability: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that visits a vertex in $T$ at least once (i.e. you want to reach..."
10:3010:30, 15 February 2023 diff hist +1,085‎ N Reachability in MDPs ‎ Created page with "{{DISPLAYTITLE:Reachability in MDPs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a Markov Decision Process (MDP), and the objective is reachability: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that visits a vertex in $T$ at least once (i.e. you want to reach some vertex in $T$)...."
10:3010:30, 15 February 2023 diff hist +42‎ N MIPS ‎ Redirected page to Maximum Inner Product Search current Tag: New redirect
10:3010:30, 15 February 2023 diff hist +2,800‎ N Maximum Inner Product Search ‎ Created page with "{{DISPLAYTITLE:Maximum Inner Product Search (Maximum Inner Product Search)}} == Description == Given a new query $q$, MIPS targets at retrieving the datum having the largest inner product with $q$ from the database $A$. Formally, the MIPS problem is formulated as below: $p = \arg \max \limits_{a \in A} a \top q$ == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions TO Problem..." current
10:2910:29, 15 February 2023 diff hist +1,339‎ N RNA Folding ‎ Created page with "{{DISPLAYTITLE:RNA Folding (RNA Folding)}} == Description == In RNA Folding we are given a string over some alphabet (e.g. $\{A, C, G, T\}$) with a fixed pairing between its symbols (e.g. $A − T$ match and $C − G$ match), and the goal is to compute the maximum number of non-crossing arcs between matching letters that one can draw above the string (which corresponds to the minimum energy folding in two dimensions). == Parameters == <pre>n: length of the given str..."
10:2910:29, 15 February 2023 diff hist +1,075‎ N Ap-reach ‎ Created page with "{{DISPLAYTITLE:ap-reach (Vertex Reachability)}} == Description == Given a directed graph $G=(V,E)$, determine for each pair $s \neq t \in V$ whether $t$ is reachable from $s$. == Related Problems == Generalizations: st-Reach Related: #SSR, sensitive incremental #SSR, ST-Reach, constant sensitivity incremental ST-Reach, 1-sensitive incremental ss-reach, 2-sensitive incremental st-reach == Parameters == <pre>n: number of vertices m: num..."
10:2910:29, 15 February 2023 diff hist +1,158‎ N 2-sensitive incremental st-reach ‎ Created page with "{{DISPLAYTITLE:2-sensitive incremental st-reach (Vertex Reachability)}} == Description == Given a directed graph $G=(V,E)$ and vertices $s, t \in V$, incrementally determine wheteher $t$ is reachable from $s$, with sensitivity 2, i.e. when 2 edges are added. == Related Problems == Generalizations: st-Reach Related: #SSR, sensitive incremental #SSR, ST-Reach, constant sensitivity incremental ST-Reach, 1-sensitive incremental ss-reach, ap-re..."
10:2910:29, 15 February 2023 diff hist +1,331‎ N 1-sensitive incremental ss-reach ‎ Created page with "{{DISPLAYTITLE:1-sensitive incremental ss-reach (Vertex Reachability)}} == Description == Given a directed graph $G=(V,E)$ and a source node $s \in G$, an incremental single-source reachability algorithm maintains the set of nodes reachable from $s$ (i.e., all nodes $v$ for which there is a path from $s$ to $v$ in the current version of $G$) during a sequence of edge insertions, with sensitivity 1, i.e. when 1 edge is inserted. == Related Problems == Generalizations..."
10:2910:29, 15 February 2023 diff hist +694‎ N Constant sensitivity incremental ST-Reach ‎ Created page with "{{DISPLAYTITLE:constant sensitivity incremental ST-Reach (Vertex Reachability)}} == Description == Given a graph $G=(V,E)$, incrementally determine whether each node $s\in S\subseteq V$ can reach a node $t\in T \subseteq V$, with a constant sensitivity of $K(\epsilon, t)$, i.e. when $K(\epsilon, t)$ edges are added. == Related Problems == Generalizations: ST-Reach Related: #SSR, sensitive incremental #SSR, st-Reach, 1-sensitive incremental ss-reac..."
10:2910:29, 15 February 2023 diff hist +669‎ N St-Reach ‎ Created page with "{{DISPLAYTITLE:st-Reach (Vertex Reachability)}} == Description == Given a directed graph $G=(V,E)$ and vertices $s, t \in V$, determine wheteher $t$ is reachable from $s$. == Related Problems == Subproblem: constant sensitivity incremental ST-Reach, 1-sensitive incremental ss-reach, 2-sensitive incremental st-reach, ap-reach Related: #SSR, sensitive incremental #SSR, ST-Reach, 1-sensitive incremental ss-reach, 2-sensitive increm..."
10:2910:29, 15 February 2023 diff hist +675‎ N ST-Reach ‎ Created page with "{{DISPLAYTITLE:ST-Reach (Vertex Reachability)}} == Description == Given a graph $G=(V,E)$, determine whether each node $s\in S\subseteq V$ can reach a node $t\in T \subseteq V$. == Related Problems == Subproblem: constant sensitivity incremental ST-Reach, 1-sensitive incremental ss-reach, 2-sensitive incremental st-reach, ap-reach Related: #SSR, sensitive incremental #SSR, st-Reach, 1-sensitive incremental ss-reach, 2-sensitive..."

User contributions for Admin

15 February 2023

Navigation menu

Search