default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDPaul S. Bonsma
Person information
- affiliation: University of Twente, Faculty of Electrical Engineering, Mathematics and Computer Science
- affiliation: Humboldt University Berlin, Computer Science Department
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2010 – 2019
- 2019
[j24]Paul S. Bonsma, Daniël Paulusma
:
Using contracted solution graphs for solving reconfiguration problems. Acta Informatica 56(7-8): 619-648 (2019)- 2017
- [j23]Roberto Solis-Oba, Paul S. Bonsma, Stefanie Lowski:
A 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves. Algorithmica 77(2): 374-388 (2017) - [j22]Paul S. Bonsma:
Rerouting shortest paths in planar graphs. Discret. Appl. Math. 231: 95-112 (2017) - [j21]Christoph Berkholz, Paul S. Bonsma, Martin Grohe:
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. Theory Comput. Syst. 60(4): 581-614 (2017) - 2016
- [j20]Paul S. Bonsma:
Independent Set Reconfiguration in Cographs and their Generalizations. J. Graph Theory 83(2): 164-195 (2016) - [c21]Paul S. Bonsma, Daniël Paulusma:
Using Contracted Solution Graphs for Solving Reconfiguration Problems. MFCS 2016: 20:1-20:15 - 2015
- [i15]Paul S. Bonsma, Daniël Paulusma:
Using Contracted Solution Graphs for Solving Reconfiguration Problems. CoRR abs/1509.06357 (2015) - [i14]Christoph Berkholz, Paul S. Bonsma, Martin Grohe:
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. CoRR abs/1509.08251 (2015) - 2014
- [j19]Paul S. Bonsma, Jens Schulz, Andreas Wiese:
A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths. SIAM J. Comput. 43(2): 767-799 (2014) - [c20]Paul S. Bonsma, Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman:
The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration. IPEC 2014: 110-121 - [c19]Paul S. Bonsma, Marcin Kaminski, Marcin Wrochna:
Reconfiguring Independent Sets in Claw-Free Graphs. SWAT 2014: 86-97 - [c18]Paul S. Bonsma:
Independent Set Reconfiguration in Cographs. WG 2014: 105-116 - [i13]Paul S. Bonsma:
Independent Set Reconfiguration in Cographs. CoRR abs/1402.1587 (2014) - [i12]Paul S. Bonsma, Marcin Kaminski, Marcin Wrochna:
Reconfiguring Independent Sets in Claw-Free Graphs. CoRR abs/1403.0359 (2014) - [i11]Paul S. Bonsma, Amer E. Mouawad:
The Complexity of Bounded Length Graph Recoloring. CoRR abs/1404.0337 (2014) - 2013
- [j18]Paul S. Bonsma:
The complexity of rerouting shortest paths. Theor. Comput. Sci. 510: 1-12 (2013) - [c17]Christoph Berkholz, Paul S. Bonsma, Martin Grohe:
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. ESA 2013: 145-156 - [c16]Hans L. Bodlaender, Paul S. Bonsma, Daniel Lokshtanov:
The Fine Details of Fast Dynamic Programming over Tree Decompositions. IPEC 2013: 41-53 - 2012
- [j17]Paul S. Bonsma, Felix Breuer:
Counting Hexagonal Patches and Independent Sets in Circle Graphs. Algorithmica 63(3): 645-671 (2012) - [j16]Paul S. Bonsma, Florian Zickfeld:
Improved bounds for spanning trees with many leaves. Discret. Math. 312(6): 1178-1194 (2012) - [j15]Paul S. Bonsma:
Max-leaves spanning tree is APX-hard for cubic graphs. J. Discrete Algorithms 12: 14-23 (2012) - [j14]Paul S. Bonsma, Hajo Broersma, Viresh Patel, Artem V. Pyatkin:
The complexity of finding uniform sparsest cuts in various graph classes. J. Discrete Algorithms 14: 136-149 (2012) - [j13]Paul S. Bonsma, Arthur M. Farley, Andrzej Proskurowski:
Extremal graphs having no matching cuts. J. Graph Theory 69(2): 206-222 (2012) - [c15]Paul S. Bonsma:
Rerouting shortest paths in planar graphs. FSTTCS 2012: 337-349 - [c14]Paul S. Bonsma:
The Complexity of Rerouting Shortest Paths. MFCS 2012: 222-233 - [c13]Paul S. Bonsma:
Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces. STACS 2012: 531-542 - [i10]Paul S. Bonsma:
Rerouting shortest paths in planar graphs. CoRR abs/1204.5613 (2012) - 2011
- [j12]Paul S. Bonsma, Florian Zickfeld:
A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs. SIAM J. Discret. Math. 25(4): 1652-1666 (2011) - [j11]Paul S. Bonsma, Frederic Dorn:
Tight bounds and a fast FPT algorithm for directed Max-Leaf Spanning Tree. ACM Trans. Algorithms 7(4): 44:1-44:19 (2011) - [c12]Paul S. Bonsma, Jens Schulz, Andreas Wiese:
A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths. FOCS 2011: 47-56 - [c11]Paul S. Bonsma, Daniel Lokshtanov:
Feedback Vertex Set in Mixed Graphs. WADS 2011: 122-133 - [i9]Paul S. Bonsma, Jens Schulz, Andreas Wiese:
A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths. CoRR abs/1102.3643 (2011) - [i8]Paul S. Bonsma:
Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces. CoRR abs/1109.4554 (2011) - 2010
- [j10]Paul S. Bonsma:
Most balanced minimum cuts. Discret. Appl. Math. 158(4): 261-276 (2010) - [c10]Paul S. Bonsma, Hajo Broersma, Viresh Patel, Artem V. Pyatkin:
The Complexity Status of Problems Related to Sparsest Cuts. IWOCA 2010: 125-135 - [c9]Paul S. Bonsma, Felix Breuer:
Counting Hexagonal Patches and Independent Sets in Circle Graphs. LATIN 2010: 603-614 - [i7]Paul S. Bonsma:
Shortest Path Reconfiguration is PSPACE-hard. CoRR abs/1009.3217 (2010) - [i6]Paul S. Bonsma, Daniel Lokshtanov:
Feedback Vertex Set in Mixed Graphs. CoRR abs/1010.5974 (2010)
2000 – 2009
- 2009
- [j9]Paul S. Bonsma:
The complexity of the matching-cut problem for planar graphs and other graph classes. J. Graph Theory 62(2): 109-126 (2009) - [j8]Paul S. Bonsma, Luis Cereceda:
Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor. Comput. Sci. 410(50): 5215-5226 (2009) - [c8]Paul S. Bonsma, Felix Breuer:
Finding Fullerene Patches in Polynomial Time. ISAAC 2009: 750-759 - [i5]Paul S. Bonsma, Felix Breuer:
Finding Fullerene Patches in Polynomial Time. CoRR abs/0907.2627 (2009) - [i4]Paul S. Bonsma:
Max-Leaves Spanning Tree is APX-hard for Cubic Graphs. CoRR abs/0912.0226 (2009) - 2008
- [j7]Paul S. Bonsma:
Spanning Trees with Many Leaves in Graphs With Minimum Degree Three. SIAM J. Discret. Math. 22(3): 920-937 (2008) - [c7]Paul S. Bonsma, Frederic Dorn:
Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree. ESA 2008: 222-233 - [c6]Paul S. Bonsma, Florian Zickfeld:
Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms. LATIN 2008: 531-543 - [c5]Paul S. Bonsma, Florian Zickfeld:
A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs. WG 2008: 66-77 - [i3]Paul S. Bonsma, Frederic Dorn:
Tight Bounds and Faster Algorithms for Directed Max-Leaf Problems. CoRR abs/0804.2032 (2008) - [i2]Paul S. Bonsma, Felix Breuer:
Finding Fullerene Patches in Polynomial Time I: Counting Hexagonal Patches. CoRR abs/0808.3881 (2008) - 2007
- [j6]Paul S. Bonsma:
Linear time algorithms for finding sparsest cuts in various graph classes. Electron. Notes Discret. Math. 28: 265-272 (2007) - [j5]Paul S. Bonsma, Luis Cereceda, Jan van den Heuvel, Matthew Johnson:
Finding Paths between Graph Colourings: Computational Complexity and Possible Distances. Electron. Notes Discret. Math. 29: 463-469 (2007) - [c4]Paul S. Bonsma:
Most balanced minimum cuts and partially ordered knapsack. CTW 2007: 17-21 - [c3]Paul S. Bonsma, Luis Cereceda:
Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances. MFCS 2007: 738-749 - [i1]Paul S. Bonsma, Frederic Dorn:
An FPT Algorithm for Directed Spanning k-Leaf. CoRR abs/0711.4052 (2007) - 2006
- [j4]Paul S. Bonsma, Thomas Epping, Winfried Hochstättler:
Complexity results on restricted instances of a paint shop problem for words. Discret. Appl. Math. 154(9): 1335-1343 (2006) - 2004
- [j3]Paul S. Bonsma:
Sparsest cuts and concurrent flows in product graphs. Discret. Appl. Math. 136(2-3): 173-182 (2004) - 2003
- [j2]Paul S. Bonsma:
The Complexity of the Matching-cut Problem for Various Graph Classes. Electron. Notes Discret. Math. 13: 18-21 (2003) - [c2]Paul S. Bonsma, Tobias Brüggemann, Gerhard J. Woeginger:
A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves. MFCS 2003: 259-268 - [c1]Paul S. Bonsma:
The Complexity of the Matching-Cut Problem for Planar Graphs and Other Graph Classes. WG 2003: 93-105 - 2002
- [j1]Paul S. Bonsma, Nicola Ueffing, Lutz Volkmann:
Edge-cuts leaving components of order at least three. Discret. Math. 256(1-2): 431-439 (2002)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-01-09 13:00 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
