Back to search

National and Kapodistrian University of Athens

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

Abstract

dc:description

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.

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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/23425

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Liazi, Maria; Λιάζη, Μαρία. Προσεγγιστικά σχήματα, κλίκες, χρώματα και πυκνότεροι υπογράφοι. National and Kapodistrian University of Athens, 2008. http://hdl.handle.net/10442/hedi/23425