Follow

Un groupe de gens veut faire un Secret Santa mais où chacun donnera un cadeau à un de ses "amis" : étant donné le graphe des amitiés, on veut calculer si c'est possible ?

Si on demande un seul "cycle" de cadeaux alors c'est NP-dur (= Hamiltonian cycle), mais si on en permet plusieurs alors c'est PTIME (= vertex-disjoint cycle cover).

À présent, si on interdit les échanges entre 2 amis mutuels, alors ça reste PTIME si le graphe d'amitiés est non-orienté mais ça devient NP-dur s'il est orienté !

· · Web · 0 · 0 · 0
Sign in to participate in the conversation
La Quadrature du Net - Mastodon - Media Fédéré

Mamot.fr est une serveur Mastodon francophone, géré par La Quadrature du Net.