Projects ακαδημαικού έτους 2002-2003

Project 1: Generalized Visibility Representations

Let G be a (not necessarily planar) graph. A generalized visibility representation for G is defined as follows:

Each vertex is mapped to a horizontal vertex segment and each edge is mapped to a vertical edge segment connecting the two corresponding vertex segments. Clearly, since the graph is not planar, some edges will be drawn between vertex segments that are not visible (i.e., the edge segments will "pass through" some vertex segments). We call this a crossing.

Write a program to costruct generalized visibility representations for any given graph G. Naturally, you want to minimize either

  • the number of edges that cross some vertex segment, or
  • the total number of crossings, or
  • the number of vertex segments that are crossed, or
  • the maximum number of vertex segments crossed by an edge, or any combination of the these measures.

Given a graph G your program should draw the generalized visibility representation for G and report at least the numbers for all the measures above.

Project 2: Σχεδιασμός του centralized network ενός τηλεπικοινωνιακού δικτύου

Το δίκτυο μπορεί να αναπαρασταθεί με ένα αμφίδρομο γράφο με βάρη στις ακμές (undirected weighted graph) όπου:

  • οι κόμβοι: αποτελούν τους σταθμούς (ή τερματικά) του δικτύου. (Για παράδειγμα τα MSCs ενός παροχέα κινητής τηλεφωνίας)
  • οι ακμές: αποτελούν τις δυνατές συνδέσεις ανάμεσα στους σταθμούς
  • τα βάρη : αναπαριστούν το κόστος σύνδεσης κάθε διασύνδεσης. (Για παράδειγμα το κόστος καλωδίωσης ανάμεσα στους σταθμούς)

Στόχος:

Η κατασκευή ενός δικτύου όπου όλοι οι κόμβοι πρέπει να επικοινωνούν μεταξύ τους δηλαδή σε μορφή συνδεδεμένου δένδρου. Απαίτηση είναι το κόστος των γραμμών της καλωδίωσης να είναι το ελάχιστο δυνατό (MST). Επιπλέον θα πρέπει να τηρείται ο ακόλουθος περιορισμός. Κάθε κόμβος i δεν θα πρέπει να έχει πάνω από bi συνδέσεις με άλλους κόμβους (Degree constrained MST). Μία τέτοια παράμετρος συναντάται σε πολλά προβλήματα του πραγματικού κόσμου και μπορεί να αφορά την αποφυγή συσσώρευσης φόρτου σε ένα κόμβο ή την ασφάλεια των δικτύων.

Υλοποίηση:

Πρέπει να υλοποιήσετε τρεις διαφορετικούς αλγόριθμους οι οποίοι θα δέχονται ως είσοδο έναν συνδεδεμένο (αν όχι πλήρη) γράφο και ένα άνω όριο συνδέσεων, b, που ισχύει για όλους τους κόμβους. Ως έξοδο θα παράγουν ένα Degree Constrained Minimum Spannig Tree. Ο παραγόμενος γράφος στη συνέχεια θα οπτικοποιείται.

Παρακάτω δίνεται το paper με τους τρεις αλγόριθμους και τα απαραίτητα παραδείγματα για πιθανές δοκιμές.

S. H. Narula and C. A. Ho " Degree-Constrained Minimum Spanning tree" (pdf).