National and Kapodistrian University of Athens
Προσεγγιστικά σχήματα, κλίκες, χρώματα και πυκνότεροι υπογράφοι
Abstract
dc:descriptionIn 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.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2008
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Liazi, Maria
- Λιάζη, Μαρία
Subjects
dc:subject × 14- πυκνότερος k-υπογράφος
- Πολυωνυμικού χρόνου αλγόριθμοι
- Προσεγγιστικοί αλγόριθμοι
- Πολυωνυμικού χρόνου προσεγγιστικό σχήμα
- Χονδρικοί γράφοι
- Densest k-subgraph
- Polynomial time algorithms
- Approximation algorithms
- Polynomial time approximation scheme
- Chordal graphs
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/23425