Προσεγγιστικά σχήματα, κλίκες, χρώματα και πυκνότεροι υπογράφοι

Abstract

In this thesis we study the problem of finding the densest k-subgraph of a given graph G = (V, E). We present algorithms of polynomial time as well as approximation results on special graph classes. Analytically, in the thesis we study polynomial time algorithms for the densest k-subgraph problem on weighted graphs of maximal degree two, on weighted trees even if the solution is disconnected, and on interval graphs with intersection only between two consecutive cliques. Moreover, we present a polynomial time approximation scheme for the densest k-subgraph problem on stars of cliques and a polynomial time algorithm on trees of cliques of bounded degree. Finally, in the last part of the thesis we analyze a constant-factor approximation algorithm for the densest k-subgraph problem on chordal graphs.

Σε αυτήν τη διατριβή μελετάμε το πρόβλημα του πυκνότερου k-υπογράψου ενός δοθέντος γράφου G = (V, Ε). Παρουσιάζονται αλγόριθμοι πολυωνυμικού χρόνου καθώς και κάποια προσεγγιστικά αποτελέσματα σε ειδικές κατηγορίες γράφων. Αναλυτικότερα, στη διατριβή παρουσιάζονται αλγόριθμοι πολυωνυμικού χρόνου για το πρόβλημα του πυκνότερου k-υπογράφου σε βεβαρημένους γράφους με μέγιστο βαθμό δύο, δέντρα με βάρη όπου η λύση δεν είναι απαραίτητα συνεκτική, καθώς και σε γράφους διαστημάτων με τομή μόνο ανά δύο διαδοχικές κλίκες. Επιπλέον, παρουσιάζεται ένα πολυωνυμικού χρόνου προσεγγιστικό σχήμα για το πρόβλημα του πυκνότερου k-υπογράψου σε αστέρι κλικών καθώς και ένας πολυωνυμικού χρόνου αλγόριθμος σε δέντρο κλικών φραγμένου βαθμού. Στο τελευταίο μέρος της διατριβής αναλύεται ένας σταθερού λόγου προσεγγιστικός αλγόριθμος για το πρόβλημα του πυκνότερου k-υπογράφου στους χορδικούς γράφους.