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é !

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

Bienvenue dans le media fédéré de la Quadrature du Net association de défense des libertés. Les inscriptions sont ouvertes et libres.
Tout compte créé ici pourra a priori discuter avec l'ensemble des autres instances de Mastodon de la fédération, et sera visible sur les autres instances.
Nous maintiendrons cette instance sur le long terme.