Skip to content

Improve clique finding for digraphs with isolated vertices #23

@wilfwilson

Description

@wilfwilson

For a digraph with isolated vertices, the automorphism group tends to be large - since the isolated vertices can be permuted at will. Therefore calculations involving the automorphism group of such digraphs may take longer. However, for cliques, an isolated vertex is only ever in a trivial (maximal) clique - so we really don't need to compute with these at all. (And they're probably not relevant to other computations either). Therefore the clique finder should pre-process a digraph to remove its isolated vertices using ReducedDigraph.

Metadata

Metadata

Assignees

Labels

enhancementA label for PRs that provide enhancements.

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions