Cum pot determina cardinalul stable setului maximal dintr-un graf folosind un algoritm care genereaza un stable set oarecare.

Last Updated: Nov 13 2016 20:05, Started by cd9 , Nov 12 2016 17:04

#1
cd9

Posted 12 November 2016 - 17:04

Junior Member

Grup: Members
Posts: 195
Înscris: 04.04.2015

Salut! Sa presupunem ca am un algoritm care aplicat pe un graf G genereaza, in timp polinomial, o multime S care este un stable set al grafului G.
Si am si o relatie de genul: alpha(G) - |S| <= k (k constanta, numar natural). Cum as putea folosi algoritmul meu sa aflu cardinalul stable setului maximal.

M-am gandit sa construiesc un graf G* = (k)G, deci reunesc k copii izomore ale grafului G. Daca aplic algoritmul meu pe G* obtin un set stabil S' cu |S'| = alpha(G). Totusi, chestia asta vine mai mult din intuitie, cum as putea sa demostrez formal treaba asta?

Edited by cd9, 12 November 2016 - 17:06.

#2
dani.user

Posted 13 November 2016 - 13:55

Guru Member

Grup: Senior Members
Posts: 30,240
Înscris: 24.02.2007

Mai mari sanse aici.

Edited by dani.user, 13 November 2016 - 13:55.

#3
cd9

Posted 13 November 2016 - 20:05

Junior Member

Grup: Members
Posts: 195
Înscris: 04.04.2015

Badluck, e de 3 zile la bounty pe cs.stackexchange.

Anunturi

Chirurgia spinală minim invazivă

Chirurgia spinală minim invazivă oferă pacienților oportunitatea unui tratament eficient, permițându-le o recuperare ultra rapidă și nu în ultimul rând minimizând leziunile induse chirurgical.

Echipa noastră utilizează un spectru larg de tehnici minim invazive, din care enumerăm câteva: endoscopia cu variantele ei (transnazală, transtoracică, transmusculară, etc), microscopul operator, abordurile trans tubulare și nu în ultimul rând infiltrațiile la toate nivelurile coloanei vertebrale.

www.neurohope.ro

Cum pot determina cardinalul stable setului maximal dintr-un graf folosind un algoritm care genereaza un stable set oarecare.

#1 cd9 Posted 12 November 2016 - 17:04

#2 dani.user Posted 13 November 2016 - 13:55

#3 cd9 Posted 13 November 2016 - 20:05

Anunturi

▶ 0 user(s) are reading this topic

Sign In

#1
cd9

Posted 12 November 2016 - 17:04

#2
dani.user

Posted 13 November 2016 - 13:55

#3
cd9

Posted 13 November 2016 - 20:05