13 citations · 26 across the 10 of their papers we have counts for
3 papers · 1 filter
-Coloring Parameterized by Pathwidth is XNLP-complete
Lars Jaffke, Paloma T. Lima, Roohani Sharma
We show that the -Coloring problem is complete for the class XNLP when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexit…
Generalized distance domination problems and their complexity on graphs of bounded mim-width
Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme +1
We generalize the family of -problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as dista…
A note on the complexity of Feedback Vertex Set parameterized by mim-width
Lars Jaffke, O-joung Kwon, Jan Arne Telle
We complement the recent algorithmic result that Feedback Vertex Set is XP-time solvable parameterized by the mim-width of a given branch decomposition of the input graph [3] by sh…