| Description: |
Ερευνούμε δύο εκδοχές του προβλήματος του Συνδεδεμένου Κυρίαρχου Συνόλου (ΣΚΣ), τα προβλήματα του Μερικώς Συνδεδεμένου Κυρίαρχου Συνόλου (ΜΣΚΣ) και του Μπάτζετ Συνδεδεμένου Κυρίαρχου Συνόλου (ΠΣΚΣ). Ερευνούμε επίσης τρία ακόμη προβλήματα, χαλαρά ή στενά συσχετισμένα με το ΣΚΣ, τα οποία είναι: Τα προβλήματα του Γαλαξιακού Κοντινότερου Μονοπατιού, του Άμεσου Μπάτζετ Συνδεδεμένου Κυρίαρχου Συνόλου και του Κυρίαρχου Συνόλου Εκμηδένισης. Επακολούθως του καθενός από αυτά, παρουσιάζουμε κάποιες από τις πιθανές εφαρμογές και επεκτάσεις του. Επιπλέον, εστιάζοντας στα προβλήματα ΜΣΚΣ και ΠΣΚΣ, εισάγουμε δύο τροποποιημένες εκδοχές τους, που είναι τα προβλήματα του Μερικώς Κυρίαρχου Μονοπατιού και του k-Κυρίαρχου Μονοπατιού (ή του Μπάτζετ Κυρίαρχου Μονοπατιού), αντίστοιχα. Τελικώς, γίνεται μια προσπάθεια για προσέγγιση και των δύο με νέους αλγορίθμους. H ανάλυσή και τα αποτελέσματά μας παρουσιάζονται σε κάποια συγκεκριμένα στιγμιότυπα. ; We study two versions of the Connected Dominating Set (CDS) problem, the Partial Connected Dominating Set (PCDS) and the Budgeted Connected Dominating Set (BCDS) problems. We also study three other problems, loosely or strictly related to the CDS, which are: Τhe Online Budgeted Connected Dominating Set, the Galactic Shortest Path and the Annihilator Dominating Set problems. Following each one, we present some of its possible applications and extensions. Furthermore, focusing on the PCDS and BCDS problems, we introduce two modified versions respectively, the Partial Dominating Path and the k-Dominating Path (or Budgeted Dominating Path) problems. Finally, an attempt to approach both of them is made with new algorithms. The analysis and our results are presented in some specific instances. |