8 citations · 15 across the 7 of their papers we have counts for
4 papers · 1 filter
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…
Graph Isomorphism, Color Refinement, and Compactness
V. Arvind, Johannes Köbler, Gaurav Rattan +1
Color refinement is a classical technique used to show that two given graphs G and H are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a…
On the Complexity of Noncommutative Polynomial Factorization
V. Arvind, Pushkar S Joglekar, Gaurav Rattan
In this paper we study the complexity of factorization of polynomials in the free noncommutative ring of polynomials over the field $\m…
Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity
Vikraman Arvind, Gaurav Rattan
We give a time isomorphism testing algorithm for graphs of eigenvalue multiplicity bounded by which improves on the previous best running time bound of $O^*(2^{…