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 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...")
- 10:26, 15 February 2023 Chromatic Number (hist | edit) [709 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Chromatic Number (Graph Coloring)}} == Description == In this case, we wish to compute the chromatic number of a graph; that is, the smallest number of colors needed to color the graph. == Related Problems == Related: k-Graph Coloring, 2-Graph Coloring, 3-Graph Coloring, 4-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameter...")
- 10:26, 15 February 2023 K-Graph Coloring (hist | edit) [962 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:k-Graph Coloring (Graph Coloring)}} == Description == Graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In this case, the number of colors we have is given as an input. == Related Problems == Subproblem: 2-Graph Coloring, 3-Graph Coloring, 4-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring Related: Chromati...")
- 10:26, 15 February 2023 Link Analysis (hist | edit) [3,244 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Link Analysis (Link Analysis)}} == Description == Unlike "flat" document collections, the World Wide Web is hypertext and provides considerable auxiliary information on top of the text of the web pages, such as link structure and link text. With link analysis, we take advantage of the link structure of the Web to produce a global "importance" ranking of every web page that helps search engines and users quickly make sense of the vast heterogeneity of the...")
- 10:26, 15 February 2023 No-Steal/Force (hist | edit) [470 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:No-Steal/Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a No-Steal/Force policy, the recovery algorithm will never write uncommited data to memory, but will force all commits to memory. == Related Problems == Related: Steal/No-Force == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem.")
- 10:26, 15 February 2023 Steal/No-Force (hist | edit) [554 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Steal/No-Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a Steal/No-Force policy, the recovery algorithm will write possibly uncommited data to memory, while not forcing all commits to memory. == Related Problems == Related: No-Steal/Force == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem...")
- 10:26, 15 February 2023 Online (hist | edit) [2,107 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Online (Page Replacements)}} == Description == When page fault occurs during the program execution, operating systems use page replacement algorithms to select a victim page from primary memory and makes room for the required page. == Related Problems == Related: Offline == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Ap...")
- 10:26, 15 February 2023 Offline (hist | edit) [866 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Offline (Page Replacements)}} == Description == When page fault occurs during the program execution, operating systems use page replacement algorithms to select a victim page from primary memory and makes room for the required page. == Related Problems == Related: Online == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Ap...")
- 10:26, 15 February 2023 Dining Philosophers Problem (hist | edit) [1,486 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Dining Philosophers Problem (Deadlock Avoidance)}} == Description == There are $n$ philosophers numbered 0 through $n-1$, seated around a circle table. Their only problem--besides philosophy--is that the dish served is a very difficult kind of spaghetti, that has to be eaten with two forks. There are two forks next to each plate, so that presents no difficulty: as a consequence, however, no two neighbors may be eating simultaneously. The philosophers' li...")