Προηγμένα θέματα στους αλγόριθμους γραφημάτω

Αυτό το αρχείο περιέχει υλικό σχετικά με το μάθημα «Advanced Topics in Algorithms Graph» © που διδάσκεται από τον Ron Shamir στο τμήμα Επιστήμης Υπολογιστών του πανεπιστημίου Tel-Aviv στις 10 / 91-2 / 92 (Φθινόπωρο 92), 4-6 / 94 Spring 94) και 4-6 / 97 (άνοιξη 97). Αυτό ήταν ένα εξάμηνο μαθήματα ανοιχτό επίσης για τους ηλικιωμένους, με μια τριήμερη συνεδρίαση κάθε εβδομάδα.

Το μάθημα υπογράμμισε αλγοριθμικές και δομικές πτυχές των «ωραίων» οικογενειών γραφημάτων, ιδιαίτερα τέλειων γραφημάτων, γραφημάτων διαστήματος, γραφημάτων χορδή και γραφημάτων συγκρισιμότητας.

Στο Φθινόπωρο 92 το μάθημα βασίστηκε σε μεγάλο βαθμό στο κλασικό βιβλίο του Martin C. Golumbic “Αλγόριθμος Θεωρίας Γραφήματος και Τέλειων Γραφημάτων” (Academic Press, 1980), και σε μερικά μέρη επίσης στο χειρόγραφο “The Art of Combinatorics” από τον Douglas B. West.

Το μάθημα της Άνοιξης 94 και της Άνοιξης 97 είχε παρόμοια βάση, αλλά υπογράμμισε πιο πρόσφατο υλικό και έκανε πολλές αναφορές σε εφαρμογές στη μοριακή βιολογία. (Δείτε τους αλγόριθμους της ιστοσελίδας για τη μοριακή βιολογία για πολλά περισσότερα σχετικά με αυτές τις πτυχές.)

ιαθέσιμο υλικό:

Λεπτομερή περιγραφή του μαθήματος.

Προηγμένα θέματα στους αλγόριθμους γραφημάτων

 ιαθέσιμο υλικό:

Λεπτομερή περιγραφή του μαθήματος.

• Άνοιξη 97(HTML)
• Άνοιξη 94(ASCII)
• Φθινόπωρο 92(ASCII)

