Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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

Properties and Sampling of Tree-like Structures with Blocks of Higher Connectivity

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login