This C++11 project provides efficient data structures for small graphs (n ≤ 64). A graph with n vertices is represented as a adjacency matrix of n machine words, which can be efficiently manipulated by bit twiddling. A few examples are provided.
-
In
extremal.cc, the maximum number of a subgraph such as P3 that a graph on n vertices can have as induced subgraph is determined. Here, a P3 is a path with 3 vertices. It turns out that the numbers are0, 0, 1, 4, 9, 18, 30, 48, 70, 100, 135
-
The file
p5editing.ccexamines a conjecture about a data reduction rule for the P5-Free Editing problem, that is, the problem of adding and deleting a minimum number of edges in a graph to make it P5-free, where P5 is the induced subgraph of a path with 5 vertices. The conjecture is that vertices that are not in any P5 can be omitted, since it is not meaningful to delete them. The program finds a counterexample with 8 vertices. -
In
ssge-approx.cc, the approximation factor of an approximation algorithm for Sparse Split Graph Editing is examined. The worst case found is factor 2.5 for a graph with 6 vertices, and graphs with more vertices seem to have better factors. The best proven bound for this algorithm is a factor of 3 (F. Hüffner, C. Komusiewicz, and A. Nichterlein: Editing graphs into few cliques: complexity, approximation, and kernelization schemes. WADS 2015.)
The default maximum number of vertices is 32. To change this, edit
wordsize.h and run make clean.
Licensed under the Apache License, Version 2.0; see LICENSE.
Non-legally binding summary:
- You can freely use the software without any conditions.
- You can freely distribute the software unmodified as long as you don't strip the license or copyright, patent, trademark, and attribution notices.
- If you want to distribute modified versions, you must additionally state significant changes made and must not misrepresent the original source's endorsement.
Enumeration of graphs up to isomorphism is currently handled by nauty, which comes with the same license.