2
$\begingroup$

Hello Does someone have an idea for heuristics for the problem:

Given undirected weighted(weights on edges) complete graph $G(V,E)[|V|=n,|E| = m]$, find a clique of size $k < n$(k is number of nodes) having the minimum weight.

I have searched for minclique problem but it doesn't really answer my question. Thank you in advance.

$\endgroup$
  • $\begingroup$ Is k part of the input or a fixed constant? $\endgroup$ – Robin Kothari Oct 15 '10 at 16:47
  • $\begingroup$ its part of the input $\endgroup$ – Yakov Oct 15 '10 at 16:48
  • 1
    $\begingroup$ weights on edges or vertices ? $\endgroup$ – Suresh Venkat Oct 15 '10 at 16:50
  • $\begingroup$ @Suresh: wieghts on edges $\endgroup$ – Yakov Oct 15 '10 at 16:55
  • $\begingroup$ please edit the problem defn to incorporate this. $\endgroup$ – Suresh Venkat Oct 15 '10 at 16:59
4
$\begingroup$

Your problem appears to be the minimization variant (flip the edge weight signs?) of the edge-weighted maximal clique problem. Check out this reference:

@article{park1996extended,
title={{An extended formulation approach to the edge-weighted maximal clique problem}},
author={Park, K. and Lee, K. and Park, S.},
journal={European Journal of Operational Research},
volume={95}, number={3},
pages={671--682},
year={1996},
publisher={Elsevier} }

where they discuss various LP-based heuristics.

$\endgroup$
  • $\begingroup$ The lp-heuristics is too slow but i will look for other algorithms $\endgroup$ – Yakov Oct 15 '10 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.