Title: Maximum Independent Set of A Permutation Graph in $k$ Tracks*
D. T. Lee and Majid Sarrafzadeh
Department of Electrical Engineering and Computer Science
Northwestern University
Evanston, IL 60208
* Supported in part by the National Science Foundation
under grants CCR-8901815 and MIP-8921540.
Abstract:
A maximum weighted independent set of a permutation graph is a maximum
subset of noncrossing chords in a matching diagram (i.e., a set
$\Phi$ of chords with end-points on two horizontal lines). The
problem of finding, among all noncrossing subsets of $\Phi$ with
density at most $k$, one with maximum size is considered, where the
density of a subset is the maximum number of chords crossing a
vertical line and $k$ is a given parameter. A $\Theta (n\log n)$
time and $\Theta (n)$ space algorithm, for solving the problem with
$n$ chords, is proposed. As an application, we solve the problem of
finding, among all proper subsets with density at most $k$ of an
interval graph, one with maximum number of intervals.
Keywords: Permutation graphs, maximum independent set, maximum
chain, track assignment, plane sweep technique.
Int'l J. Comput. Geometry & Applications, (3,3) Sept. 1993, 291-304.