Description Usage Arguments Details Value Examples
View source: R/graph_culberson.R
Implemented methods: 1. Flat graph 2. Equipartite graph with independent random edge assignment 3. K-Colorable graph with variability and independent random edge assignment
1 | graph_culberson_flat(N, probability = 1, flatness = 0)
|
N |
Integer - number of vertices in the graph. |
probability |
0..1 - edge's probability. |
flatness |
0.. - (flatness = 0 -> fairly uniform) |
K |
- number of partitions (colors) |
Flat Graph Source: http://webdocs.cs.ualberta.ca/~joe/Coloring/Generators/flat.html
The algorithm is defined in 3 steps:
1- Create a permutation of nodes 2- Create 3 groups with N/3 nodes 3- Given two groups A and B, select edges at random from the pairs AxB, subject to: - for any a in A degree(a in AxB) <= ceil(e_AB / |A|) + flatness - for any b in B degree(b in AxB) <= ceil(e_AB / |B|) + flatness - where e_AB = |A|*|B|*(edge's probability)
Discussion about this graph: J. Culberson, F. Luo. “Exploring the k-Colorable landscape with iterated greedy.” Cliques, Coloring, and Satisfiability DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Jan. 1996, pp. 245–284.
a list with two elements: V - number of nodes in the graph, and E - an edge list in the shape of a 2xE matrix. The graph is guaranteed to have a valid 3-coloring
1 | graph_culberson_flat(10,1,0)
|
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.