Athens University Economics and Business (AUEB)
Scheduling in computer and communication systems and generalized graph coloring problems
Abstract
dc:descriptionThe 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- Χρωματισμός γράφων
- ΝΡ-πληρότητα
- Πολυωνυμικοί και προσεγγιστικοί αλγόριθμοι
- Αλγόριθμοι γράφων
- Χρονοπρογραμματισμός
- Graph coloring
- NP-complete
- Polynomial and approximation algorithms
- Graph algorithms
- Scheduling
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/23538