Philipp Klaus Krause

Teaching

[an error occurred while processing this directive]
WS 2014

Grundlagen der Informationsintegration

SS 2013

Tree Decomposition, Algorithms and Logic

WS 2013

Diskrete Modellierung

SS 2013

Graphstrukturtheorie im Übersetzerbau

WS 2012

Logik und Datenbanken

WS 2011

Baumzerlegungen, Algorithmen und Logik

SS 2011

Kombinatorische Spiele und diskrete Systeme

Übersetzerbau

WS 2010

Graphstruktur, Algorithmen und Logik

Perlen der theoretischen Informatik

SS 2010

Datenstrukturen

WS 2009

Baumzerlegungen, Algorithmen und Logik

SS 2009

Security Aspects of Embedded Systems

Publications

[an error occurred while processing this directive]

Register allocation

AVOS

ftc

Software

[an error occurred while processing this directive]
Graph theory

rank-width and -decomposition

linear nlc-width and -expressions

Programming tools

sdcc

Libraries and tools for the ColecoVision

Computer graphics

DSSIM

Contact

Theorie der Informatik

Isolde Adler

Philipp Klaus Krause

rw

rw is a program that calculates rank-width and rank-decompositions. It is based on ideas from "Computing rank-width exactly" by Sang-il Oum, "Sopra una formula numerica" by Ernesto Pascal, "Generation of a Vector from the Lexicographical Index" by B.P. Buckles and M. Lybanon and "Fast additions on masked integers" by Michael D. Adams and David S. Wise.

On 2009's computers it works quite well up to graph sizes of about 28 nodes.

Assuming that libigraph is installed it can be compiled using e.g. "gcc -O2 --std=c99 -pedantic rw.c simplerw.c -ligraph".

It supports a number of input graph formats; there is an example graph included, for which rank-width and rank-decomposition can be calculated using "./a.out --edgelist igrid".

Download C source