24 citations · 124 across the 75 of their papers we have counts for
4 papers · 1 filter
Backdoors to Tractable Valued CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
We extend the notion of a strong backdoor from the CSP setting to the Valued CSP setting (VCSP, for short). This provides a means for augmenting a class of tractable VCSP instances…
Combining Treewidth and Backdoors for CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
We show that CSP is fixed-parameter tractable when parameterized by the treewidth of a backdoor into any tractable CSP problem over a finite constraint language. This result combin…
A single-exponential fixed-parameter algorithm for Distance-Hereditary Vertex Deletion
Eduard Eiben, Robert Ganian, O-joung Kwon
Vertex deletion problems ask whether it is possible to delete at most vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years,…
Faster Algorithms for the Maximum Common Subtree Isomorphism Problem
Andre Droschinsky, Nils M. Kriege, Petra Mutzel
The maximum common subtree isomorphism problem asks for the largest possible isomorphism between subtrees of two given input trees. This problem is a natural restriction of the max…