Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization

Laszlo Egri , Daniel Marx , Paweł Rzążewski

Abstract

W pracy rozważamy złożoność problemu znajdowania listowego homomorfizmu z grafu G w graf H, parametryzowaną szerokością drzewową grafu G. Przedstawiamy dokładne oszacowanie takiej złożoności w przypadku, gdy H jest grafem z pętlą na każdym wierzchołku.
Author Laszlo Egri - [Indiana State University]
Laszlo Egri,,
-
-
, Daniel Marx - [Computer and Automation Research Institute Hungarian Academy of Sciences]
Daniel Marx,,
-
-
, Paweł Rzążewski (FMIS / DIPS)
Paweł Rzążewski,,
- Department of Information Processing Systems
Journal seriesLeibniz International Proceedings in Informatics, ISSN 1868-8969, (0 pkt)
Issue year2018
Vol96
Pages27_1-27_15
Publication size in sheets0.3
Conference35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018), 28-02-2018 - 03-03-2018, Caen, Francja
Keywords in Polishhomomorfizm, szerokość drzewowa, SETH
Keywords in Englishhomomorphism, treewidth, SETH
DOIDOI:10.4230/LIPIcs.STACS.2018.27
URL http://drops.dagstuhl.de/opus/volltexte/2018/8486/pdf/LIPIcs-STACS-2018-27.pdf
Languageen angielski
Score (nominal)15
ScoreMinisterial score = 15.0, 21-05-2019, ArticleFromConference
Ministerial score (2013-2016) = 15.0, 26-04-2019, ArticleFromConference
Publication indicators Scopus Citations = 0
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back