All reports by Author Sebastian Kuhnert:

__
TR16-157
| 13th October 2016
__

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran#### Parameterized Complexity of Small Weight Automorphisms

__
TR14-096
| 29th July 2014
__

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran#### Solving Linear Equations Parameterized by Hamming Weight

__
TR13-074
| 9th May 2013
__

Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky#### Helly Circular-Arc Graph Isomorphism is in Logspace

__
TR12-078
| 14th June 2012
__

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev#### Approximate Graph Isomorphism

__
TR12-032
| 4th April 2012
__

Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe#### Interval graph representation with given interval and intersection lengths

__
TR10-043
| 5th March 2010
__

Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky#### Interval Graphs: Canonical Representation in Logspace

Revisions: 1

__
TR09-053
| 20th May 2009
__

Johannes Köbler, Sebastian Kuhnert#### The Isomorphism Problem for k-Trees is Complete for Logspace

Revisions: 1

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran

We consider the PermCode problem to decide, given a representation of a permutation group G and a parameter k, whether there is a non-trivial element of G with support at most k. This problem generalizes several problems in the literature. We introduce a new method that allows to reduce the ... more >>>

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran

Given a system of linear equations $Ax=b$ over the binary field $\mathbb{F}_2$ and an integer $t\ge 1$, we study the following three algorithmic problems:

1. Does $Ax=b$ have a solution of weight at most $t$?

2. Does $Ax=b$ have a solution of weight exactly $t$?

3. Does $Ax=b$ have a ...
more >>>

Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky

We present logspace algorithms for the canonical labeling problem and the representation problem of Helly circular-arc (HCA) graphs. The first step is a reduction to canonical labeling and representation of interval intersection matrices. In a second step, the Delta trees employed in McConnell's linear time representation algorithm for interval matrices ... more >>>

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev

We study optimization versions of Graph Isomorphism. Given two graphs $G_1,G_2$, we are interested in finding a bijection $\pi$ from $V(G_1)$ to $V(G_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log n)}$ time approximation scheme that for any constant ... more >>>

Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe

We consider the problem of finding interval representations of graphs that additionally respect given interval lengths and/or pairwise intersection lengths, which are represented as weight functions on the vertices and edges, respectively. Pe'er and Shamir proved that the problem is NP-complete if only the former are given [SIAM J. Discr. ... more >>>

Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky

We present a logspace algorithm for computing a canonical interval representation and a canonical labeling of interval graphs. As a consequence, the isomorphism and automorphism problems for interval graphs are solvable in logspace.

more >>>Johannes Köbler, Sebastian Kuhnert

We show that k-tree isomorphism can be decided in logarithmic

space by giving a logspace canonical labeling algorithm. This improves

over the previous StUL upper bound and matches the lower bound. As a

consequence, the isomorphism, the automorphism, as well as the

canonization problem for k-trees ...
more >>>