Maximum independent set algorithms, e.g. branching, measure and conquer.
Type ] in a Julia REPL, then input
pkg> dev git@github.com:GiggleLiu/EliminateGraphs.jl.gitjulia> using EliminateGraphs
julia> eg = rand_eg(60, 0.05);
julia> mis1(eg) # naive branching algorithm with O(3^(n/3)) complexity.
julia> mis2(eg) # sophisticated branching algorithm with O(1.2852^N) complexity.Using EliminateGraph,
julia> p = K_eg(3,3)
EliminateGraph
0 0 0 1 1 1
0 0 0 1 1 1
0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 0 0 0
1 1 1 0 0 0
julia> q = p \ Neighbors{CLOSED, 1}(3)
EliminateGraph
0 0 ⋅ ⋅ ⋅ ⋅
0 0 ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅
julia> nv(q), ne(q)
(2, 0)
julia> vertices(q)
2-element VertexIter{EliminateGraph}:
1
2
julia> neighbors(p, 3)
NeighborIter{OPEN,1,EliminateGraph}
(4, 5, 6)