search

snowleopard / alga

Algebraic graphs
MIT License
722 stars 69 forks source link

Implement graph complement #21

Open snowleopard opened 7 years ago

snowleopard commented 7 years ago

(I think this is mostly relevant for undirected graphs.)

Graph complement of an undirected graph (V, E) is (V, K \ E), where K is the clique on all vertices V, e.g. see https://en.wikipedia.org/wiki/Complement_graph.

Interestingly, complements of sparse graphs have as compact algebraic representations as sparse graphs.

snowleopard commented 5 years ago

Thanks to @gabrielelana and @sphaso we now have a simple implementation: #237. There is a lot of room for improvement though, since the current complexity is O(n^2 * m) time and O(n^2) memory.

Let's keep this open.

fawaz990 commented 4 years ago

ممكن احد يفهمني هاذا البرنامج حق ايش

snowleopard commented 4 years ago

@fawaz990 Please use English so that as many people as possible could participate without relying on Google translate.