Welcome
Our group's interests in both research and teaching are in various areas within the theory of computation, among them logic, complexity theory, algorithms, and automata theory, and especially the numerous connections between these areas.
Computer Science 7 is part of the Computer Science Department within the Faculty of Mathematics, Computer Science and Natural Sciences. There is a close collaboration with the Mathematical Foundations of Computer Science group.
News
Monday, 14.08.2017
11:00

12:00
Fixing sets are a way to break symmetries and determine automorphisms of a graph. The fixing number of a graph G is the smallest
cardinality of a set of vertices S such that only the trivial automorphism of G fixes every vertex in S. In this talk I present
an algorithm for computing the fixing number of a planar graph by decomposing it into its triconnected components and by using
bottomup recursion upon these components. For this to work I introduce a generalization of the fixing number, the socalled
vertexarc fixing number: in addition to vertices, the fixing set may also contain edges and arcs of the graph. The provided
algorithm can be applied to any minorclosed graph class that allows isomorphism testing and computing the vertexarc fixing
number of its triconnected graphs in polynomial time.