Wolfram Research

Second DIMACS P-Hat Graph 7

The Second DIMACS Implementation Challenge: 1992-1993

Originator: Patrick Soriano and Michel Gendreau

NP Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability, The Second DIMACS Implementation Challenge: 1992-1993.

Random graphs generated with the p hat generator which is a generalization of the classical uniform random graph generator. Uses 3 parameters: n, the number of nodes, and a and b, two density parameters verifying 0 <= a <= b <= 1.

Examples

Basic Examples

Retrieve the graph:

In[1]:=
ResourceData["Second DIMACS P-Hat Graph 7"]
Out[1]=

Summary properties:

In[2]:=
ResourceData["Second DIMACS P-Hat Graph 7", All]["Summary"]
Out[2]=

Basic Applications

Find the maximum clique:

In[3]:=
g = ResourceData["Second DIMACS P-Hat Graph 7"];
In[4]:=
maxclique = FindClique[g]
Out[4]=

Show the maximum clique:

In[5]:=
HighlightGraph[g, Subgraph[g, maxclique], VertexCoordinates -> ReplacePart[
GraphEmbedding[g, "SpringElectricalEmbedding"], 
Thread[Map[VertexIndex[g, #]& , 
First[maxclique]] -> CirclePoints[{4., 1.2}, 0.8, 
Length[
First[maxclique]]]]], Sequence[
 EdgeStyle -> {Blank[] -> Opacity[0.05]}, GraphLayout -> "SpringElectricalEmbedding", VertexSize -> {Blank[] -> 0.5}]]
Out[9]=

Wolfram Research, "Second DIMACS P-Hat Graph 7" from the Wolfram Data Repository (2019) 

Data Resource History

Source Metadata

Data Downloads

Publisher Information