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

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.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2009

Author dc:creator

• Mertzios, George B.

Contributors dc:contributor

• Unger, Walter

• info:eu-repo/classification/ddc/004
• Kombinatorische Optimierung
• Repräsentation
• Polynomialzeitalgorithmus
• Erkennung
• Informatik
• NP-Vollständigkeit
• combinatorial optimization
• representation
• recognition
• polynomial algorithm
• NP-completeness

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-113721%22

OAI record oai:identifier

https://publications.rwth-aachen.de/oai2d?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Apublications.rwth-aachen.de%3A51430