Combinatorial optimization and recognition of graph classes with applications to related models

Mertzios, George B.; Unger, Walter

doi:910014399

Combinatorial optimization and recognition of graph classes with applications to related models = Kombinatorische Optimierung und Erkennung von Graphklassen mit Anwendungen auf verwandte Modelle

Mertzios, George B. (Author)

2009

Verantwortlichkeitsangabevorgelegt von George B. Mertios

ImpressumAachen : Publikationsserver der RWTH Aachen University 2009

UmfangXI, 145 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2009

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Unger, Walter (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2009-11-30

Online
URN: urn:nbn:de:hbz:82-opus-30325
URL: http://publications.rwth-aachen.de/record/51430/files/Mertzios_George.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Kombinatorische Optimierung (Genormte SW) ; Repräsentation (Genormte SW) ; Polynomialzeitalgorithmus (Genormte SW) ; Erkennung (Genormte SW) ; Informatik (frei) ; NP-Vollständigkeit (frei) ; combinatorial optimization (frei) ; representation (frei) ; recognition (frei) ; polynomial algorithm (frei) ; NP-completeness (frei)

Thematische Einordnung (Klassifikation)
DDC: 004
msc: 68Q25 * 68M20 * 05C85 * 05C62 * 68R10

Kurzfassung
In dieser Dissertation beschäftigen wir uns hauptsächlich mit der Struktur einiger Klassen von perfekten Graphen, die weitgehend erforscht sind. Wir nutzen die Struktur dieser Graphenklassen aus, um Lösungen zu einigen offenen Problemen (sowohl positiv als auch negativ) wie auch einige neue Repräsentationsmodelle zu liefern, die den Entwurf neuer effizienter Algorithmen ermöglichen. Insbesondere untersuchen wir als Erstes die Klassen der echten und allgemeinen Intervallgraphen und hauptsächlich Pfadprobleme auf ihnen. Diese Graphklassen sind weit erforscht und in zahlreichen Bereichen und Disziplinen anwendbar wie unter anderen in der Genetik, der Molekulärbiologie, der Arbeitsplanung, dem VLSI Design, der Archäologie und der Psychologie. Wir präsentieren den ersten polynomiellen Algorithmus mit Laufzeit O(n^4) für das Problem des längsten Pfades auf einem Intervallgraphen mit n Knoten; der Komplexitätsstatus dieses Problems war bisher offen. Weiterhin präsentieren wir eine neue Matrix-Charakterisierung der echten und allgemeinen Intervallgraphen, die SNIR- bzw. NIR-Matrix genannt wird. Die gesamte Information so einer Matrix kann in O(n) Platz erfasst werden. Wir stellen die Nützlichkeit dieser kurzgefassten SNIR Matrix der echten Intervallgraphen mit dem Entwurf eines optimalen O(n)-Algorithmus für das Problem der k-fixierten-Endpunkten-Pfadenabdeckung auf echten Intervallgraphen dar. Als nächstes untersuchen wir die Klassen der beschränkten und allgemeinen Toleranzgraphen, die beide Intervall- und Permutationsgraphen in einer natürlichen Weise verallgemeinern. Diese Klassen, die 1982 eingeführt wurden, haben viele Anwendungen unter anderen in der Bioinformatik, der Ressourcenanweisung und der Arbeitsplanung. Wir präsentieren das erste Schnittmodel für Toleranzgraphen, gegeben durch dreidimensionale Parallelepipede. Dieses Schnittmodel ermöglicht den Entwurf effizienter Algorithmen auf Toleranzgraphen. Insbesondere präsentieren wir optimale O(n log n)-Algorithmen für die Probleme der minimalen Färbung und der maximalen Clique, wie auch einen verbesserten O(n^2)-Algorithmus für das Problem der maximalen gewichteten Unabhängigkeitsmenge. Die Erkennungsprobleme beider der beschrankten und allgemeinen Toleranzgraphen waren die fundamentalste Probleme auf diese Klassen seit ihrer Einführung. Wir beweisen, dass beide Erkennungsprobleme NP-vollständig sind. Diese Resultate sind überraschend, da erwartet wurde, dass die Erkennung dieser Klassen polynomiell wäre. Abschließend untersuchen wir ein Arbeitsplanungsmodel, das nah verwandt mit dem Konzept der Intervall- und Toleranzgraphen ist. Dabei betrachten wir die unterbrechbare Arbeitsplanung gewichteter Arbeiten mit gleicher Bearbeitungszeit und verschiedenen Freigabezeiten auf einer Maschine. Unser Ziel ist, eine Arbeitsplanung zu finden, die die gewichtete Summe der Abgabezeiten minimiert. Der Komplexitätsstatus dieses Problems ist offen. Wir präsentieren den ersten polynomiellen Algorithmus, unter der Annahme dass die Anzahl der unterschiedlichen Gewichte konstant ist.

This thesis mainly deals with the structure of some classes of perfect graphs that have been widely investigated, due to both their interesting structure and their numerous applications. By exploiting the structure of these graph classes, we provide solutions to some open problems on them (in both the affirmative and negative), along with some new representation models that enable the design of new efficient algorithms. In particular, we first investigate the classes of interval and proper interval graphs, and especially, path problems on them. These classes of graphs have been extensively studied and they find many applications in several fields and disciplines such as genetics, molecular biology, scheduling, VLSI design, archaeology, and psychology, among others. Although the Hamiltonian path problem is well known to be linearly solvable on interval graphs, the complexity status of the longest path problem, which is the most natural optimization version of the Hamiltonian path problem, was an open question. We present the first polynomial algorithm for this problem with running time O(n^4). Furthermore, we introduce a matrix representation for both interval and proper interval graphs, called the Normal Interval Representation (NIR) and the Stair Normal Interval Representation (SNIR) matrix, respectively. The whole information of both NIR and SNIR matrices for a graph with n vertices can be captured in O(n) space. We illustrate the use of this succinct matrix representation (SNIR) for proper interval graphs to solve in optimal O(n) time the k-fixed-endpoint path cover problem, which is another optimization variant of the Hamiltonian path problem. Next, we investigate the classes of tolerance and bounded tolerance graphs, which generalize in a natural way both interval and permutation graphs. This class of graphs has attracted many research efforts since its introduction by Golumbic and Monma in 1982, as it finds many important applications in bioinformatics, constrained-based temporal reasoning, resource allocation, and scheduling, among others. We present the first non-trivial intersection model for tolerance graphs, given by three-dimensional parallelepipeds. Apart of being important on its own, this new intersection model enables the design of efficient algorithms on tolerance graphs. Namely, given a tolerance graph G with n vertices, we present optimal O(n log n) time algorithms for the minimum coloring and the maximum clique problems, as well as an improved O(n^2) time algorithm for the maximum weighted independent set problem on G. In spite of the extensive study of these classes, the recognition of both tolerance and bounded tolerance graphs have been the most fundamental open problems since their introduction. Therefore, all existing efficient algorithms assumed that the input graph is given along with a tolerance or a bounded tolerance representation, respectively. We prove that both recognition problems are NP-complete, thereby settling a long standing open question. These hardness results are surprising, since it was expected that the recognition of these graph classes is polynomial. Finally, we investigate a scheduling model, which is closely related to the concept of interval and tolerance graphs. Namely, we deal with the scheduling of weighted jobs with release times and with equal processing time each on a single machine. In our model, the scheduling of the jobs is preemptive, i.e. the processing of a job can be interrupted by another one. Our goal is to find a schedule of the given jobs with the minimum weighted sum of completion times. The complexity status of this problem has been stated as an open question. We present for this problem the first polynomial algorithm for the case where the number of different weights of the jobs is constant.

Fulltext:
PDF