Autore Topic: Max Clique  (Letto 208 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline PL3

  • Utente Senior
  • *
  • Post: 179
  • Reputazione: 0
Max Clique
« il: 01 Giugno 2012, 17:34:16 »
Come trovare il LB?

Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Max Clique
« Risposta #1 il: 01 Giugno 2012, 19:34:19 »
Questo argomento non era stato trattato l'anno scorso, e dalla tua domanda non è che ti si possa aiutare più di tanto
(suppongo tu intenda in un contesto di Branch&Bound e non a livello teorico in termini di complessità computazionale, però).

In un tempo molto remoto, quando preparavo le gare per le OII, un po' di teoria dei grafi spinta me l'ero vista, ma oramai mi rimangono solamente vaghi ricordi.
Non vorrei sviarti, però se non sbaglio per le clique veniva praticamente sempre a galla anche il problema degli "indipendent set", per cui se non sai risolvere il problema diretto, tanto vale approcciarlo "di lato".

Eventualmente, se hai degli appunti a riguardo, rendili disponibili, che vediamo se si ricava qualcosa.

Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"