Parallel Maximum Clique Problem Problem Descriptions:
Maximum Clique Problem (MCP) is a fundamental problem in graph theory. Given a graph G with V vertices and E undirected edges, the maximal clique is the largest subset of vertices in which each vertex is directly connected to every other vertex in the subset.
What you need to do is to design and implement an efficient parallel MCP algorithm.
Graph represented in DIMACS ascii format. There is an example partially copied from the file:
Copyright By PowCoder代写 加微信 powcoder
https://iridia.ulb.ac.be/~fmascia/files/DIMACS/C125.9.clq.
The most important information of the input graph is in bold. The indices of vertices start from 1.
A maximum clique with 4 nodes.
FILE: C125.9.clq
SOURCE: Generated by using ggen, a program by
DESCRIPTION: Cx.y is a random graph on x vertices with edge probability .y
G(n,p) graph
c number of vertices : 125
c max number of edges: 20000
c edge probability : 0.900000 c data structure : dense
c Graph Stats
c number of vertices : 125 c nonisolated vertices: 125
graph gen seed : 74328432
c number of edges
c edge density
c max degree
c avg degree
: 0.898452
c min degree
p col 125 6963 e21
Output the size (number of vertices) of the searched maximum clique, and output the number indices in the maximum clique.
Benchmark:
1. https://iridia.ulb.ac.be/~fmascia/files/DIMACS/C125.9.clq
2. https://iridia.ulb.ac.be/~fmascia/files/DIMACS/gen200_p0.9_44.clq 3. https://iridia.ulb.ac.be/~fmascia/files/DIMACS/hamming8-4.clq
4. https://iridia.ulb.ac.be/~fmascia/files/DIMACS/p_hat300-1.clq
5. https://iridia.ulb.ac.be/~fmascia/files/DIMACS/brock400_4.clq
6. https://iridia.ulb.ac.be/~fmascia/files/DIMACS/gen400_p0.9_55.clq 7. https://iridia.ulb.ac.be/~fmascia/files/DIMACS/C500.9.clq
8. https://iridia.ulb.ac.be/~fmascia/files/DIMACS/keller5.clq
9. https://iridia.ulb.ac.be/~fmascia/files/DIMACS/p_hat700-1.clq
10. https://iridia.ulb.ac.be/~fmascia/files/DIMACS/brock800_4.clq
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com