Screenshots

Browse database window

The 'browse database' window. Currently the Berge graphs are selected. The window shows complexity of the Independent Set problem on Berge graphs (polynomial) and its super-, sub-, and equivalent classes.

Complexity boundary for independent set

The boundary between polynomial/NP-complete for the Independent Set problem, as seen when starting from bridged graphs. Red classes are NP-Complete, dark green are polynomial, light green are linear, while white are still open.

Relation between two classes

Finding and drawing the relation between $2K2$ and $(2K2,C4,C5)$-free graphs. The system calculates that $(2K2,C4,C5)$-free graphs are a subclass of $2K2$-free graphs and draws all classes that are superset of one and a subset of the other class.

Choosing the naming preference

The same diagram, but with forbidden subgraph characterization as naming preference.

Database contents

1310 classes
146971 inclusions
updated 2012-02-11


Latest news

  • 2012-01-14 'Find relation' in the Java application now gives a witness for proper inclusions.
  • 2011-11-12 'Find relation' in the Java application now can detect disjoint and incomparable classes.
  • 2011-10-15 Java cleanup and rewrite using jgrapht.