struct ring::PackingCertificate

Overview

Proof that the reported number of equatorial rings is maximum. More…

#include <src/include/internal/topo_bulk.hpp>
 
struct PackingCertificate {
    // fields
 
    int cages = 0;
    int upper = -1;
    int matching = 0;
    int cover = 0;
    int isolates = 0;
    int vertices = 0;
    int edges = 0;
    int components = 0;
    int method = 0;
    bool tight = false;
    double milliseconds = 0;
};

Detailed Documentation

Proof that the reported number of equatorial rings is maximum.

method 1: the mutual-conflict graph is the line graph of a bipartite graph, and a matching equals a König cover. method 2: each connected component was solved by branch-and-bound. The cover is a clique partition (an upper bound). When it equals the set, that partition is the certificate; otherwise the exhausted search is.