×
Author ID: bonsma.paul-s Recent zbMATH articles by "Bonsma, Paul S."
Published as: Bonsma, Paul; Bonsma, Paul S.; Bonsma, P.
External Links: MGP
Documents Indexed: 45 Publications since 2002
Co-Authors: 31 Co-Authors with 29 Joint Publications
1,410 Co-Co-Authors

Publications by Year

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 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

Citations by Year