Author Publications

2012

Bonsma, P.S. and Broersma, H.J. and Patel, Viresh and Pyatkin, A.V. (2012) The complexity of finding uniform sparsest cuts in various graph classes. Journal of Discrete Algorithms, 14 . pp. 136-149. ISSN 1570-8667

2011

Bonsma, Paul and Broersma, Hajo and Patel, Viresh and Pyatkin, Artem (2011) The complexity status of problems related to sparsest cuts. In: 21st International Workshop on Combinatorial Algorithms, IWOCA 2010, 26-28 July 2010, London, UK.

2009

Bonsma, Paul (2009) The complexity of the matching-cut problem for planar graphs and other graph classes. Journal of Graph Theory, 62 (2). pp. 109-126. ISSN 0364-9024

2007

Bonsma, Paul S. (2007) Linear time algorithms for finding sparsest cuts in various graph classes. Electronic Notes in Discrete Mathematics, 28 . pp. 265-272. ISSN 1571-0653

2006

Bonsma, P. and Epping, Th. and Hochstättler, W. (2006) Complexity results on restricted instances of a paint shop problem for words. Discrete Applied Mathematics, 154 (9). pp. 1335-1343. ISSN 0166-218X

Bonsma, P.S. (2006) Spanning trees with many leaves: new extremal results and an improved FPT algorithm. [Report]

Bonsma, Paul Simon (2006) Sparse cuts, matching-cuts and leafy trees in graphs. thesis.

2005

Bonsma, P.S. (2005) A characterization of extremal graphs without matching-cuts. [Report]

Bonsma, Paul (2005) A characterization of extremal graphs with no matching-cut. In: European Conference on Combinatorics, Graph Theory and Applications, EuroComb '05, September 5-9, 2009, Berlin, Germany.

2004

Bonsma, Paul (2004) Sparsest cuts and concurrent flows in product graphs. Discrete Applied Mathematics, 136 (2-3). pp. 173-182. ISSN 0166-218X

2003

Bonsma, P.S. (2003) Complexity results for restricted instances of a paint shop problem. [Report]

Bonsma, Paul (2003) The Complexity of the Matching-Cut Problem for Planar Graphs and Other Graph Classes (Extended Abstract). In: 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG, June 19-21, 2003, Elspeet, The Netherlands.

Bonsma, Paul and Brueggemann, Tobias and Woeginger, Gerhard J. (2003) A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves. In: 28th International Symposium on Mathematical Foundations of Computer Science, MFCS, August 25-29, 2003, Bratislava, Slovakia.

2002

Bonsma, P.S. (2002) The complexity of the matching-cut problem for planar graphs and other graph classes. [Report]

Bonsma, Paul and Ueffing, Nicola and Volkmann, Lutz (2002) Edge-cuts leaving components of order at least three. Discrete Mathematics, 256 (1-2). pp. 431-439. ISSN 0012-365X