3 ms·
> NAUTY (and SAUCY) were good practical implementations > that found solutions efficiently (except for some > harder class of graphs, maybe). There are g
by lmkg 11y ago
> NAUTY (and SAUCY) were good practical implementations
> that found solutions efficiently (except for some
> harder class of graphs, maybe).
There are good practical implementations of SAT solvers as well (except degenerate cases), even though SAT is the canonical NP-Complete problem.
- abetusk 11y agoFair enough, though I think the problem space is substantially different (though I didn't mention it above). It's much easier to make (random) 3-SAT difficult instances whereas for GI you needed highly structured graphs. Apparently Johnson graphs were one of the classes of graphs that caused people problems in GI.
- wolfgke 11y agoThere are other NP-complete problems, where really hard instances are a lot more rare.