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

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

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

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

Back to profile page