May 2008 - tr-announce - lists.rwth-aachen.de

2008-10: Preemptive Scheduling of Equal-Length Jobs in Polynomial Time
by Peter Schneider-Kamp 07 May '08

07 May '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: Preemptive Scheduling of Equal-Length Jobs in Polynomial Time George B. Mertzios, Walter Unger AIB 2008-10 We study the preemptive scheduling problem of a set of $n$ jobs with release times and equal processing time on a single machine. The objective is to minimize the sum of the weighted completion times $\sum_{i=1}^{n}w_{i}C_{i}$ of the jobs, where the number $k$ of different weights is constant. We provide for this problem a first polynomial algorithm with runtime $O(\frac{n^{k+8}}{k^{k}})$.

1 0

2008-09: An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs
by Peter Schneider-Kamp 07 May '08

07 May '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs George B. Mertzios, Walter Unger AIB 2008-09 In this paper we consider the $k$-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a proper interval graph $G$ and a particular set $T$ of $k$ vertices, the goal is to compute a path cover of $G$ with minimum cardinality, such that the vertices of $T$ are endpoints of these paths. We propose an optimal algorithm for this problem with runtime $O(n)$, where $n$ is the number of intervals in $G$. This algorithm is based on the \emph{Stair Normal Interval Representation (SNIR) matrix} of proper interval graphs.

1 0

2008-08: The $\lambda$-cluster Problem on Parameterized Interval Graphs
by Peter Schneider-Kamp 07 May '08

07 May '08

The following technical report is available from http://aib.informatik.rwth-aachen.de: The $\lambda$-cluster Problem on Parameterized Interval Graphs George B. Mertzios, Stavros D. Nikolopoulos AIB 2008-08 This paper is concerned with the problem of finding, for a given graph $G$ and a given natural number $\lambda$, a subgraph of $G$ on $\lambda$ vertices with a maximum number of edges. The problem is known as the $\lambda$-cluster problem and is NP-hard on general graphs; it remains NP-hard even when restricted to specific graph classes such as comparability, bipartite, chordal graphs, while it is polynomially solvable on the class of interval graphs. Here, we are interested in investigating how the $\lambda$-cluster problem behaves on input graphs that are ``close'' to interval graphs. For this purpose, we consider the class of modified interval graphs, denoted by interval$\pm ke$, which is the class of graphs obtained from interval graphs by adding at most $k_1$ edges and deleting at most $k_2$ edges, where $k=k_1+k_2$. We show that the $\lambda$-cluster problem is fixed-parameter tractable (FPT) with parameter $k$ on interval$\pm ke$ graphs. In particular, we present a dynamic programming algorithm which computes a $\lambda$-cluster of an $n$-vertex interval$\pm ke$ graph in $O(2^{k_1+2k_2} \cdot n \lambda6)$ time, where $k=k_1+k_2$. Our results imply that the $\lambda$-cluster problem is also FPT on both interval$+ke$ and interval$-ke$ classes of graphs with complexity $O(2^{k} \cdot n \lambda6)$ and $O(2^{2k} \cdot n \lambda6)$ respectively.

1 0