tr-announce May 2008

tr-announce@lists.rwth-aachen.de

1 participants
3 discussions

2008-10: Preemptive Scheduling of Equal-Length Jobs in Polynomial Time

by Peter Schneider-Kamp

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}})$.

16 years, 4 months

2008-09: An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs

by Peter Schneider-Kamp

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.

16 years, 4 months

2008-08: The $\lambda$-cluster Problem on Parameterized Interval Graphs

by Peter Schneider-Kamp

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.

16 years, 4 months

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

tr-announce May 2008