By Professor Serge Gaspers

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

Bessy S; Fomin FV; Gaspers S; Paul C; Perez A; Saurabh S; Thomassé S, 2011, 'Kernels for feedback arc set in tournaments.', J. Comput. Syst. Sci., 77, pp. 1071 - 1078

Binkele-Raible D; Fernau H; Gaspers S; Liedloff M, 2010, 'Exact exponential-time algorithms for finding bicliques', Information Processing Letters, 111, pp. 64 - 67, http://dx.doi.org/10.1016/j.ipl.2010.10.020

Fomin FV; Gaspers S; Golovach PA; Kratsch D; Saurabh S, 2010, 'Parameterized algorithm for eternal vertex cover', Information Processing Letters, 110, pp. 702 - 706, http://dx.doi.org/10.1016/j.ipl.2010.05.029

Gaspers S; Messinger ME; Nowakowski RJ; Prałat P, 2010, 'Parallel cleaning of a network with brushes', Discrete Applied Mathematics, 158, pp. 467 - 478, http://dx.doi.org/10.1016/j.dam.2009.11.003

Fomin FV; Gaspers S; Kratsch D; Liedloff M; Saurabh S, 2010, 'Iterative compression and exact algorithms', Theoretical Computer Science, 411, pp. 1045 - 1053, http://dx.doi.org/10.1016/j.tcs.2009.11.012

Gaspers S; Kratsch D; Liedloff M; Todinca I, 2009, 'Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes', ACM TRANSACTIONS ON ALGORITHMS, 6, http://dx.doi.org/10.1145/1644015.1644024

Fomin FV; Gaspers S; Saurabh S; Stepanov AA, 2009, 'On two techniques of combining branching and treewidth', Algorithmica (New York), 54, pp. 181 - 207, http://dx.doi.org/10.1007/s00453-007-9133-3

Gaspers S; Messinger ME; Nowakowski RJ; Prałat P, 2009, 'Clean the graph before you draw it!', Information Processing Letters, 109, pp. 463 - 467, http://dx.doi.org/10.1016/j.ipl.2009.01.003

Back to profile page