Το υλικό του μαθήματος της Άνοιξης του 1997 (ανεξερεύνητο, ορισμένοι σύνδεσμοι δεν ενημερώθηκαν και κάποιο υλικό είναι αναγνώσιμο μόνο στα προγράμματα περιήγησης TAU.

επίσημη ιστοσελίδα του μαθήματος

ενεργή ιστοσελίδα

Συντάκτες της Άνοιξης 94 διαλέξεις

Οι συνομιλίες περιγράφηκαν από τους μαθητές και αναθεωρήθηκαν από τον καθηγητή. Το πλήρες σετ σημειώσεων επεξεργάστηκε και διαμορφώθηκε στη συνέχεια από τον Sariel Har-Peled. Ευχαριστώ, Σάριελ!

Μπορείτε είτε να κατεβάσετε τις πλήρεις σημειώσεις ως ένα ενιαίο αρχείο postscript (150 σελίδες), ή κάθε διάλεξη ξεχωριστά.

Για μεταφράσεις των σημειώσεων διάλεξης σε άλλες γλώσσες δείτε εδώ.

Κάλυμμα

• Εξώφυλλο
• Πίνακας Περιεχομένων
• Κατάλογος των αριθμών

ιάλεξη # 1: Εισαγωγή στη Θεωρία Γραφημάτων

• Βασικοί ορισμοί και σημειώσεις
• ιαγράμματα διασταύρωσης
• ιαγράμματα κυκλικού τόξου
• ιαγράμματα διαστήματος
• Γραφήματα γραμμής διμερών γραφημάτων

ιάλεξη # 2: Perfect Graphs

• Ορισμός τέλειου γραφήματος
• Ορισμένοι ορισμοί και ιδιότητες
• Perfect Graph Θεώρημα

ιάλεξη # 3: Τέλεια και τριγωνικά γραφήματα

• Perfect Graphs
• $ p $ -Critical Graphs
  • Εισαγωγή
  • Χαρακτηριστικά τριγωνισμένα γραφήματα
  • Αναγνώριση τριγωνικών γραφημάτων
  • Χρόνος Πολυπλοκότητα
    • Ένας πολυεδρικός χαρακτηρισμός των τέλειων γραφημάτων
    • Η Ισχυρή Perfect Graph Εικασία

    Τριγωνικά γραφήματα

ιάλεξη # 4: Αναγνώριση τριγωνικών γραφημάτων

• Αναγνώριση τριγωνικών γραφημάτων
• ημιουργία ενός PEO
• οκιμή ενός προγράμματος απομάκρυνσης
  • Ανεπιθύμητος Αλγόριθμος
  • Αποτελεσματικός Αλγόριθμος
  • Παράδειγμα
  • Η ορθότητα του αλγορίθμου
  • Πολυπλοκότητα του Αλγορίθμου
• Τριγωνισμένα γραφήματα ως διαγράμματα διασταύρωσης
• Εξελικτικά δέντρα
• Τριγωνισμένα γραφήματα ως διαγράμματα διασταύρωσης

ιάλεξη # 5: Τα τριγωνικά γραφήματα είναι τέλεια

• Τα τριγωνικά γραφήματα είναι τέλεια
• Αποδείξτε αυτή την ιδιότητα
• Άλλα Αποτελέσματα

Υπολογισμός της ελάχιστης συμπλήρωσης

• Το πρόβλημα
• Η συμπλήρωση είναι NP-Hard
• Γραφήματα Αλυσίδας
• Βέλτιστη Γραμμική Διάρθρωση (OLA)
• Ολοκλήρωση γραφήματος αλυσίδας (CGC)
• Το αποτέλεσμα για τη συμπλήρωση

Προβλήματα

ιάλεξη#6: Αλγόριθμοι για τριγωνικά γραφήματα και γραφήματα συγκρισιμότητας

• Μερικοί Αλγόριθμοι Βελτιστοποίησης σε Τριγωνισμένα Γραφήματα
• Υπολογισμός του χρωματικού αριθμού και όλων των μέγιστων κλιμάκων
• Εύρεση $ \ alpha $ και $ k $

Γράφημα συγκρισιμότητας

• Μερικοί ορισμοί
• Τάξεις επιπτώσεων
• Το Τρίγωνο Λήμμα
• Αποσύνθεση γραφημάτων

ιάλεξη # 7:  Μοναδικά μερικώς διατιθέμενα γραφήματα

• Μοναδικά μερικώς διατιθέμενα γραφήματα
• Χαρακτηρισμοί και Αλγόριθμοι Αναγνώρισης

ιάλεξη#8: Μερικές ενδιαφέρουσες οικογένειες γραφημάτων που χαρακτηρίζονται από τομή

• Εισαγωγή
• ιαγράμματα μεταβολής
• $ F $ -Γγραφα
• “ Οι ελεγκτές αέρα χτυπάνε ”
• Σύνθεση διαγράμματος μεταστοιχείωσης.
• Γραφήματα ανοχής
• Τα διαγράμματα διαστήματος ως υποσύνολο γραφημάτων ανοχής.
• Οριακά και μη δεσμευμένα διαγράμματα ανοχής.

ιάλεξη#9: Γράφημα συγκρισιμότητας

• Αναγνώριση γραφήματος συγκρισιμότητας
• Η πολυπλοκότητα της αναγνωσιμότητας γραφήματος συγκρισιμότητας
• Εκτέλεση
• Ανάλυση Πολυπλοκότητας

Χρωματισμός και άλλα προβλήματα στα γραφήματα συγκρισιμότητας

• Τα γραφήματα συγκρισιμότητας είναι τέλεια
• Μέγιστη σταθμισμένη κλίση
• Υπολογισμός $ \ alpha (G) $

Η διάσταση των μερικών παραγγελιών

ιάλεξη # 10: Συμβατότητα μεταβλητών και διαγράμματα διαστήματος

• Comparability invariants
• Interval graphs

ιάλεξη # 11: ιαγράμματα διαστήματος

• Προτίμηση και αδιαφορία
• Αναγνώριση γραφημάτων διαστήματος
  • Ένας τετραγωνικός αλγόριθμος
  • Ένας γραμμικός αλγόριθμος
• Περισσότερα για τη διαδοχή του ακινήτου

ιάλεξη # 12: Χρονική λογική

• Χρονική λογική και αθροιστική κλίμακα
• Προβλήματα ικανοποίησης διαστημάτων
• ιαστήματα προβλήματα σάντουιτς και ISAT
• Ένας γραμμικός αλγόριθμος χρόνου για το ISAT ($ \ Delta _1} $)
• Εύρος ζώνης, εύρος διαδρομής και σωστό εύρος διαδρομής

Link to original soufrce: http://www.math.tau.ac.il/~rshamir/atga/atga.html