By Professor Serge Gaspers

Books

Gaspers S, 2010, Exponential Time Algorithms - Structures, Measures, and Bounds., VDM

Book Chapters

Fernau H; Gaspers S; Klasing R, 2024, 'Preface', in SOFSEM 2024: Theory and Practice of Computer Science, pp. v - vii, https://link.springer.com/content/pdf/bfm:978-3-031-52113-3/1

Gaspers S; Ordyniak S; Szeider S, 2017, 'Backdoor Sets for CSP', in Krokhin AA; Zivný S (ed.), The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 137 - 157, http://dx.doi.org/10.4230/DFU.Vol7.15301.5

Gaspers S; Walsh T, 2017, 'Preface', in Theory and Applications of Satisfiability Testing – SAT 2017, Springer International Publishing, pp. V - VIII

Gaspers S, 2016, 'Backdoors to SAT.', in Encyclopedia of Algorithms, Springer Science & Business Media, pp. 167 - 170, http://dx.doi.org/10.1007/978-1-4939-2864-4_781

Gaspers S, 2015, 'Backdoors to SAT', in Encyclopedia of Algorithms, Springer Berlin Heidelberg, pp. 1 - 5, http://dx.doi.org/10.1007/978-3-642-27848-8_781-1

Gaspers S; Szeider S, 2012, 'Backdoors to Satisfaction', in Bodlaender HL; Downey R; Fomin FV; Marx D (ed.), The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, Springer, Berlin, pp. 287 - 317, http://dx.doi.org/10.1007/978-3-642-30891-8_15

Fellows MR; Gaspers S; Rosamond FA, 2011, 'Multivariate Complexity Theory', in Blum EK; Aho AV (ed.), Computer Science: The Hardware, Software and Heart of It, Springer, New York, pp. 269 - 293, http://dx.doi.org/10.1007/978-1-4614-1168-0_13

Journal articles

Clinch K; Gaspers S; He Z; Saffidine A; Zhang T, 2025, 'A Piecewise Approach for the Analysis of Exact Algorithms', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 15411 LNCS, pp. 79 - 93, http://dx.doi.org/10.1007/978-981-96-2845-2_6

Gaspers S; Lee EJ, 2023, 'Faster Graph Coloring in Polynomial Space', Algorithmica, 85, pp. 584 - 609, http://dx.doi.org/10.1007/s00453-022-01034-7

Aziz H; Biró P; Fleiner T; Gaspers S; de Haan R; Mattei N; Rastegari B, 2022, 'Stable matching with uncertain pairwise preferences', Theoretical Computer Science, 909, pp. 1 - 11, http://dx.doi.org/10.1016/j.tcs.2022.01.028

Smith J; Asghar HJ; Gioiosa G; Mrabet S; Gaspers S; Tyler P, 2022, 'Making the Most of Parallel Composition in Differential Privacy', Proceedings on Privacy Enhancing Technologies, 2022, pp. 253 - 273, http://dx.doi.org/10.2478/popets-2022-0013

Casel K; Fernau H; Gaspers S; Gras B; Schmid ML, 2021, 'On the Complexity of the Smallest Grammar Problem over Fixed Alphabets', Theory of Computing Systems, 65, pp. 344 - 409, http://dx.doi.org/10.1007/s00224-020-10013-w

Smith J; Asghar HJ; Gioiosa G; Mrabet S; Gaspers S; Tyler P, 2021, 'Making the Most of Parallel Composition in Differential Privacy.', CoRR, abs/2109.09078

Aziz H; Biró P; Gaspers S; de Haan R; Mattei N; Rastegari B, 2020, 'Stable Matching with Uncertain Linear Preferences', Algorithmica, 82, pp. 1410 - 1433, http://dx.doi.org/10.1007/s00453-019-00650-0

Aziz H; Biró P; Gaspers S; Haan RD; Mattei N; Rastegari B, 2020, 'Stable Matching with Uncertain Linear Preferences.', Algorithmica, 82, pp. 1410 - 1433

Gaspers S; Huang S, 2019, 'Linearly χ-bounding (P6, C4)-free graphs*', Journal of Graph Theory, 92, pp. 322 - 342, http://dx.doi.org/10.1002/jgt.22456

