Independent Set |
Maximum set of pairwise non-adjacent vertices in a graph |
![](graph_is.png) |
![](lp_is.png) |
p = MixedIntegerLinearProgram(maximization = True)
b = p.new_variable(binary = True)
p.set_objective( sum([b[v] for v in g]) )
for u,v in g.edges(labels = False):
p.add_constraint( b[u] + b[v] <= 1 )
p.solve()
b = p.get_values(b)
print [v for v,i in b.items() if i]
|
Dominating Set |
Minimum set of vertices whose neighborhood is the whole graph |
![](graph_dom.png) |
![](lp_dom.png) |
|
Vertex Cover |
Minimum Set of vertices touching each edge |
![](graph_vc.png) |
|
|
Partition |
Partition a set of integers into two sets whose sum is equal |
![](graph_partition.png) |
|
|
Bipartite Set |
Partition the graph into two independent sets |
![](graph_bip.png) |
|
|
Subset Sum |
Find a nonempty subset of integers with null sum |
![](graph_subsetsum.png) |
|
|
Distances |
Compute the distance from vertex 0 to any other |
![](graph_distance.png) |
|
|
Girth |
Size of the shortest cycle |
![](graph_girth.png) |
|
|
Matching |
Maximum number of non-incident edges |
![](graph_matching.png) |
|
|
Feedback Arc Set |
Minimum set of arcs hitting all circuits |
![](graph_fas.png) |
|
|
Feedback Vertex Set |
Minimum set of vertices hitting all circuits |
![](graph_fvs.png) |
|
|
Hamiltonian Cycle |
A cycle going through all vertices |
![](graph_tsp.png) |
|
|
3-coloration |
Partition a graph into three independent sets |
![](graph_col.png) |
|
|