Changeset 904:c279b19abc62 in lemon-main

Timestamp:

07/23/10 06:29:37 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Add a heuristic algorithm for the max clique problem (#380)

Files:

• doc/groups.dox (modified) (2 diffs)
• doc/references.bib (modified) (1 diff)
• lemon/Makefile.am (modified) (1 diff)
• lemon/grosso_locatelli_pullan_mc.h (added)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (modified) (2 diffs)
• test/max_clique_test.cc (added)

doc/groups.dox

@@ -552 +552 @@
 
 /**
-@defgroup approx Approximation Algorithms
+@defgroup approx_algs Approximation Algorithms
 @ingroup algs
 \brief Approximation algorithms.
@@ -558 +558 @@
 This group contains the approximation and heuristic algorithms
 implemented in LEMON.
+
+<b>Maximum Clique Problem</b>
+  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
+    Grosso, Locatelli, and Pullan.
 */
 

doc/references.bib

@@ -298 +298 @@
   address =      {Dublin, Ireland},
   year =         1991,
-  month =        sep,
-}
+  month =        sep
+}
+
+%%%%% Other algorithms %%%%%
+
+@article{grosso08maxclique,
+  author =       {Andrea Grosso and Marco Locatelli and Wayne Pullan},
+  title =        {Simple ingredients leading to very efficient
+                  heuristics for the maximum clique problem},
+  journal =      {Journal of Heuristics},
+  year =         2008,
+  volume =       14,
+  number =       6,
+  pages =        {587--612}
+}

lemon/Makefile.am

@@ -91 +91 @@
         lemon/graph_to_eps.h \
         lemon/grid_graph.h \
+        lemon/grosso_locatelli_pullan_mc.h \
         lemon/hartmann_orlin_mmc.h \
         lemon/howard_mmc.h \

test/CMakeLists.txt

@@ -32 +32 @@
   maps_test
   matching_test
+  max_clique_test
   min_cost_arborescence_test
   min_cost_flow_test

test/Makefile.am

@@ -34 +34 @@
         test/maps_test \
         test/matching_test \
+        test/max_clique_test \
         test/min_cost_arborescence_test \
         test/min_cost_flow_test \
@@ -85 +86 @@
 test_mip_test_SOURCES = test/mip_test.cc
 test_matching_test_SOURCES = test/matching_test.cc
+test_max_clique_test_SOURCES = test/max_clique_test.cc
 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc