Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  b-Coloring Parameterized by Pathwidth is XNLP-complete

Jaffke, L., Lima, P. T., & Sharma, R. (2022). b-Coloring Parameterized by Pathwidth is XNLP-complete. Retrieved from https://arxiv.org/abs/2209.07772.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/21.11116/0000-000C-1E7E-7 Versions-Permalink: https://hdl.handle.net/21.11116/0000-000C-1E7F-6
Genre: Forschungspapier
Latex : $b$-Coloring Parameterized by Pathwidth is {XNLP}-complete

Dateien

einblenden: Dateien
ausblenden: Dateien
:
arXiv:2209.07772.pdf (Preprint), 433KB
Öffnen   Speichern
Datei-Permalink:
https://hdl.handle.net/21.11116/0000-000C-1E80-2
Name:
arXiv:2209.07772.pdf
Beschreibung:
File downloaded from arXiv at 2023-01-04 10:04
OA-Status:
Grün
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Öffnen
Copyright Datum:
-
Copyright Info:
-
Lizenz:
http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Jaffke, Lars1, Autor
Lima, Paloma T.1, Autor
Sharma, Roohani2, Autor           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS
 Zusammenfassung: We show that the $b$-Coloring problem is complete for the class XNLP when
parameterized by the pathwidth of the input graph. Besides determining the
precise parameterized complexity of this problem, this implies that b-Coloring
parameterized by pathwidth is $W[t]$-hard for all $t$, and resolves the
parameterized complexity of $b$-Coloring parameterized by treewidth.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2022-09-162022
 Publikationsstatus: Online veröffentlicht
 Seiten: 7 p.
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: arXiv: 2209.07772
BibTex Citekey: Jaffke2209.07772
URI: https://arxiv.org/abs/2209.07772
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: