To πρόβλημα ΣΧΕΔΙΑΣΜΟΥ ΔΙΑΣΥΝΔΕΣΙΜΟΤΗΤΑΣ ΥΠΟΣΥΝΟΛΩΝ είναι ένα NP-hard πρόβλημα
το οποίο αντλεί το ενδιαφέρον από διάφορες εφαρμογές όπως ο σχεδιασμός
συστημάτων “vacuum”, η εύρεση της ενδομοριάκης σύνδεσης των πρωτεϊνών, ο
σχεδιασμός επεκτάσιμων δικτύων επικάλυψης και διάφορα άλλα προβλήματα στην
βιομηχανία. Δοθέντος ενός συνόλου κόμβων V και μια συλλογής S = {S1, S2, …, Sm}
επικαλυπτόμενων υποσυνόλων του V, ένας γράφος G ζητείται, με ένα σύνολο ακμών E
ελάχιστου πληθικού αριθμού τέτοιος ώστε κάθε G[Si] να επάγει ένα συνδεδεμένο
υπογράφο στον G. Αρχικά, γίνεται μια γενική μελέτη του προβλήματος αναφορικά με
την πολυπλοκότητα και τις διάφορες τεχνικές που μπορούν να προσεγγίσουν το
πρόβλημα αποτελεσματικά. Μέρος της έως τώρα έρευνας παρουσιάζεται και αναλύεται
και γίνεται μια προσπάθεια για προσέγγιση του γενικού προβλήματος με νέους
αλγόριθμους. Επιπροσθέτως, ερευνώνται ειδικά στιγμιότυπα και τροποποιήσεις του
προβλήματος. Ορισμένα σημαντικά αποτελέσματα σε ειδικά στιγμιότυπα
παρουσιάζονται και ιδιαίτερη προσοχή δίνεται στις τροποποιήσεις του προβλήματος
που αφορούν τοπολογικούς περιορισμούς και συγκεκριμένα αστέρια, μονοπάτια και
δένδρα. Προς αυτήν την κατεύθυνση ορισμένα δημοσιευμένα αποτελέσματα αναλύονται
και γίνεται κάποια συνεισφορά για συγκεκριμένα στιγμιότυπα αυτών.
(EL)
SUBSET INTERCONNECTION DESIGN is an NP-hard problem which draws its motivation
from various applications as the design of vacuum systems, the inference of
inter-molecular protein connectivity, the design of scalable overlay networks,
the inference of social networks from outbreaks and several other problems in
the industry. Given a set of vertices V and a collection S = {S1, S2, …, Sm} of
overlapping subsets of V, graph G is asked, with an edge set E of minimum
cardinality such that every G[Si] induces a connected subgraph in G. At first,
a general study of the problem is conducted concerning its complexity and
various techniques which can approach it efficiently. Part of the work done so
far is presented and analyzed and there is an attempt to approach the general
problem with new algorithms. Moreover, a study is also been made in special
instances and modifications of the problem. Some important results are
presented in special instances and specific notice is given to modifications
with topological constraints and especially to stars, paths and trees. Towards
that direction, some published results are analyzed and some contribution for
specific instances is being made.
(EN)
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
