The mutual exclusion scheduling problem for permutation and comparability graphs

Jansen, Klaus

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

報告書

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

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

MPI-I-98-1-005.pdf
(全文テキスト（全般）), 182KB

付随資料 (公開)

There is no public supplementary material available

引用

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.

引用: https://hdl.handle.net/11858/00-001M-0000-0014-7BE5-E

要旨

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