Edit Profile (opens in new tab) Bonsma, Paul S. Co-Author Distance Author ID: bonsma.paul-s Published as: Bonsma, Paul; Bonsma, Paul S.; Bonsma, P. more...less External Links: MGP Documents Indexed: 45 Publications since 2002 Co-Authors: 31 Co-Authors with 29 Joint Publications 1,410 Co-Co-Authors all top 5 Co-Authors 16 single-authored 4 Zickfeld, Florian 3 Breuer, Felix 3 Cereceda, Luis 2 Berkholz, Christoph 2 Broersma, Hajo J. 2 Dorn, Frederic 2 Grohe, Martin 2 Lokshtanov, Daniel 2 Patel, Viresh 2 Paulusma, Daniël 2 Pyatkin, Artëm Valer’evich 2 Schulz, Jens 2 Wiese, Andreas 1 Bodlaender, Hans L. 1 Brüggemann, Tobias 1 Epping, Thomas 1 Farley, Arthur M. 1 Hochstättler, Winfried 1 Johnson, Matthew 1 Kamiński, Marcin Marek 1 Lowski, Stefanie 1 Mouawad, Amer E. 1 Nishimura, Naomi 1 Proskurowski, Andrzej 1 Raman, Venkatesh 1 Solis-Oba, Roberto 1 Ueffing, Nicola 1 van den Heuvel, Jan 1 Volkmann, Lutz 1 Woeginger, Gerhard 1 Wrochna, Marcin all top 5 Serials 4 Discrete Applied Mathematics 3 Journal of Graph Theory 2 Discrete Mathematics 2 Theoretical Computer Science 2 Algorithmica 2 SIAM Journal on Discrete Mathematics 2 Journal of Discrete Algorithms 1 Acta Informatica 1 SIAM Journal on Computing 1 Theory of Computing Systems 1 ACM Transactions on Algorithms Fields 42 Combinatorics (05-XX) 35 Computer science (68-XX) 9 Operations research, mathematical programming (90-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 43 Publications have been cited 503 times in 353 Documents Cited by ▼ Year ▼ Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Zbl 1177.05112 Bonsma, Paul; Cereceda, Luis 81 2009 Edge-cuts leaving components of order at least three. Zbl 1017.05063 Bonsma, Paul; Ueffing, Nicola; Volkmann, Lutz 57 2002 Reconfiguring independent sets in claw-free graphs. Zbl 1417.05199 Bonsma, Paul; Kamiński, Marcin; Wrochna, Marcin 33 2014 The complexity of bounded length graph recoloring and CSP reconfiguration. Zbl 1456.68065 Bonsma, Paul; Mouawad, Amer E.; Nishimura, Naomi; Raman, Venkatesh 26 2014 The complexity of the matching-cut problem for planar graphs and other graph classes. Zbl 1179.05104 Bonsma, Paul 23 2009 The complexity of rerouting shortest paths. Zbl 1416.68082 Bonsma, Paul 22 2013 A constant factor approximation algorithm for unsplittable flow on paths. Zbl 1292.68162 Bonsma, Paul; Schulz, Jens; Wiese, Andreas 18 2011 Spanning trees with many leaves in graphs with minimum degree three. Zbl 1181.05051 Bonsma, Paul S. 17 2008 Spanning trees with many leaves in graphs without diamonds and blossoms. Zbl 1136.68448 Bonsma, Paul; Zickfeld, Florian 16 2008 Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Zbl 1147.68529 Bonsma, Paul; Cereceda, Luis 16 2007 Independent set reconfiguration in cographs and their generalizations. Zbl 1346.05209 Bonsma, Paul 15 2016 A faster FPT algorithm for finding spanning trees with many leaves. Zbl 1124.68398 Bonsma, Paul S.; Brueggemann, Tobias; Woeginger, Gerhard J. 13 2003 Complexity results on restricted instances of a paint shop problem for words. Zbl 1131.68048 Bonsma, P.; Epping, Th.; Hochstättler, W. 12 2006 A constant-factor approximation algorithm for unsplittable flow on paths. Zbl 1297.68185 Bonsma, Paul; Schulz, Jens; Wiese, Andreas 12 2014 The fine details of fast dynamic programming over tree decompositions. Zbl 1406.68067 Bodlaender, Hans L.; Bonsma, Paul; Lokshtanov, Daniel 10 2013 Max-leaves spanning tree is APX-hard for cubic graphs. Zbl 1246.68121 Bonsma, Paul 9 2012 A 2-approximation algorithm for finding a spanning tree with maximum number of leaves. Zbl 1359.68318 Solis-Oba, Roberto; Bonsma, Paul; Lowski, Stefanie 9 2017 Rerouting shortest paths in planar graphs. Zbl 1354.68110 Bonsma, Paul 8 2012 The complexity of rerouting shortest paths. Zbl 1365.68273 Bonsma, Paul 7 2012 Improved bounds for spanning trees with many leaves. Zbl 1238.05053 Bonsma, Paul; Zickfeld, Florian 7 2012 A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs. Zbl 1202.68274 Bonsma, Paul; Zickfeld, Florian 7 2008 Tight lower and upper bounds for the complexity of canonical colour refinement. Zbl 1362.68097 Berkholz, Christoph; Bonsma, Paul; Grohe, Martin 7 2013 Feedback vertex set in mixed graphs. Zbl 1342.05180 Bonsma, Paul; Lokshtanov, Daniel 6 2011 Using contracted solution graphs for solving reconfiguration problems. Zbl 1398.90188 Bonsma, Paul; Paulusma, Daniël 6 2016 Tight bounds and a fast FPT algorithm for directed max-leaf spanning tree. Zbl 1158.68427 Bonsma, Paul; Dorn, Frederic 6 2008 A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs. Zbl 1237.05041 Bonsma, Paul; Zickfeld, Florian 5 2011 Sparsest cuts and concurrent flows in product graphs. Zbl 1036.90023 Bonsma, Paul 5 2004 Tight lower and upper bounds for the complexity of canonical colour refinement. Zbl 1368.68219 Berkholz, Christoph; Bonsma, Paul; Grohe, Martin 5 2017 Independent set reconfiguration in cographs. Zbl 1417.05149 Bonsma, Paul 5 2014 Finding paths between graph colourings: Computational complexity and possible distances. Zbl 1341.05063 Bonsma, Paul; Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew 4 2007 Finding fullerene patches in polynomial time. Zbl 1272.05189 Bonsma, Paul; Breuer, Felix 4 2009 Tight bounds and a fast FPT algorithm for directed MAX-leaf spanning tree. Zbl 1295.05223 Bonsma, Paul; Dorn, Frederic 4 2011 Rerouting shortest paths in planar graphs. Zbl 1369.05041 Bonsma, Paul 4 2017 Linear time algorithms for finding sparsest cuts in various graph classes. Zbl 1293.05364 Bonsma, Paul S. 3 2007 Surface split decompositions and subgraph isomorphism in graphs on surfaces. Zbl 1244.05214 Bonsma, Paul 3 2012 The complexity of finding uniform sparsest cuts in various graph classes. Zbl 1248.05208 Bonsma, Paul; Broersma, Hajo; Patel, Viresh; Pyatkin, Artem 3 2012 The complexity status of problems related to sparsest cuts. Zbl 1326.68145 Bonsma, Paul; Broersma, Hajo; Patel, Viresh; Pyatkin, Artem 3 2011 The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract). Zbl 1255.05146 Bonsma, Paul 3 2003 Extremal graphs having no matching cuts. Zbl 1234.05127 Bonsma, Paul; Farley, Arthur M.; Proskurowski, Andrzej 2 2012 Counting hexagonal patches and independent sets in circle graphs. Zbl 1239.05093 Bonsma, Paul; Breuer, Felix 2 2012 Most balanced minimum cuts. Zbl 1226.05142 Bonsma, Paul 2 2010 Using contracted solution graphs for solving reconfiguration problems. Zbl 1431.90161 Bonsma, Paul; Paulusma, Daniël 2 2019 A characterization of extremal graphs with no matching-cut. Zbl 1192.05075 Bonsma, Paul 1 2005 Using contracted solution graphs for solving reconfiguration problems. Zbl 1431.90161 Bonsma, Paul; Paulusma, Daniël 2 2019 A 2-approximation algorithm for finding a spanning tree with maximum number of leaves. Zbl 1359.68318 Solis-Oba, Roberto; Bonsma, Paul; Lowski, Stefanie 9 2017 Tight lower and upper bounds for the complexity of canonical colour refinement. Zbl 1368.68219 Berkholz, Christoph; Bonsma, Paul; Grohe, Martin 5 2017 Rerouting shortest paths in planar graphs. Zbl 1369.05041 Bonsma, Paul 4 2017 Independent set reconfiguration in cographs and their generalizations. Zbl 1346.05209 Bonsma, Paul 15 2016 Using contracted solution graphs for solving reconfiguration problems. Zbl 1398.90188 Bonsma, Paul; Paulusma, Daniël 6 2016 Reconfiguring independent sets in claw-free graphs. Zbl 1417.05199 Bonsma, Paul; Kamiński, Marcin; Wrochna, Marcin 33 2014 The complexity of bounded length graph recoloring and CSP reconfiguration. Zbl 1456.68065 Bonsma, Paul; Mouawad, Amer E.; Nishimura, Naomi; Raman, Venkatesh 26 2014 A constant-factor approximation algorithm for unsplittable flow on paths. Zbl 1297.68185 Bonsma, Paul; Schulz, Jens; Wiese, Andreas 12 2014 Independent set reconfiguration in cographs. Zbl 1417.05149 Bonsma, Paul 5 2014 The complexity of rerouting shortest paths. Zbl 1416.68082 Bonsma, Paul 22 2013 The fine details of fast dynamic programming over tree decompositions. Zbl 1406.68067 Bodlaender, Hans L.; Bonsma, Paul; Lokshtanov, Daniel 10 2013 Tight lower and upper bounds for the complexity of canonical colour refinement. Zbl 1362.68097 Berkholz, Christoph; Bonsma, Paul; Grohe, Martin 7 2013 Max-leaves spanning tree is APX-hard for cubic graphs. Zbl 1246.68121 Bonsma, Paul 9 2012 Rerouting shortest paths in planar graphs. Zbl 1354.68110 Bonsma, Paul 8 2012 The complexity of rerouting shortest paths. Zbl 1365.68273 Bonsma, Paul 7 2012 Improved bounds for spanning trees with many leaves. Zbl 1238.05053 Bonsma, Paul; Zickfeld, Florian 7 2012 Surface split decompositions and subgraph isomorphism in graphs on surfaces. Zbl 1244.05214 Bonsma, Paul 3 2012 The complexity of finding uniform sparsest cuts in various graph classes. Zbl 1248.05208 Bonsma, Paul; Broersma, Hajo; Patel, Viresh; Pyatkin, Artem 3 2012 Extremal graphs having no matching cuts. Zbl 1234.05127 Bonsma, Paul; Farley, Arthur M.; Proskurowski, Andrzej 2 2012 Counting hexagonal patches and independent sets in circle graphs. Zbl 1239.05093 Bonsma, Paul; Breuer, Felix 2 2012 A constant factor approximation algorithm for unsplittable flow on paths. Zbl 1292.68162 Bonsma, Paul; Schulz, Jens; Wiese, Andreas 18 2011 Feedback vertex set in mixed graphs. Zbl 1342.05180 Bonsma, Paul; Lokshtanov, Daniel 6 2011 A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs. Zbl 1237.05041 Bonsma, Paul; Zickfeld, Florian 5 2011 Tight bounds and a fast FPT algorithm for directed MAX-leaf spanning tree. Zbl 1295.05223 Bonsma, Paul; Dorn, Frederic 4 2011 The complexity status of problems related to sparsest cuts. Zbl 1326.68145 Bonsma, Paul; Broersma, Hajo; Patel, Viresh; Pyatkin, Artem 3 2011 Most balanced minimum cuts. Zbl 1226.05142 Bonsma, Paul 2 2010 Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Zbl 1177.05112 Bonsma, Paul; Cereceda, Luis 81 2009 The complexity of the matching-cut problem for planar graphs and other graph classes. Zbl 1179.05104 Bonsma, Paul 23 2009 Finding fullerene patches in polynomial time. Zbl 1272.05189 Bonsma, Paul; Breuer, Felix 4 2009 Spanning trees with many leaves in graphs with minimum degree three. Zbl 1181.05051 Bonsma, Paul S. 17 2008 Spanning trees with many leaves in graphs without diamonds and blossoms. Zbl 1136.68448 Bonsma, Paul; Zickfeld, Florian 16 2008 A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs. Zbl 1202.68274 Bonsma, Paul; Zickfeld, Florian 7 2008 Tight bounds and a fast FPT algorithm for directed max-leaf spanning tree. Zbl 1158.68427 Bonsma, Paul; Dorn, Frederic 6 2008 Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Zbl 1147.68529 Bonsma, Paul; Cereceda, Luis 16 2007 Finding paths between graph colourings: Computational complexity and possible distances. Zbl 1341.05063 Bonsma, Paul; Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew 4 2007 Linear time algorithms for finding sparsest cuts in various graph classes. Zbl 1293.05364 Bonsma, Paul S. 3 2007 Complexity results on restricted instances of a paint shop problem for words. Zbl 1131.68048 Bonsma, P.; Epping, Th.; Hochstättler, W. 12 2006 A characterization of extremal graphs with no matching-cut. Zbl 1192.05075 Bonsma, Paul 1 2005 Sparsest cuts and concurrent flows in product graphs. Zbl 1036.90023 Bonsma, Paul 5 2004 A faster FPT algorithm for finding spanning trees with many leaves. Zbl 1124.68398 Bonsma, Paul S.; Brueggemann, Tobias; Woeginger, Gerhard J. 13 2003 The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract). Zbl 1255.05146 Bonsma, Paul 3 2003 Edge-cuts leaving components of order at least three. Zbl 1017.05063 Bonsma, Paul; Ueffing, Nicola; Volkmann, Lutz 57 2002 all cited Publications top 5 cited Publications all top 5 Cited by 522 Authors 29 Ito, Takehiro 16 Bonsma, Paul S. 15 Bousquet, Nicolas 14 Suzuki, Akira 13 Mouawad, Amer E. 12 Paulusma, Daniël 11 Bonamy, Marthe 11 Otachi, Yota 11 Wang, Shiying 11 Zhou, Xiao 10 Johnson, Matthew 9 Feghali, Carl 9 Lê Văn Băng 9 Uehara, Ryuhei 8 Kamiński, Marcin Marek 8 Nishimura, Naomi 8 Zhang, Zhao 7 Bartier, Valentin 7 Demaine, Erik D. 7 Kratsch, Dieter 7 Ono, Hirotaka 7 Volkmann, Lutz 7 Wiese, Andreas 6 Lin, Shangwei 6 Rautenbach, Dieter 5 Brewster, Richard C. 5 Liu, Aixia 5 Mafuta, Phillip 5 Meng, Jixiang 5 Ou, Jianping 5 Patel, Viresh 5 Saurabh, Saket 5 Yuan, Jun 4 Aravind, N. R. 4 Balbuena, Camino 4 Broersma, Hajo J. 4 Gutin, Gregory Z. 4 Haas, Ruth 4 Heinrich, Marc 4 Hoàng Anh Đức 4 Karpov, Dmitriy V. 4 Kim, Eun Jung 4 Kobayashi, Yusuke 4 Lee, Jae-Baek 4 Milanič, Martin 4 Noel, Jonathan Andrew 4 Raman, Venkatesh 4 Rzążewski, Paweł 4 Siggers, Mark H. 4 Wasa, Kunihiro 4 Wrochna, Marcin 3 Belmonte, Rémy 3 Cereceda, Luis 3 Chakaravarthy, Venkatesan T. 3 Chalermsook, Parinya 3 Fernandes, Cristina G. 3 Hanaka, Tesshu 3 Hatanaka, Tatsuhiko 3 Havet, Frédéric 3 Hellwig, Angelika 3 Hsieh, Sun-Yuan 3 Kobayashi, Yasuaki 3 Lampis, Michael 3 Li, Xueliang 3 Lintzmayer, Carla Negri 3 Liu, Qinghai 3 Lokshtanov, Daniel 3 Marcote, Xavier 3 Masařík, Tomáš 3 Medvedev, Paul 3 Meunier, Frédéric 3 Mizuta, Haruka 3 Montejano, Luis Pedro 3 Moore, Benjamin R. 3 Mühlenthaler, Moritz 3 Mukwembi, Simon 3 Mynhardt, Christina Magdalena 3 Okrasa, Karolina 3 Osawa, Hiroki 3 Perarnau, Guillem 3 Sabharwal, Yogish 3 Sau, Ignasi 3 Seyffarth, Karen 3 Siebertz, Sebastian 3 Stacho, Ladislav 3 Tuza, Zsolt 3 van den Heuvel, Jan 3 Yamada, Takeshi 3 Zhang, Heping 3 Zhang, Lei 3 Zhao, Shuang 3 Zickfeld, Florian 2 Adamaszek, Anna 2 Agrawal, Akanksha 2 Alon, Noga 2 Andres, Stephan Dominique 2 Araújo, Júlio César Silva 2 Arvind, Vikraman 2 Asplund, John 2 Bankevich, A. V. ...and 422 more Authors all top 5 Cited in 70 Serials 35 Theoretical Computer Science 29 Discrete Applied Mathematics 25 Discrete Mathematics 21 Algorithmica 10 Journal of Computer and System Sciences 10 European Journal of Combinatorics 10 Journal of Combinatorial Optimization 9 Journal of Graph Theory 8 Information Processing Letters 8 Graphs and Combinatorics 7 Journal of Discrete Algorithms 6 SIAM Journal on Discrete Mathematics 5 Applied Mathematics and Computation 5 Journal of Mathematical Sciences (New York) 4 SIAM Journal on Computing 3 Journal of Combinatorial Theory. Series B 3 Networks 3 European Journal of Operational Research 3 The Australasian Journal of Combinatorics 3 The Electronic Journal of Combinatorics 3 Theory of Computing Systems 3 Journal of Graph Algorithms and Applications 3 Discrete Optimization 3 Logical Methods in Computer Science 2 Artificial Intelligence 2 Quaestiones Mathematicae 2 Computers & Operations Research 2 International Journal of Foundations of Computer Science 2 Mathematical Programming. Series A. Series B 2 Journal of Scheduling 2 Discrete Dynamics in Nature and Society 2 RAIRO. Operations Research 2 Algorithms 2 Science China. Mathematics 1 Acta Informatica 1 Israel Journal of Mathematics 1 Linear and Multilinear Algebra 1 Journal of Applied Probability 1 Journal of Geometry 1 Operations Research Letters 1 Information and Computation 1 Asia-Pacific Journal of Operational Research 1 Applied Mathematics Letters 1 Formal Aspects of Computing 1 Annals of Operations Research 1 Random Structures & Algorithms 1 International Journal of Computer Mathematics 1 Linear Algebra and its Applications 1 Computational Complexity 1 Journal of Algebraic Combinatorics 1 Applied Categorical Structures 1 Applied Mathematics. Series B (English Edition) 1 Combinatorics, Probability and Computing 1 Filomat 1 The Journal of Artificial Intelligence Research (JAIR) 1 Journal of Mathematical Chemistry 1 Mathematical Problems in Engineering 1 Taiwanese Journal of Mathematics 1 Journal of Discrete Mathematical Sciences & Cryptography 1 Fundamenta Informaticae 1 Trudy Instituta Matematiki 1 ACM Journal of Experimental Algorithmics 1 Journal of Statistical Mechanics: Theory and Experiment 1 Parallel Processing Letters 1 Optimization Letters 1 Ars Mathematica Contemporanea 1 ACM Transactions on Algorithms 1 Afrika Matematika 1 Electronic Journal of Graph Theory and Applications 1 CGT. Computing in Geometry and Topology all top 5 Cited in 16 Fields 244 Combinatorics (05-XX) 206 Computer science (68-XX) 58 Operations research, mathematical programming (90-XX) 8 Probability theory and stochastic processes (60-XX) 4 Mathematical logic and foundations (03-XX) 4 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 4 Information and communication theory, circuits (94-XX) 3 Biology and other natural sciences (92-XX) 1 General algebraic systems (08-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Category theory; homological algebra (18-XX) 1 Group theory and generalizations (20-XX) 1 Convex and discrete geometry (52-XX) 1 Algebraic topology (55-XX) 1 Quantum theory (81-XX) 1 Statistical mechanics, structure of matter (82-XX) Citations by Year