Gaspers S; Gudmundsson J; Jones M; Mestre J; Rümmele S, 2019, 'Turbocharging Treewidth Heuristics', Algorithmica, 81, pp. 439 - 475, http://dx.doi.org/10.1007/s00453-018-0499-1

Gaspers S; Huang S, 2019, '(2P2,K4)-Free graphs are 4-Colorable', SIAM Journal on Discrete Mathematics, 33, pp. 1095 - 1120, http://dx.doi.org/10.1137/18M1205832

Gaspers S; Huang S; Paulusma D, 2019, 'Colouring square-free graphs without long induced paths.', J. Comput. Syst. Sci., 106, pp. 60 - 79, http://dx.doi.org/10.1016/j.jcss.2019.06.002

Fomin FV; Gaspers S; Lokshtanov D; Saurabh S, 2019, 'Exact Algorithms via Monotone Local Search.', J. ACM, 66, pp. 8:1 - 8:23, http://dx.doi.org/10.1145/3284176

Aziz H; Gaspers S; Mackenzie S; Mattei N; Stursberg P; Walsh T, 2018, 'Fixing balanced knockout and double elimination tournaments', Artificial Intelligence, 262, pp. 1 - 14, http://dx.doi.org/10.1016/j.artint.2018.05.002

Finbow S; Gaspers S; Messinger ME; Ottaway P, 2018, 'A note on the eternal dominating set problem', International Journal of Game Theory, 47, pp. 543 - 555, http://dx.doi.org/10.1007/s00182-018-0623-0

Gaspers S; Mackenzie S, 2018, 'On the number of minimal separators in graphs', Journal of Graph Theory, 87, pp. 653 - 659, http://dx.doi.org/10.1002/jgt.22179

Gaspers S; Sorkin GB, 2017, 'Separate, measure and conquer: Faster polynomial-space algorithms for Max 2-CSP and counting dominating sets', ACM Transactions on Algorithms, 13, http://dx.doi.org/10.1145/3111499

Gaspers S; Misra N; Ordyniak S; Szeider S; Živný S, 2017, 'Backdoors into heterogeneous classes of SAT and CSP', Journal of Computer and System Sciences, 85, pp. 38 - 56, http://dx.doi.org/10.1016/j.jcss.2016.10.007

Gaspers S; Ordyniak S; Ramanujan MS; Saurabh S; Szeider S, 2016, 'Backdoors to q-Horn', Algorithmica, 74, pp. 540 - 557, http://dx.doi.org/10.1007/s00453-014-9958-5

van Bevern R; Downey RG; Fellows MR; Gaspers S; Rosamond FA, 2015, 'Myhill–Nerode Methods for Hypergraphs', Algorithmica, 73, pp. 696 - 729, http://dx.doi.org/10.1007/s00453-015-9977-x

Aziz H; Gaspers S; Mackenzie S; Walsh T, 2015, 'Two Desirable Fairness Concepts for Allocation of Indivisible Objects under Ordinal Preferences', ACM SIGECOM EXCHANGES, 14, pp. 16 - 21, https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000372616400002&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=891bb5ab6ba270e68a29b250adbe88d1

Aziz H; Gaspers S; Mackenzie S; Walsh T, 2015, 'Fair assignment of indivisible objects under ordinal preferences', Artificial Intelligence, 227, pp. 71 - 92, http://dx.doi.org/10.1016/j.artint.2015.06.002

Gaspers S; Liedloff M; Stein M; Suchan K, 2015, 'Complexity of splits reconstruction for low-degree trees', Discrete Applied Mathematics, 180, pp. 89 - 100, http://dx.doi.org/10.1016/j.dam.2014.08.005

Frati F; Gaspers S; Gudmundsson J; Mathieson L, 2015, 'Augmenting Graphs to Minimize the Diameter.', Algorithmica, 72, pp. 995 - 1010, http://dx.doi.org/10.1007/s00453-014-9886-4

