Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  The mutual exclusion scheduling problem for permutation and comparability graphs

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.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-7BE5-E Versions-Permalink: https://hdl.handle.net/21.11116/0000-0001-733F-8
Genre: Bericht

Dateien

einblenden: Dateien
ausblenden: Dateien
:
MPI-I-98-1-005.pdf (beliebiger Volltext), 182KB
Öffnen   Speichern
Datei-Permalink:
https://hdl.handle.net/21.11116/0000-0001-7340-5
Name:
MPI-I-98-1-005.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Öffnen
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Jansen, Klaus1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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$.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 1998
 Publikationsstatus: Erschienen
 Seiten: 12 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Max-Planck-Institut für Informatik
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: Reportnr.: MPI-I-1998-1-005
BibTex Citekey: Jansen98-1-005
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Research Report / Max-Planck-Institut für Informatik
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: - Identifikator: -