Back to search

Athens University Economics and Business (AUEB)

Scheduling in computer and communication systems and generalized graph coloring problems

Abstract

dc:description

The thesis deals with weighted generalizations of the classical graph coloring problems motivated by scheduling arising in computer and communication systems. The most general problems we attack are called bounded max-vertex/edge-coloring problems and take as input a vertex/edge weighted graph and a bound b. In these problems each color class is of cardinality at most b and of weight equal to that of the heaviest vertex/edge in this class. The objective is to find a proper coloring of the input graph minimizing the sum of all color classes' weights. For unit weights these problems reduce to the known bounded coloring problems, while in the absence of the cardinality bound we get the (unbounded) max-coloring problems. The max-coloring problems have been well motivated and studied in the literature. Max-vertex-coloring problems arise in the management of dedicated memories, organized as buffer pools, which is the case for wireless protocol stacks like GPRS or 3G. Max-edge-coloring problems arise in switch based communication systems like SS/TDMA, where messages are to be transmitted through direct connections established by an underlying network. Moreover, max-coloring problems correspond to scheduling jobs with conflicts in multiprocessor or batch scheduling environments. However, in all practical applications there exist physical constraints on the number of entities (corresponding to vertices/edges of a graph) assigned the same resource (color), which motivate the study of bounded max-coloring problems. In the first part of the thesis we present new complexity and approximation results for several variants of the max-edge-coloring problem with respect to the class of the underlying graph. In particular, we present polynomial algorithms for special graph classes and approximation results for NP-complete variants. For bipartite graphs we present a series of four approximation algorithms; the last of them achieves a 1.74 approximation ratio and improves substantially the known ratio of 2. For trees we give a 3/2-approximation algorithm, two parameterized approximation algorithms and finally a PTAS. We also prove that the problem is NP-complete for complete bi-valued graphs and we present an asymptotic 4/3-approximation algorithm for general bi-valued graphs. In the second part of the thesis we give the first known results for the bounded max-coloring problems. For the bounded max-edge-coloring problem, we prove approximation factors of at most 3 for general and bipartite graphs and 2 for trees. Furthermore, we show that this bounded problem is NP-complete for trees. This is the first complexity result for any max-coloring problem on trees. For the bounded max-vertex-coloring problem we present a generic scheme which becomes a 17/11-approximation algorithm for bipartite graphs, a PTAS for bipartite graphs when b is fixed and also a PTAS for trees even if b is part of the problem's instance

Degree

thesis:*
Grantor dc:publisher
Athens University Economics and Business (AUEB)
Year dc:date
2009

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Lucarelli, Giorgio
  • Λουκαρέλλι, Γεώργιος

Subjects

dc:subject × 14

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/23538

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

Lucarelli, Giorgio; Λουκαρέλλι, Γεώργιος. Scheduling in computer and communication systems and generalized graph coloring problems. Athens University Economics and Business (AUEB), 2009. http://hdl.handle.net/10442/hedi/23538