New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 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...")
- 10:27, 15 February 2023 K-OV (hist | edit) [2,102 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:k-OV (Orthogonal Vectors)}} == Description == Given $k$ sets of $d$-dimensional vectors $A_1, A_2, \ldots, A_k$, each of size $n$, does there exist $a_1 \in A_1, a_2 \in A_2, \ldots, a_k \in A_k$ such that $a_1 * a_2 * \ldots * a_k = 0$? == Related Problems == Subproblem: OV, 3-OV Related: 3-OV, Unbalanced OV == Parameters == <pre>$n$: number of vectors per set $k$: number of sets $d$: dimension of each vector; $d = omega(log(n))$...")
- 10:27, 15 February 2023 OV (hist | edit) [5,802 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:OV (Orthogonal Vectors)}} == Description == Given $n$ vectors in $\{0,1\}^{O(\log n)}$, are two of them orthogonal? == Related Problems == Generalizations: k-OV Subproblem: Unbalanced OV Related: 3-OV == Parameters == <pre>$n$: number of vectors $d$: dimension of each vector; $d = O(log(n))$ typically</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Sp...")
- 10:27, 15 February 2023 MaxSAT (hist | edit) [2,980 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:MaxSAT (Boolean Satisfiability)}} == Description == Given an instance of SAT represented in Conjunctive Normal Form (CNF), compute an assignment to the variables that maximizes the number of satisfied clauses. == Related Problems == Generalizations: Conjunctive Normal Form SAT Related: SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE...")
- 10:27, 15 February 2023 Renamable Horn (hist | edit) [1,109 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Renamable Horn (Boolean Satisfiability)}} == Description == Renamable Horn asks the question whether or not there exists a subset of variables that can be negated such that the boolean formula is turned into a Horn formula == Related Problems == Generalizations: Horn SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT,...")
- 10:27, 15 February 2023 Dual-Horn SAT (hist | edit) [784 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Dual-Horn SAT (Boolean Satisfiability)}} == Description == Dual-Horn SAT restricts the boolean formula to the conjunction of dual-Horn clauses, i.e. clauses with at most one negated literal == Related Problems == Generalizations: Horn SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, [[Not-All-Equal 3-SAT (NAE 3SAT)]...")
- 10:27, 15 February 2023 Horn SAT (hist | edit) [808 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Horn SAT (Boolean Satisfiability)}} == Description == Horn SAT restricts the boolean formula to the conjunction of Horn clauses, i.e. clauses with at most one positive literal == Related Problems == Generalizations: Conjunctive Normal Form SAT Subproblem: Dual-Horn SAT, Renamable Horn Related: SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All...")
- 10:27, 15 February 2023 XOR-SAT (hist | edit) [695 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:XOR-SAT (Boolean Satisfiability)}} == Description == XOR-SAT replaces the ORs in CNF with XORs == Related Problems == Generalizations: Conjunctive Normal Form SAT Related: SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT), k-SAT, 2SAT, 3SAT, 3SAT-5, 4SAT,...")
- 10:27, 15 February 2023 Monotone 3SAT (hist | edit) [772 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Monotone 3SAT (Boolean Satisfiability)}} == Description == Monotone 3SAT is 3SAT with the restriction that all of the literals in a clause are either all negated or all positive == Related Problems == Generalizations: 3SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone No...")
- 10:27, 15 February 2023 4SAT (hist | edit) [1,033 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:4SAT (Boolean Satisfiability)}} == Description == 4SAT restricts the boolean formula to CNF with (at most) 4 literals per clause == Related Problems == Generalizations: k-SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT), [[2SAT]...")
- 10:27, 15 February 2023 3SAT-5 (hist | edit) [736 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3SAT-5 (Boolean Satisfiability)}} == Description == 3SAT-5 is 3SAT with the restriction that each variable occurs in at most 5 clauses == Related Problems == Generalizations: 3SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT), ...")
- 10:27, 15 February 2023 3SAT (hist | edit) [1,486 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3SAT (Boolean Satisfiability)}} == Description == 3SAT restricts the boolean formula to CNF with (at most) 3 literals per clause == Related Problems == Generalizations: k-SAT Subproblem: 1-in-3SAT, Not-All-Equal 3-SAT (NAE 3SAT), 3SAT-5, Monotone 3SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal...")
- 10:27, 15 February 2023 2SAT (hist | edit) [732 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2SAT (Boolean Satisfiability)}} == Description == 2SAT restricts the boolean formula to CNF with (at most) 2 literals per clause == Related Problems == Generalizations: k-SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT), [[3SAT]...")
- 10:27, 15 February 2023 K-SAT (hist | edit) [1,694 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:k-SAT (Boolean Satisfiability)}} == Description == k-SAT restricts the boolean formula to CNF with (at most) k literals per clause == Related Problems == Generalizations: Conjunctive Normal Form SAT Subproblem: 2SAT, 3SAT, 4SAT Related: SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3...")
- 10:27, 15 February 2023 Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT) (hist | edit) [780 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT) (Boolean Satisfiability)}} == Description == Monotone NAE 3SAT is NAE 3SAT with the restriction that all of the literals in a clause are either all negated or all positive == Related Problems == Generalizations: Not-All-Equal 3-SAT (NAE 3SAT) Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT,...")
- 10:27, 15 February 2023 Not-All-Equal 3-SAT (NAE 3SAT) (hist | edit) [876 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Not-All-Equal 3-SAT (NAE 3SAT) (Boolean Satisfiability)}} == Description == NAE 3SAT restricts the boolean formula to CNF with 3 literals per clause and determines whether there is an assignment of variables such that, for none of the clauses, all 3 literals have the same boolean value == Related Problems == Generalizations: 3SAT Subproblem: Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT) Related: SAT, Conjunctive Normal Form SAT, [...")
- 10:27, 15 February 2023 All-Equal-SAT (hist | edit) [839 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:All-Equal-SAT (Boolean Satisfiability)}} == Description == All-Equal-SAT restricts the boolean formula to CNF and determines whether there is an assignment of variables such that, for all of the clauses, all literals have the same boolean value == Related Problems == Generalizations: Conjunctive Normal Form SAT Related: SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, Not-All-E...")
- 10:27, 15 February 2023 Monotone Not-Exactly-1-in-3SAT (hist | edit) [847 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Monotone Not-Exactly-1-in-3SAT (Boolean Satisfiability)}} == Description == Monotone Not-Exactly-1-in-3SAT is Monotone 1-in-3SAT, except that rather than exactly one variable in a clause being true, it requires exactly 0, 2, or 3 of the variables in a clause being true == Related Problems == Generalizations: 1-in-3SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, Monotone 1-in-3SAT, All-Equal-SAT, N...")
- 10:27, 15 February 2023 Monotone 1-in-3SAT (hist | edit) [824 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Monotone 1-in-3SAT (Boolean Satisfiability)}} == Description == Monotone 1-in-3SAT is 1-in-3SAT with the restriction that all of the literals in a clause are all positive (note: here, we don't allow clauses to be all negated literals) == Related Problems == Generalizations: 1-in-3SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE...")
- 10:27, 15 February 2023 1-in-3SAT (hist | edit) [896 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:1-in-3SAT (Boolean Satisfiability)}} == Description == 1-in-3SAT restricts the boolean formula to CNF with 3 literals per clause and determines whether there is an assignment of variables such that exactly 1 of the 3 literals in each clause is TRUE == Related Problems == Generalizations: 3SAT Subproblem: Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT Related: SAT, Conjunctive Normal Form SAT, Disjunctive Normal Form SAT,...")
- 10:27, 15 February 2023 Disjunctive Normal Form SAT (hist | edit) [755 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Disjunctive Normal Form SAT (Boolean Satisfiability)}} == Description == DNF-SAT restricts the boolean formula to disjunctive normal form (DNF), meaning it is the OR of ANDs. == Related Problems == Generalizations: SAT Related: Conjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT), k-S...")
- 10:27, 15 February 2023 Conjunctive Normal Form SAT (hist | edit) [9,078 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Conjunctive Normal Form SAT (Boolean Satisfiability)}} == Description == CNF-SAT restricts the boolean formula to conjunctive normal form (CNF), meaning it is the AND of ORs. == Related Problems == Generalizations: SAT Subproblem: All-Equal-SAT, k-SAT, XOR-SAT, Horn SAT, MaxSAT Related: Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, Not-All-Equal 3-SAT (NAE 3S...")
- 10:27, 15 February 2023 SAT (hist | edit) [3,026 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:SAT (Boolean Satisfiability)}} == Description == Boolean satisfiability problems involve determining if there is an assignment of variables that satisfies a given boolean formula. == Related Problems == Subproblem: Conjunctive Normal Form SAT, Disjunctive Normal Form SAT Related: Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), [...")
- 10:27, 15 February 2023 Chromatic Polynomial (hist | edit) [31 bytes] Admin (talk | contribs) (Created page with "#REDIRECT #k-Graph Coloring")
- 10:26, 15 February 2023 5-Graph Coloring (hist | edit) [689 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:5-Graph Coloring (Graph Coloring)}} == Description == In this case, we wish to determine whether or not a graph is 5-colorable. == Related Problems == Generalizations: k-Graph Coloring Related: Chromatic Number, 2-Graph Coloring, 3-Graph Coloring, 4-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameters == <pre>n: number of vertices m: numb...")
- 10:26, 15 February 2023 4-Graph Coloring (hist | edit) [1,659 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:4-Graph Coloring (Graph Coloring)}} == Description == In this case, we wish to determine whether or not a graph is 4-colorable. == Related Problems == Generalizations: k-Graph Coloring Related: Chromatic Number, 2-Graph Coloring, 3-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameters == <pre>n: number of vertices m: numb...")
- 10:26, 15 February 2023 3-Graph Coloring (hist | edit) [3,281 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3-Graph Coloring (Graph Coloring)}} == Description == In this case, we wish to determine whether or not a graph is 3-colorable. == Related Problems == Generalizations: k-Graph Coloring Related: Chromatic Number, 2-Graph Coloring, 4-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameters == <pre>n: number of vertices m: numb...")
- 10:26, 15 February 2023 2-Graph Coloring (hist | edit) [578 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:2-Graph Coloring (Graph Coloring)}} == Description == In this case, we wish to determine whether or not a graph is 2-colorable. == Related Problems == Generalizations: k-Graph Coloring Related: Chromatic Number, 3-Graph Coloring, 4-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameters == <pre>n: number of vertices m: numb...")