Aziz H; Gaspers S; Mackenzie S; Walsh T, 2015, 'Fair assignment of indivisible objects under ordinal preferences.', Artif. Intell., 227, pp. 71 - 92, http://dx.doi.org/10.1016/j.artint.2015.06.002

Gaspers S; Koivisto M; Liedloff M; Ordyniak S; Szeider S, 2015, 'On finding optimal polytrees.', Theor. Comput. Sci., 592, pp. 49 - 58

Gaspers S; Ordyniak S; Ramanujan MS; Saurabh S; Szeider S, 2014, 'Backdoors to q-Horn', Algorithmica, http://dx.doi.org/10.1007/s00453-014-9958-5

Gaspers S; Szeider S, 2014, 'Guarantees and limits of preprocessing in constraint satisfaction and reasoning', Artificial Intelligence, 216, pp. 1 - 19, http://dx.doi.org/10.1016/j.artint.2014.06.006

Fürer M; Gaspers S; Kasiviswanathan SP, 2013, 'An exponential time 2-approximation algorithm for bandwidth', Theoretical Computer Science, 511, pp. 23 - 31, http://dx.doi.org/10.1016/j.tcs.2013.03.024

Fomin FV; Gaspers S; Saurabh S; Thomassé S, 2013, 'A linear vertex kernel for maximum internal spanning tree', Journal of Computer and System Sciences, 79, pp. 1 - 6, http://dx.doi.org/10.1016/j.jcss.2012.03.004

Binkele-Raible D; Fernau H; Gaspers S; Liedloff M, 2013, 'Exact and parameterized algorithms for max internal spanning tree', Algorithmica, 65, pp. 95 - 128, http://dx.doi.org/10.1007/s00453-011-9575-5

Gaspers S; Mnich M, 2013, 'Feedback vertex sets in tournaments', Journal of Graph Theory, 72, pp. 72 - 89, http://dx.doi.org/10.1002/jgt.21631

Fomin FV; Gaspers S; Saurabh S; Thomasse S, 2013, 'A linear vertex kernel for maximum internal spanning tree', JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 79, pp. 1 - 6, http://dx.doi.org/10.1016/j.jcss.2012.03.004

Gaspers S; Liedloff M, 2012, 'A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set', Discrete Mathematics & Theoretical Computer Science, Vol. 14 no. 1, http://dx.doi.org/10.46298/dmtcs.563

Gaspers S; Koivisto M; Liedloff M; Ordyniak S; Szeider S, 2012, 'On Finding Optimal Polytrees', Proceedings of the 26th AAAI Conference on Artificial Intelligence, AAAI 2012, pp. 750 - 756

Gaspers S; Liedloff M, 2012, 'A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set', Discrete Mathematics & Theoretical Computer Science, 14, pp. 29 - 42, http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1744

Gaspers S; Sorkin GB, 2012, 'A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between', Journal of Computer and System Sciences, 78, pp. 305 - 335, http://dx.doi.org/10.1016/j.jcss.2011.05.010

Bevern RV; Fellows MR; Gaspers S; Rosamond FA, 2012, 'How applying Myhill-Nerode methods to hypergraphs helps mastering the Art of Trellis Decoding', CoRR, abs/1211.1299

Gaspers S; Kratsch D; Liedloff M, 2012, 'On Independent Sets and Bicliques in Graphs', Algorithmica, 62, pp. 637 - 658, http://dx.doi.org/10.1007/s00453-010-9474-1

Fellows MR; Gaspers S; Rosamond FA, 2012, 'Parameterizing by the Number of Numbers', Theory of Computing Systems, 50, pp. 675 - 693, http://dx.doi.org/10.1007/s00224-011-9367-y

Fellows MR; Gaspers S; Rosamond FA, 2012, 'Parameterizing by the Number of Numbers.', Theory Comput. Syst., 50, pp. 675 - 693, http://dx.doi.org/10.1007/s00224-011-9367-y

Bessy S; Fomin FV; Gaspers S; Paul C; Perez A; Saurabh S; Thomassé S, 2011, 'Kernels for feedback arc set in tournaments', Journal of Computer and System Sciences, 77, pp. 1071 - 1078, http://dx.doi.org/10.1016/j.jcss.2010.10.001

Back to profile page