Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement graph complement #21

Open
snowleopard opened this issue Sep 6, 2017 · 3 comments · Fixed by #237
Open

Implement graph complement #21

snowleopard opened this issue Sep 6, 2017 · 3 comments · Fixed by #237

Comments

@snowleopard
Copy link
Owner

(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
Copy link
Owner Author

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
Copy link

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

@snowleopard
Copy link
Owner Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants