Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 30, 2006, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Andreas Weissl
We consider the following tree-like graph structures which appear frequently in applications in mathematics, physics, and bioinformatics: a cactus graph is a graph in which each edge is contained in at most one cycle; a block graph is a graph in which each maximal biconnected block is a clique.
Using generating function techniques and probabilistic arguments, we derive properties of random cactus and random block graphs on n nodes that hold with probability approaching 1 as n tends to infinity. For instance we show upper bounds on the maximum node degree, maximum cycle length, and maximum clique size, respectively. Using the Boltzmann sampler framework of Duchon et al. we provide an expected linear time approximate-size and a quadratic time exact-size sampler for both graph classes.
Automatic MiSe System Software Version 1.4803M | admin login