Se anunță susținerea tezei de doctor în științe matematice „Acoperirea cu mulțimi d-convexe a grafurilor neorientate” a dlui Buzatu Radu

Postat 14/03/2017 in categoria Announcements

Pretendent: Buzatu Radu

Conducător ştiinţific: Cataranciuc Sergiu, doctor habilitat în științe matematice, profesor universitar

Consiliul Ştiinţific Specializat: D 30.112.03 – 07 la Universitatea de Stat din Moldova

Tema tezei: „Acoperirea cu mulțimi d-convexe a grafurilor neorientate

Specialitatea: 112.03 – Cibernetică Matematică și Cercetări Operaționale

Data: 23.03.2017

Ora: 16:00

Local: MD 2009, Republica Moldova, mun. Chişinău, str. A. Mateevici 60, bloc IV, sala 222/4.

 

Principalele publicaţii ştiinţifice la tema tezei ale autorului:

  1. Buzatu R. Covers of graphs by two convex sets. Studia univ. Babeș-Bolyai, Series Informatica, vol. LXI, no. 1, 2016, p 5–22.
  2. Buzatu R. Minimum convex cover of special nonoriented graphs. Studia Universitatis Moldaviae, Seria “Științe exacte și economice”, 2(92), 2016, p. 46–54.
  3. Buzatu R., Cataranciuc S. Nontrivial convex covers of trees. Buletinul Academiei de Științe a Republicii Moldva, Matematica, No. 3(82), 2016, p. 72–81.
  4. Buzatu R., Cataranciuc S. Convex graph covers. Computer Science Journal of Moldova, vol. 23, no. 3(69), 2015, p 251–269.
  5. Buzatu R., Cataranciuc S. Acoperirea unui graf neorientat cu mulțimi convexe netriviale. Materialele Conferinței Internaționale: Modelare Matematică, Optimizare și Tehnologii Informaționale, Volumul I, 22–25 martie 2016, Chișinău, Moldova, 2016, p. 64–71.
  6. Buzatu R. Cataranciuc S. Minimum convex covers of some graph operations. A XX-a Conferința Anuală a Societății de Științe Matematice din Romania Dedicată celei de-a 80-a aniversări a Prof. Univ. Emerit Dr. Ioan A. RUS, Baia Mare, 19–22 mai 2016, p. 18–19.
  7. Buzatu R. Nontrivial convex cover of a tree. Proceedings of the 24th Conference on Applied and Industrial Mathematics, CAIM-2016, Craiova, Romania, September 15–18, p. 82.
  8. Buzatu R. NP-completeness of graph convex cover problems. Proceedings of International Conference “Mathematics & Information Technologies: Research and Education”, (MITRE-2015), Chișinău, Moldova, p. 13.

 

Rezumatul tezei

Problema științifică importantă soluționată constă în demonstrarea NP-completitudinii problemei de acoperire/divizare a unui graf neorientat cu mulțimi d-convexe, ceea ce a condus la necesitatea studierii condițiilor de existență a  mulțimi d-convexe, ce formează acoperire/divizare unor clase de grafuri pentru implementarea ulterioară în construirea metodelor și algoritmilor eficienți de soluționare a problemelor aplicative.

Conţinutul de bază al tezei:

Teza este scrisă în limba română și conține introducere, trei capitole, concluzii generale și recomandări, bibliografie ce cuprinde 115 de titluri. Lucrarea conține 122 pagini text de bază. Rezultatele obținute sunt publicate în 12 lucrări științifice.

Capitolul I poartă un caracter introductiv și are drept scop examinarea situației actuale în domeniul de cercetare al tezei, evidențierea unor probleme ce urmează a fi investigate și propunerea metodologiei de soluționare a lor.

Capitolul II conține rezultatele de bază, obținute de către autor cu referite la                        NP-completitudinea problemei de acoperire cu două mulțimi d-convexe și a problemelor de acoperire/divizare cu mulțimi d-convexe netriviale.

În Capitolul al III-lea este examinată problema de acoperire cu mulțimi d-convexe netriviale pe diferite clase de grafuri, care se regăsesc la soluționarea problemelor practice. Printre clasele de grafuri studiate se enumeră grafurile triangulate, grafurile ce formează puterea ciclului, grafurile cactus, arborii.

Principalele rezultate obținute:

  • A fost demonstrat că problema acoperirii grafului cu mulțimi d-convexe, atât în caz general cât și în cazul mulțimilor d-convexe netriviale, este o problemă NP-completă;
  • Au fost stabilite condițiile de existență a unei familii de mulțimi d-convexe, ce formează o acoperire a grafului neorientat;
  • Au fost elaborați algoritmi polinomiali pentru soluționarea problemelor de acoperire/divizare a unor clase de grafuri cu mulțimi d-convexe;
  • Au fost deduse formulele recurente de calcul ale numărului maxim de mulțimi d-convexe netriviale, care acoperă sau divizează un arbore;
  • A fost estimat numărul de acoperire/divizare d-convexă minimă pentru diferite clase de grafuri speciale.