AI Paper Atlas

Research map / Graph learning / Graph algorithms and clustering

Incremental Symmetry Breaking Constraints for Graph Search Problems

Avraham Itzhakov, Michael Codish

AAAI 2020 · Graph learning › Graph algorithms and clustering · approach: Graph comparison and random features · 6 citations (OpenAlex)

Read the paper

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
compute symmetry breaking constraints incrementally instead of directlycolumn-wise symmetry breaking · order 11 graphscomputation time: 12.39d -> 5.56dImproved
incremental instead of direct computationcolumn-wise symmetry breaking · order 10 graphscomputation time: 3.73h -> 2.10hImproved
incremental instead of direct computationcolumn-wise symmetry breaking · order 5 graphscomputation time: 0.07s -> 0.08sNo clear effect
incremental instead of direct computationcolumn-wise symmetry breaking · order 3-11constraint size: 289,698 -> 290,117No clear effect
use compact column-wise constraints instead of LexLeadersymmetry breaking · order 11constraint size: 2,195,424,000 -> 289,698Improved
use specialized constraints per order-7 canonical graph instead of simplified general onessymmetry breaking · order 11average constraint size: 58,561.44 -> 873.03Improved
generate and extend instead of generate and testword-representable graph enumeration · order 11computation time: 1,100d -> 4.04dImproved
generate and extend instead of generate and testword-representable graph enumeration · order 10computation time: 74h -> 1.41hImproved
generate and extend instead of direct constraint solvingtotally magic graphs · order >= 9solutions foundImproved
generate and extend for totally magic graphs vs Jager and Arnoldtotally magic graph enumeration · order 11total computation days: 13,595 -> 976.36Improved
generate and extend for totally magic graphs vs Jager and Arnoldtotally magic graph enumeration · order 10total computation days: 21.70 -> 7.21Improved
filter with step 1 before testing totally magic propertytotally magic graph enumeration · order 11graphs tested: 1,018,997,864 -> 91,397,498Improved

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy