Opened 9 years ago

Last modified 5 years ago

#9060 needs_work enhancement

break symmetries in subgraph search

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-6.4
Component: graph theory Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

Useless, when looking for a triangle, to test both abc, bca, and cab. The same is true when looking for Cycles, for complete graphs, etc...

There may be a way to generally deal with those symmetries to improve the speed of subgraph search. Build complete table of n! symmetries if necessary (optional argument to toggle it).

If not, it is still possible to manually improve it for cycles, complete graphs, and other "common" graphs.

Nathann

Change History (6)

comment:1 Changed 9 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 9 years ago by ncohen

  • Status changed from new to needs_work

comment:3 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.