Find Graph Cliques

Description
<div><span>An&#160;</span><a href="http://en.wikipedia.org/wiki/Undirected_graph" title="Undirected graph" class="mw-redirect">undirected graph</a><span>&#160;is formed by a&#160;</span><a href="http://en.wikipedia.org/wiki/Finite_set" title="Finite set">finite set</a><span>&#160;of&#160;</span><a href="http://en.wikipedia.org/wiki/Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a><span>&#160;and a set of&#160;</span><a href="http://en.wikipedia.org/wiki/Unordered_pair" title="Unordered pair">unordered pairs</a><span>&#160;of vertices, which are called&#160;</span><a href="http://en.wikipedia.org/wiki/Edge_(graph_theory)" title="Edge (graph theory)" class="mw-redirect">edges</a><span>. By convention, in algorithm analysis, the number of vertices in the graph is denoted by&#160;</span><i></i><i>n</i><span>and</span><span> the number of edges is denoted by&#160;</span><i>m</i><span>. A&#160;</span><a href="http://en.wikipedia.org/wiki/Clique_(graph_theory)" title="Clique (graph theory)">clique</a><span>&#160;in a graph&#160;</span><i>G</i><span>&#160;is a&#160;</span><a href="http://en.wikipedia.org/wiki/Complete_graph" title="Complete graph">complete</a><span>&#160;</span><a href="http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs" title="Glossary of graph theory">subgraph</a><span>&#160;of&#160;</span><i>G</i><span>; that is, it is a subset&#160;</span><i>S</i><span>&#160;of the vertices such that every two vertices in&#160;</span><i>S</i><span>&#160;are connected by an edge in&#160;</span><i>G</i><span>. A&#160;</span><a href="http://en.wikipedia.org/wiki/Maximal_clique" title="Maximal clique" class="mw-redirect">maximal clique</a><span>&#160;is a clique to which no more vertices can be added; a&#160;</span><a href="http://en.wikipedia.org/wiki/Maximum_clique" title="Maximum clique" class="mw-redirect">maximum clique</a><span>&#160;is a clique that includes the largest possible number of vertices, and the clique number &#969;<span class="GINGER_SOFTWARE_mark">(</span></span><i>G</i><span>) is the number of vertices in a maximum clique of&#160;</span><i>G</i><br/></div><div><i><br/></i></div><a href="http://en.wikipedia.org/wiki/Clique_problem">http://en.wikipedia.org/wiki/Clique_problem</a><div><br/></div><div>The request is for an algorithm that takes as input a map of <span class="GINGER_SOFTWARE_mark">vertex</span> as neighbors and a size k and outputs a list of vertices that form a clique of size k.</div><div><br/></div><div><br/></div><pre><span><span class="GINGER_SOFTWARE_mark">apply</span><span class="GINGER_SOFTWARE_mark">(</span>Map&lt;String<span class="GINGER_SOFTWARE_mark">,</span><span class="GINGER_SOFTWARE_mark">Set&lt;String</span>&gt;&gt; graph, <span class="GINGER_SOFTWARE_mark">int</span> k)</span><br/></pre><div><br/></div>
Fulfilled By
    • requests
Discussion
  • {{comment.username}}
Status
Fulfilled
Bounty expires in
Bounty expired
Bounty
80
Tags
(no tags)