4 citations · 9 across the 4 of their papers we have counts for
4 papers · 1 filter
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
V. Arvind, Johannes Köbler, Sebastian Kuhnert +1
Lubiw showed that several variants of Graph Isomorphism are NP-complete, where the solutions are required to satisfy certain additional constraints [SICOMP 10, 1981]. One of these,…
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs
V. Arvind, Frank Fuhlbrück, Johannes Köbler +2
In this paper we study the complexity of the following problems: Given a colored graph X=(V,E,c), compute a minimum cardinality set S of vertices such that no nontrivial automorphi…
On the Isomorphism Problem for Helly Circular-Arc Graphs
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the…
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where `canonical' means that models of isomorphic graphs are e…