English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Report

The mutual exclusion scheduling problem for permutation and comparability graphs

MPS-Authors
/persons/resource/persons44695

Jansen,  Klaus
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

MPI-I-98-1-005.pdf
(Any fulltext), 182KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Jansen, K.(1998). The mutual exclusion scheduling problem for permutation and comparability graphs (MPI-I-1998-1-005). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-7BE5-E
Abstract
In this paper, we consider the mutual exclusion scheduling problem for comparability graphs. Given an undirected graph $G$ and a fixed constant $m$, the problem is to find a minimum coloring of $G$ such that each color is used at most $m$ times. The complexity of this problem for comparability graphs was mentioned as an open problem by M\"ohring (1985) and for permutation graphs (a subclass of comparability graphs) as an open problem by Lonc (1991). We prove that this problem is already NP-complete for permutation graphs and for each fixed constant $m \ge 6$.