Serge Gaspers

Associate Professor and Associate Head of School (Research)
Associate Professor

Currently, I am an Associate Professor and the Associate Head of School (Research) in the School of Computer Science and Engineering at UNSW.

I joined UNSW in 2012, first as an ARC DECRA Fellow and then as a Future Fellow. I obtained a PhD in Computer Science from the University of Bergen (Norway) under the supervision of Fedor V. Fomin in 2008. From 2009-2012, I held postdoctoral positions in Montpellier (France), Santiago (Chile), and Vienna (Austria).

Journal articles
add
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, vol. 65, pp. 344 - 409, http://dx.doi.org/10.1007/s00224-020-10013-w
2021
Aziz H; Biró P; Gaspers S; de Haan R; Mattei N; Rastegari B, 2020, 'Stable Matching with Uncertain Linear Preferences', Algorithmica, vol. 82, pp. 1410 - 1433, http://dx.doi.org/10.1007/s00453-019-00650-0
2020
Aziz H; Biró P; Gaspers S; Haan RD; Mattei N; Rastegari B, 2020, 'Stable Matching with Uncertain Linear Preferences.', Algorithmica, vol. 82, pp. 1410 - 1433
2020
Fomin FV; Gaspers S; Lokshtanov D; Saurabh S, 2019, 'Exact Algorithms via Monotone Local Search.', J. ACM, vol. 66, pp. 8:1 - 8:23, http://dx.doi.org/10.1145/3284176
2019
Gaspers S; Huang S, 2019, '(2P2,K4)-Free graphs are 4-Colorable', SIAM Journal on Discrete Mathematics, vol. 33, pp. 1095 - 1120, http://dx.doi.org/10.1137/18M1205832
2019
Gaspers S; Huang S; Paulusma D, 2019, 'Colouring square-free graphs without long induced paths.', J. Comput. Syst. Sci., vol. 106, pp. 60 - 79, http://dx.doi.org/10.1016/j.jcss.2019.06.002
2019
Gaspers S; Gudmundsson J; Jones M; Mestre J; Rümmele S, 2019, 'Turbocharging Treewidth Heuristics', Algorithmica, vol. 81, pp. 439 - 475, http://dx.doi.org/10.1007/s00453-018-0499-1
2019
Gaspers S; Huang S, 2019, 'Linearly χ-bounding (P6, C4)-free graphs*', Journal of Graph Theory, vol. 92, pp. 322 - 342, http://dx.doi.org/10.1002/jgt.22456
2019
Finbow S; Gaspers S; Messinger ME; Ottaway P, 2018, 'A note on the eternal dominating set problem', International Journal of Game Theory, vol. 47, pp. 543 - 555, http://dx.doi.org/10.1007/s00182-018-0623-0
2018
Gaspers S; Mackenzie S, 2018, 'On the number of minimal separators in graphs', Journal of Graph Theory, vol. 87, pp. 653 - 659, http://dx.doi.org/10.1002/jgt.22179
2018
Aziz H; Gaspers S; Mackenzie S; Mattei N; Stursberg P; Walsh T, 2018, 'Fixing balanced knockout and double elimination tournaments', Artificial Intelligence, vol. 262, pp. 1 - 14, http://dx.doi.org/10.1016/j.artint.2018.05.002
2018
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, vol. 85, pp. 38 - 56, http://dx.doi.org/10.1016/j.jcss.2016.10.007
2017
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, vol. 13, http://dx.doi.org/10.1145/3111499
2017
Gaspers S; Ordyniak S; Ramanujan MS; Saurabh S; Szeider S, 2016, 'Backdoors to q-Horn', Algorithmica, vol. 74, pp. 540 - 557, http://dx.doi.org/10.1007/s00453-014-9958-5
2016
Gaspers S; Liedloff M; Stein M; Suchan K, 2015, 'Complexity of splits reconstruction for low-degree trees', Discrete Applied Mathematics, vol. 180, pp. 89 - 100, http://dx.doi.org/10.1016/j.dam.2014.08.005
2015
Aziz H; Gaspers S; Mackenzie S; Walsh T, 2015, 'Fair assignment of indivisible objects under ordinal preferences.', Artif. Intell., vol. 227, pp. 71 - 92
2015
Aziz H; Gaspers S; Mackenzie S; Walsh T, 2015, 'Fair assignment of indivisible objects under ordinal preferences', Artificial Intelligence, vol. 227, pp. 71 - 92, http://dx.doi.org/10.1016/j.artint.2015.06.002
2015
van Bevern R; Downey RG; Fellows MR; Gaspers S; Rosamond FA, 2015, 'Myhill–Nerode Methods for Hypergraphs', Algorithmica, vol. 73, pp. 696 - 729, http://dx.doi.org/10.1007/s00453-015-9977-x
2015
Gaspers S; Koivisto M; Liedloff M; Ordyniak S; Szeider S, 2015, 'On finding optimal polytrees.', Theor. Comput. Sci., vol. 592, pp. 49 - 58
2015
Frati F; Gaspers S; Gudmundsson J; Mathieson L, 2015, 'Augmenting Graphs to Minimize the Diameter.', Algorithmica, vol. 72, pp. 995 - 1010
2015
Aziz H; Gaspers S; Mackenzie S; Walsh T, 2015, 'Two Desirable Fairness Concepts for Allocation of Indivisible Objects under Ordinal Preferences', SI GECOM EXCHANGES, vol. 14, pp. 16 - 21, http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000372616400002&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=891bb5ab6ba270e68a29b250adbe88d1
2015
Gaspers S; Szeider S, 2014, 'Guarantees and limits of preprocessing in constraint satisfaction and reasoning', Artificial Intelligence, vol. 216, pp. 1 - 19, http://dx.doi.org/10.1016/j.artint.2014.06.006
2014
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
2014
Fomin FV; Gaspers S; Saurabh S; Thomassé S, 2013, 'A linear vertex kernel for maximum internal spanning tree', Journal of Computer and System Sciences, vol. 79, pp. 1 - 6, http://dx.doi.org/10.1016/j.jcss.2012.03.004
2013
Fomin FV; Gaspers S; Saurabh S; Thomasse S, 2013, 'A linear vertex kernel for maximum internal spanning tree', JOURNAL OF COMPUTER AND SYSTEM SCIENCES, vol. 79, pp. 1 - 6, http://dx.doi.org/10.1016/j.jcss.2012.03.004
2013
Binkele-Raible D; Fernau H; Gaspers S; Liedloff M, 2013, 'Exact and parameterized algorithms for max internal spanning tree', Algorithmica, vol. 65, pp. 95 - 128, http://dx.doi.org/10.1007/s00453-011-9575-5
2013
Fürer M; Gaspers S; Kasiviswanathan SP, 2013, 'An exponential time 2-approximation algorithm for bandwidth', Theoretical Computer Science, vol. 511, pp. 23 - 31, http://dx.doi.org/10.1016/j.tcs.2013.03.024
2013
Gaspers S; Mnich M, 2013, 'Feedback vertex sets in tournaments', Journal of Graph Theory, vol. 72, pp. 72 - 89, http://dx.doi.org/10.1002/jgt.21631
2013
Fellows MR; Gaspers S; Rosamond FA, 2012, 'Parameterizing by the Number of Numbers', Theory of Computing Systems, vol. 50, pp. 675 - 693, http://dx.doi.org/10.1007/s00224-011-9367-y
2012
Gaspers S; Kratsch D; Liedloff M, 2012, 'On Independent Sets and Bicliques in Graphs', Algorithmica, vol. 62, pp. 637 - 658, http://dx.doi.org/10.1007/s00453-010-9474-1
2012
Fellows MR; Gaspers S; Rosamond FA, 2012, 'Parameterizing by the Number of Numbers.', Theory Comput. Syst., vol. 50, pp. 675 - 693
2012
Gaspers S; Liedloff M, 2012, 'A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set', Discrete Mathematics & Theoretical Computer Science, vol. 14, pp. 29 - 42, http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1744
2012
Bevern RV; Fellows MR; Gaspers S; Rosamond FA, 2012, 'How applying Myhill-Nerode methods to hypergraphs helps mastering the Art of Trellis Decoding', CoRR, vol. abs/1211.1299
2012
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, vol. 78, pp. 305 - 335, http://dx.doi.org/10.1016/j.jcss.2011.05.010
2012
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., vol. 77, pp. 1071 - 1078
2011
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, vol. 77, pp. 1071 - 1078, http://dx.doi.org/10.1016/j.jcss.2010.10.001
2011
Fomin FV; Gaspers S; Kratsch D; Liedloff M; Saurabh S, 2010, 'Iterative compression and exact algorithms', Theoretical Computer Science, vol. 411, pp. 1045 - 1053, http://dx.doi.org/10.1016/j.tcs.2009.11.012
2010
Binkele-Raible D; Fernau H; Gaspers S; Liedloff M, 2010, 'Exact exponential-time algorithms for finding bicliques', Information Processing Letters, vol. 111, pp. 64 - 67, http://dx.doi.org/10.1016/j.ipl.2010.10.020
2010
Gaspers S; Messinger ME; Nowakowski RJ; Prałat P, 2010, 'Parallel cleaning of a network with brushes', Discrete Applied Mathematics, vol. 158, pp. 467 - 478, http://dx.doi.org/10.1016/j.dam.2009.11.003
2010
Fomin FV; Gaspers S; Golovach PA; Kratsch D; Saurabh S, 2010, 'Parameterized algorithm for eternal vertex cover', Information Processing Letters, vol. 110, pp. 702 - 706, http://dx.doi.org/10.1016/j.ipl.2010.05.029
2010
Gaspers S; Messinger ME; Nowakowski RJ; Prałat P, 2009, 'Clean the graph before you draw it!', Information Processing Letters, vol. 109, pp. 463 - 467, http://dx.doi.org/10.1016/j.ipl.2009.01.003
2009
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, vol. 6, http://dx.doi.org/10.1145/1644015.1644024
2009
Fomin FV; Gaspers S; Saurabh S; Stepanov AA, 2009, 'On two techniques of combining branching and treewidth', Algorithmica (New York), vol. 54, pp. 181 - 207, http://dx.doi.org/10.1007/s00453-007-9133-3
2009
Fomin FV; Gaspers S; Pyatkin AV; Razgon I, 2008, 'On the minimum feedback vertex set problem: Exact and enumeration algorithms', Algorithmica (New York), vol. 52, pp. 293 - 307, http://dx.doi.org/10.1007/s00453-007-9152-0
2008
Conference Papers
add
Aziz H; Gaspers S; Sun Z; Yokoo M, 2020, 'Multiple Levels of Importance in Matching with Distributional Constraints: Extended Abstract.', in Seghrouchni AEF; Sukthankar G; An B; Yorke-Smith N (eds.), AAMAS, International Foundation for Autonomous Agents and Multiagent Systems, pp. 1759 - 1761, https://dl.acm.org/doi/proceedings/10.5555/3398761
2020
Aziz H; Gaspers S; Sun Z, 2020, 'Mechanism design for school choice with soft diversity constraints', in Bessiere C (ed.), IJCAI International Joint Conference on Artificial Intelligence, ijcai.org, pp. 153 - 159, https://www.ijcai.org/Proceedings/2020/
2020
Aziz H; Gaspers S; Sun Z, 2020, 'Mechanism design for school choice with soft diversity constraints', in Seghrouchni AEF; Sukthankar G; An B; Yorke-Smith N (eds.), Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, International Foundation for Autonomous Agents and Multiagent Systems, pp. 1756 - 1758, https://dl.acm.org/doi/proceedings/10.5555/3398761
2020
Aziz H; Gaspers S; Sun Z; Yokoo M, 2020, 'Multiple levels of importance in matching with distributional constraints', in Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, pp. 1759 - 1761
2020
Gerding EH; Perez-Diaz A; Aziz H; Gaspers S; Marcu A; Mattei N; Walsh T, 2019, 'Fair online allocation of perishable goods and its application to electric vehicle charging', in IJCAI International Joint Conference on Artificial Intelligence, Macao, China, pp. 5569 - 5575, presented at Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-, Macao, China, 10 August 2019, http://dx.doi.org/10.24963/ijcai.2019/773
2019
Fomin FV; Gaspers S; Lokshtanov D; Saurabh S, 2019, 'Exact algorithms via monotone local search', in Wichs D; Mansour Y (ed.), Journal of the ACM, ACM, pp. 764 - 775, presented at Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, http://dx.doi.org/10.1145/3284176
2019
Gaspers S; Li R, 2019, 'Enumeration of preferred extensions in almost oriented digraphs', in Leibniz International Proceedings in Informatics, LIPIcs, Aachen, Germany, presented at 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), Aachen, Germany, 26 August 2019, http://dx.doi.org/10.4230/LIPIcs.MFCS.2019.74
2019
Gaspers S; Lau J, 2019, 'Minimizing and computing the inverse geodesic length on trees', in Leibniz International Proceedings in Informatics, LIPIcs, Shanghai, China, presented at 30th International Symposium on Algorithms and Computation (ISAAC 2019) held in Shanghai, China on December 8-11, 2019, Shanghai, China, 08 December 2019 - 11 December 2019, http://dx.doi.org/10.4230/LIPIcs.ISAAC.2019.59
2019
Aziz H; Sun Z; Gaspers S; Walsh T, 2019, 'From matching with diversity constraints to matching with regional quotas', in Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, ASSOC COMPUTING MACHINERY, Montreal, CANADA, pp. 377 - 385, presented at 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), Montreal, CANADA, 13 May 2019 - 17 May 2019, http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000474345000047&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=891bb5ab6ba270e68a29b250adbe88d1
2019
Gaspers S; Najeebullah K, 2019, 'Optimal Surveillance of Covert Networks by Minimizing Inverse Geodesic Length', in THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE, Honolulu, HI, pp. 533 - 540, presented at 33rd AAAI Conference on Artificial Intelligence / 31st Innovative Applications of Artificial Intelligence Conference / 9th AAAI Symposium on Educational Advances in Artificial Intelligence, Honolulu, HI, 27 January 2019 - 01 February 2019, http://dx.doi.org/10.1609/aaai.v33i01.3301533
2019
Abu-Khzam FN; Egan J; Gaspers S; Shaw A; Shaw P, 2018, 'Cluster editing with vertex splitting', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 1 - 13, http://dx.doi.org/10.1007/978-3-319-96151-4_1
2018
Chen J; Sun Z; Aziz H; Gaspers S, 2018, 'Stability and pareto optimality in refugee allocation matchings', in Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, ACM, Stockholm, Sweden, pp. 964 - 972, presented at 17th International Conference on Autonomous Agents and MultiAgent Systems, Stockholm, Sweden, 10 July 2018 - 15 July 2018, https://dl.acm.org/citation.cfm?id=3237383
2018
Aziz H; Gaspers S; Lee EJ; Najeebullah K, 2018, 'Defender stackelberg game with inverse geodesic length as utility metric', in Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, International Foundation for Autonomous Agents and Multiagent Systems, Stockholm, Sweden, pp. 694 - 702, presented at AAMAS (International Conference on Autonomous Agents and Multiagent Systems) 2018, Stockholm, Sweden, 10 July 2018 - 15 July 2018, http://ifaamas.org/Proceedings/aamas2018/pdfs/p694.pdf
2018
Gaspers S; Gudmundsson J; Horton M; Rümmele S, 2018, 'When is red-blue nonblocker fixed-parameter tractable?', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 515 - 528, http://dx.doi.org/10.1007/978-3-319-77404-6_38
2018
Gaspers S; Huang S; Paulusma D, 2018, 'Colouring square-free graphs without long induced paths', in Niedermeier R; Vallée B (ed.), Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Caen, France, pp. 35:1 - 35:15, presented at 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France, 28 February 2018 - 03 March 2018, http://dx.doi.org/10.4230/LIPIcs.STACS.2018.35
2018
Gaspers S; Lee EJ, 2017, 'Exact Algorithms via Multivariate Subroutines', in Proceedings of ICALP 2017, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Warsaw, Poland, pp. 69:1 - 69:13, presented at ICALP 2017 - 44th International Colloquium on Automata, Languages, and Programming, Warsaw, Poland, 10 July 2017 - 14 July 2017, http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.69
2017
Bonnet E; Gaspers S; Lambilliotte A; Rümmele S; Saffidine A, 2017, 'The Parameterized Complexity of Positional Games', in Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Warsaw, Poland, pp. 90:1 - 90:14, presented at ICALP 2017 - 44th International Colloquium on Automata, Languages, and Programming, Warsaw, Poland, 10 July 2017 - 14 July 2017, http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.90
2017
Gaspers S; Rümmele S; Saffidine A; Tran K, 2017, 'Minesweeper with limited moves', in McIlraith SA; Weinberger KQ (eds.), 32nd AAAI Conference on Artificial Intelligence, AAAI 2018, Association for the Advancement of Artificial Intelligence, New Orleans, Louisiana, USA, pp. 860 - 867, presented at Thirty-Second AAAI Conference on Artificial Intelligence, New Orleans, Louisiana, USA, 02 February 2017 - 07 February 2017, https://www.aaai.org/ocs/index.php/AAAI/AAAI18/schedConf/presentations
2017
Gaspers S; Lee EJ, 2017, 'Faster Graph Coloring in Polynomial Space', in Faster Graph Coloring in Polynomial Space, Springer, Hong Kong, China, pp. 371 - 383, presented at COCOON 2017 - 23rd International Conference on Computing and Combinatorics, Hong Kong, China, 03 August 2017 - 05 August 2017, http://dx.doi.org/10.1007/978-3-319-62389-4_31
2017
Aziz H; Gaspers S; Najeebullah K, 2017, 'Weakening covert networks by minimizing inverse geodesic length', in IJCAI International Joint Conference on Artificial Intelligence, pp. 779 - 785, http://dx.doi.org/10.24963/ijcai.2017/108
2017
Aziz H; Biro P; Fleiner T; Gaspers S; de Haan R; Mattei N; Rastegari B, 2017, 'Stable Matching with Uncertain Pairwise Preferences', in Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, ACM, Sao Paulo, Brazil, pp. 344 - 352, presented at AAMAS 2017 - 16th Conference on Autonomous Agents and MultiAgent Systems, Sao Paulo, Brazil, 08 May 2017 - 12 May 2017, http://dl.acm.org/citation.cfm?id=3091179
2017
Gaspers S; Huang S, 2017, 'Linearly χ -Bounding (P6, C4) -Free Graphs', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Eindhoven, The Netherlands, pp. 263 - 274, presented at 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, 21 June 2017 - 23 June 2017, http://dx.doi.org/10.1007/978-3-319-68705-6_20
2017
Abeliuk A; Aziz H; Berbeglia G; Gaspers S; Kalina P; Mattei N; Peters D; Stursberg P; Hentenryck PV; Walsh T, 2016, 'Interdependent Scheduling Games.', in Kambhampati S (ed.), IJCAI, IJCAI/AAAI Press, pp. 2 - 9, presented at Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, http://www.ijcai.org/Proceedings/2016
2016
Abeliuk A; Aziz H; Berbeglia G; Gaspers S; Kalina P; Mattei N; Peters D; Stursberg P; Van Hentenryck P; Walsh T, 2016, 'Interdependent scheduling games', in IJCAI International Joint Conference on Artificial Intelligence, pp. 2 - 9
2016
Gaspers S; Papadimitriou CH; Sæther SH; Telle JA, 2016, 'On Satisfiability Problems with a Linear Structure.', in Guo J; Hermelin D (ed.), IPEC, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 14:1 - 14:1, presented at 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, http://www.dagstuhl.de/dagpub/978-3-95977-023-1
2016
Cochefert M; Couturier J-F; Gaspers S; Kratsch D, 2016, 'Faster Algorithms to Enumerate Hypergraph Transversals.', in Kranakis E; Navarro G; Chávez E (eds.), LATIN, Springer, pp. 306 - 318, presented at LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, https://doi.org/10.1007/978-3-662-49529-2
2016
Gaspers S; Papadimitriou C; Saether SH; Telle JA, 2016, 'On Satisfiability Problems with a Linear Structure', in Leibniz International Proceedings in Informatics, LIPIcs, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), Aarhus, Denmark, presented at 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), Aarhus, Denmark, 24 August 2016 - 26 August 2016, http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.14
2016
Casel K; Fernau H; Gaspers S; Gras B; Schmid ML, 2016, 'On the complexity of grammar-based compression over fixed alphabets', in Leibniz International Proceedings in Informatics, LIPIcs, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy, presented at 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy, 11 July 2016 - 15 July 2016, http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.122
2016
Aziz H; Biró P; Gaspers S; de Haan R; Mattei N; Rastegari B, 2016, 'Stable matching with uncertain linear preferences', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), SPRINGER INT PUBLISHING AG, Liverpool, UK, pp. 195 - 206, presented at Algorithmic Game Theory - 9th International Symposium (SAGT 2016), Liverpool, UK, 19 September 2016 - 21 September 2016, http://dx.doi.org/10.1007/978-3-662-53354-3_16
2016
Gaspers S; Gudmundsson J; Jones M; Mestre J; Ruemmele S, 2016, 'Turbocharging Treewidth Heuristics', in Leibniz International Proceedings in Informatics, LIPIcs, Aarhus, Denmark, presented at 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, Aarhus, Denmark, 24 August 2016 - 26 August 2016, http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.13
2016
Aziz H; Gaspers S; Mackenzie S; Mattei N; Narodytska N; Walsh T, 2015, 'Manipulating the Probabilistic Serial Rule.', in Weiss G; Yolum P; Bordini RH; Elkind E (eds.), AAMAS, ACM, pp. 1451 - 1459, presented at Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, May 4-8, 2015, http://dl.acm.org/citation.cfm?id=2772879
2015
Aziz H; Gaspers S; Mackenzie S; Mattei N; Narodytska N; Walsh T, 2015, 'Equilibria Under the Probabilistic Serial Rule.', in Yang Q; Wooldridge MJ (ed.), IJCAI, AAAI Press, pp. 1105 - 1112, presented at Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, http://ijcai.org/proceedings/2015
2015
Gaspers S; Sorkin GB, 2015, 'Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets.', in Halldórsson MM; Iwama K; Kobayashi N; Speckmann B (eds.), ICALP (1), Springer, pp. 567 - 579, presented at Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, https://doi.org/10.1007/978-3-662-47672-7
2015
Aziz H; Gaspers S; Gudmundsson J; Mackenzie S; Mattei N; Walsh T, 2015, 'Computational Aspects of Multi-Winner Approval Voting.', in Weiss G; Yolum P; Bordini RH; Elkind E (eds.), AAMAS, ACM, pp. 107 - 115, presented at Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, May 4-8, 2015, http://dl.acm.org/citation.cfm?id=2772879
2015
Aleksandrov M; Aziz H; Gaspers S; Walsh T, 2015, 'Online Fair Division: Analysing a Food Bank Problem.', in Yang Q; Wooldridge MJ (ed.), IJCAI, AAAI Press, pp. 2540 - 2546, presented at Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, http://ijcai.org/proceedings/2015
2015
Gaspers S; Mackenzie S, 2015, 'On the Number of Minimal Separators in Graphs.', in Mayr EW (ed.), WG, Springer, pp. 116 - 121, presented at Graph-Theoretic Concepts in Computer Science - 41st International Workshop, WG 2015, Garching, Germany, June 17-19, 2015, Revised Papers, https://doi.org/10.1007/978-3-662-53174-7
2015
Aziz H; Gaspers S; Gudmundsson J; Mestre J; Täubig H, 2015, 'Welfare maximization in fractional hedonic games', in IJCAI International Joint Conference on Artificial Intelligence, pp. 461 - 467
2015
Gaspers S; Naroditskiy V; Narodytska N; Walsh T, 2014, 'Possible and Necessary Winner Problem in Social Polls (extended abstract)', in Gini ML; Shehory O; Ito T; Jonker CM (eds.), 12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013, IFAAMAS, Saint Paul, pp. 1131 - 1132, presented at roceedings of the 2013 international conference on Autonomous agents and multi-agent system, Saint Paul, 06 May 2014 - 10 May 2014, http://dl.acm.org/citation.cfm?id=2484920
2014
Gaspers S; Misra N; Ordyniak S; Szeider S; Živný S, 2014, 'Backdoors into heterogeneous classes of SAT and CSP', in Proceedings of the National Conference on Artificial Intelligence, pp. 2652 - 2658
2014
Gaspers S; Naroditskiy V; Narodytska N; Walsh T, 2014, 'Possible and necessary winner problem in social polls', in 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014, pp. 613 - 620
2014
Gaspers S; Misra N; Ordyniak S; Szeider S; Zivny S, 2014, 'Backdoors into Heterogeneous Classes of SAT and CSP', in PROCEEDINGS OF THE TWENTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE, Quebec City, CANADA, pp. 2652 - 2658, presented at 28th AAAI Conference on Artificial Intelligence, Quebec City, CANADA, 27 July 2014 - 31 July 2014, http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000485439702090&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=891bb5ab6ba270e68a29b250adbe88d1
2014
Aziz H; Gaspers S; Mackenzie S; Walsh T, 2014, 'Fair Assignment Of Indivisible Objects Under Ordinal Preferences', in AAMAS'14: PROCEEDINGS OF THE 2014 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS, ASSOC COMPUTING MACHINERY, Paris, FRANCE, pp. 1305 - 1312, presented at International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Paris, FRANCE, 05 May 2014 - 09 May 2014, http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000465207100167&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=891bb5ab6ba270e68a29b250adbe88d1
2014
Aziz H; Gaspers S; Mackenzie S; Mattei N; Stursberg P; Walsh T, 2014, 'Fixing a balanced knockout tournament', in Proceedings of the National Conference on Artificial Intelligence, pp. 552 - 558
2014
Aziz H; Gaspers S; Mackenzie S; Walsh T, 2014, 'Fair assignment of indivisible objects under ordinal preferences', in 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014, pp. 1305 - 1312
2014
Gaspers S; Szeider S, 2013, 'Strong Backdoors to Bounded Treewidth SAT', in Reingold O (ed.), Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, Berkeley, CA, USA, pp. 489 - 498, presented at FOCS 2013: 54th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, USA, 27 October 2013 - 29 October 2013, http://dx.doi.org/10.1109/FOCS.2013.59
2013
Gaspers S; Ordyniak S; Ramanujan MS; Saurabh S; Szeider S, 2013, 'Backdoors to q-Horn', in Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 67 - 79, presented at 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Dagstuhl, Germany, 27 February 2013 - 02 March 2013, http://dx.doi.org/10.4230/LIPIcs.STACS.2013.67
2013
Gaspers S; Kalinowski T; Narodytska N; Walsh T, 2013, 'Coalitional manipulation for Schulze's rule.', in Gini ML; Shehory O; Ito T; Jonker CM (eds.), AAMAS, IFAAMAS, pp. 431 - 438, presented at International conference on Autonomous Agents and Multi-Agent Systems, AAMAS '13, Saint Paul, MN, USA, May 6-10, 2013, http://dl.acm.org/citation.cfm?id=2484920
2013
van Bevern R; Fellows MR; Gaspers S; Rosamond FA, 2013, 'Myhill-Nerode Methods for Hypergraphs', in Algorithms and Computation, Springer, pp. 372 - 382, presented at ISAAC 2013: 24th Annual International Symposium on Algorithms and Computation, 16 December 2013 - 18 December 2013, http://dx.doi.org/10.1007/978-3-642-45030-3_35
2013
Gaspers S; Koivisto M; Liedloff M; Ordyniak S; Szeider S, 2013, 'On Finding Optimal Polytrees', in Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI Press, Bellevue, WAshington, USA, pp. 750 - 756, presented at Twenty-Seventh Conference on Artificial Intelligence (AAAI-13), Bellevue, WAshington, USA, 14 July 2013 - 18 July 2013, https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/4927/5266
2013
Gaspers S; Kim EJ; Ordyniak S; Saurabh S; Szeider S, 2013, 'Don't Be Strict in Local Search!', in Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI Press, Bellevue, WAshington, USA, pp. 486 - 492, presented at Twenty-Seventh Conference on Artificial Intelligence (AAAI-13), Bellevue, WAshington, USA, 14 July 2013 - 18 July 2013, https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/4929/5228
2013
Aziz H; Gaspers S; Mattei N; Narodytska N; Walsh T, 2013, 'Ties matter: Complexity of manipulation when tie-breaking with a random vote', in desJardins, M; Littman M (ed.), Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013, Bellevue, Washington, USA, pp. 74 - 80, presented at 27th AAAI Conference on Artificial Intelligence, AAAI 2013, Bellevue, Washington, USA, 14 July 2013 - 18 July 2013, http://dblp.uni-trier.de/db/conf/aaai/aaai2013.html#AzizGMNW13
2013
Chu G; Gaspers S; Narodytska N; Schutt A; Walsh T, 2013, 'On the complexity of global scheduling constraints under structural restrictions', in IJCAI International Joint Conference on Artificial Intelligence, pp. 503 - 509
2013
Frati F; Gaspers S; Gudmundsson J; Mathieson L, 2013, 'Augmenting Graphs to Minimize the Diameter', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 383 - 393, presented at ISAAC 2013: 24th Annual International Symposium on Algorithms and Computation, 16 December 2013 - 18 December 2013, http://dx.doi.org/10.1007/978-3-642-45030-3_36
2013
Fomin FV; Gaspers S; Fomin FV; Suchan K; Szeider S; van Leeuwen EJ; Vatshelle M; Villanger Y, 2012, 'k-Gap Interval Graphs', in Proceedings of the 10th Latin American Symposium on Theoretical Informatics, Springer, Berlin, pp. 350 - 361, presented at 10th Latin American Symposium on Theoretical Informatics, Arequipa, Peru, 16 April 2012 - 20 April 2012, http://dx.doi.org/10.1007/978-3-642-29344-3_30
2012
Gaspers S; Szeider S, 2012, 'Backdoors to Acyclic SAT', in Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), LNCS 7391, Springer, Warwick, UK, pp. 363 - 374, presented at International Colloquium on Automata, Languages and Programming, Warwick, UK, 09 July 2012 - 13 July 2012, http://dx.doi.org/10.1007/978-3-642-31594-7_31
2012
Gaspers S; Szeider S, 2012, 'Strong backdoors to nested satisfiability', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7317 LNCS, Springer Verlag, Trento, Italy, pp. 72 - 85, presented at 15th International Conference on Theory and Applications of Satisfiability Testing, SAT 2012, Trento, Italy, 17 June 2012 - 20 June 2012, http://dx.doi.org/10.1007/978-3-642-31612-8_7
2012
Gaspers S; Szeider S, 2011, 'The parameterized complexity of local consistency', in Lee JH-M (ed.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 302 - 316, presented at Principles and Practice of Constraint Programming - CP 2011 - 17th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011. Proceedings, http://dx.doi.org/10.1007/978-3-642-23786-7_24
2011
Gaspers S; Szeider S, 2011, 'Kernels for global constraints', in IJCAI International Joint Conference on Artificial Intelligence, pp. 540 - 545, http://dx.doi.org/10.5591/978-1-57735-516-8/IJCAI11-098
2011
Gaspers S; Liedloff M; Stein M; Suchan K, 2011, 'Complexity of splits reconstruction for low-degree trees', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 167 - 178, http://dx.doi.org/10.1007/978-3-642-25870-1_16
2011
Fellows MR; Gaspers S; Rosamond FA, 2010, 'Parameterizing by the number of numbers', in Raman V; Saurabh S (eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 123 - 134, presented at Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings, http://dx.doi.org/10.1007/978-3-642-17493-3_13
2010
Fernau H; Gaspers S; Raible D, 2010, 'Exact and parameterized algorithms for max internal spanning tree', in Paul C; Habib M (eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 100 - 111, presented at Graph-Theoretic Concepts in Computer Science, 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers, http://dx.doi.org/10.1007/978-3-642-11409-0_9
2010
Gaspers S; Mnich M, 2010, 'Feedback vertex sets in tournaments', in Berg MD; Meyer U (eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 267 - 277, presented at Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I, http://dx.doi.org/10.1007/978-3-642-15775-2_23
2010
Fernau H; Gaspers S; Kratsch D; Liedloff M; Raible D, 2009, 'Exact exponential-time algorithms for finding bicliques in a graph', in Cafieri S; Mucherino A; Nannicini G; Tarissan F; Liberti L (eds.), 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2009 - Proceedings of the Conference, pp. 205 - 209, presented at Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2009, Paris, France, June 2-4 2009, http://www.lix.polytechnique.fr/ctw09/ctw09-proceedings.pdf
2009
Bessy S; Fomin FV; Gaspers S; Paul C; Perez A; Saurabh S; Thomasse S, 2009, 'Kernels for feedback arc set in tournaments', in Kannan R; Kumar KN (eds.), Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 37 - 47, presented at IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15-17, 2009, IIT Kanpur, India, http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2305
2009
Gaspers S; Sorkin GB, 2009, 'A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between', in Mathieu C (ed.), Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp. 606 - 615, presented at Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, http://dx.doi.org/10.1137/1.9781611973068.67
2009
Fomin FV; Gaspers S; Saurabh S; Thomassé S, 2009, 'A linear vertex kernel for Maximum Internal Spanning Tree', in Dong Y; Du D-Z; Ibarra OH (eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 275 - 282, presented at Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, http://dx.doi.org/10.1007/978-3-642-10631-6_29
2009
Fürer M; Gaspers S; Kasiviswanathan SP, 2009, 'An exponential time 2-approximation algorithm for bandwidth', in Chen J; Fomin FV (eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 173 - 184, presented at Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers, http://dx.doi.org/10.1007/978-3-642-11269-0_14
2009
Gaspers S; Kratsch D; Liedloff M, 2008, 'On independent sets and bicliques in graphs', in Broersma H; Erlebach T; Friedetzky T; Paulusma D (eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 171 - 182, presented at Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30 - July 2, 2008. Revised Papers, http://dx.doi.org/10.1007/978-3-540-92248-3_16
2008
Gaspers S; Saurabh S; Stepanov AA, 2008, 'A moderately exponential time algorithm for full degree spanning tree', in Agrawal M; Du D-Z; Duan Z; Li A (eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 479 - 489, presented at Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi'an, China, April 25-29, 2008. Proceedings, http://dx.doi.org/10.1007/978-3-540-79228-4_42
2008
Fomin FV; Gaspers S; Kratsch D; Liedloff M; Saurabh S, 2008, 'Iterative compression and exact algorithms', in Ochmanski E; Tyszkiewicz J (eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 335 - 346, presented at Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings, http://dx.doi.org/10.1007/978-3-540-85238-4_27
2008
Fomin FV; Gaspers S; Saurabh S, 2007, 'Improved exact algorithms for counting 3- and 4-colorings', in Lin G (ed.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 65 - 74, presented at Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings, http://dx.doi.org/10.1007/978-3-540-73545-8_9
2007
Gaspers S; Liedloff M, 2006, 'A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs', in Fomin FV (ed.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 78 - 89, presented at Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers, http://dx.doi.org/10.1007/11917496_8
2006
Fomin FV; Gaspers S; Pyatkin AV, 2006, 'Finding a minimum feedback vertex set in time O(1.7548n)', in Bodlaender HL; Langston MA (eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 184 - 191, presented at Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings, http://dx.doi.org/10.1007/11847250_17
2006
Gaspers S; Kratsch D; Liedloff M, 2006, 'Exponential time algorithms for the minimum dominating set problem on some graph classes', in Arge L; Freivalds R (eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 148 - 159, presented at Algorithm Theory - SWAT 2006, 10th ScandinavianWorkshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006, Proceedings, http://dx.doi.org/10.1007/11785293_16
2006
Fomin FV; Gaspers S; Saurabh S, 2006, 'Branching and treewidth based exact algorithms', in Asano T (ed.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, pp. 16 - 25, presented at Algorithms and Computation, 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings, http://dx.doi.org/10.1007/11940128_4
2006
Reports
add
Aziz H; Gaspers S; Sun Z; Walsh T, 2020, From Matching with Diversity Constraints to Matching with Regional Quotas.
2020
Gaspers S; Huang S; Paulusma D, 2019, Colouring square-free graphs without long induced paths, http://dx.doi.org/10.1016/j.jcss.2019.06.002
2019
Gaspers S; Lau J, 2018, Minimizing and Computing the Inverse Geodesic Length on Trees.
2018
Gaspers S; Lee EJ, 2017, Exact algorithms via multivariate subroutines, http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.69
2017
Gaspers S; Lee EJ, 2017, Faster Graph Coloring in Polynomial Space, http://dx.doi.org/10.1007/978-3-319-62389-4_31
2017
Cochefert M; Couturier JF; Gaspers S; Kratsch D, 2016, Faster algorithms to enumerate hypergraph transversals, http://dx.doi.org/10.1007/978-3-662-49529-2_23
2016
Gaspers S; Mackenzie S, 2016, On the number of minimal separators in graphs, http://dx.doi.org/10.1007/978-3-662-53174-7_9
2016
Fomin FV; Gaspers S; Lokshtanov D; Saurabh S, 2016, Exact algorithms via monotone local search, http://dx.doi.org/10.1145/2897518.2897551
2016
Aziz H; Gaspers S; Gudmundsson J; Mackenzie S; Mattei N; Walsh T, 2015, Computational aspects of multi-winner approval voting
2015
Aziz H; Gaspers S; Mackenzie S; Mattei N; Narodytska N; Walsh T, 2015, Manipulating the probabilistic serial rule
2015
Gaspers S; Sorkin GB, 2015, Separate, measure and conquer: Faster polynomial-space algorithms for max 2-CSP and counting dominating sets, http://dx.doi.org/10.1007/978-3-662-47672-7_46
2015
Aziz H; Gaspers S; Mackenzie S; Mattei N; Narodytska N; Walsh T, 2015, Equilibria under the probabilistic serial rule
2015
Aleksandrov M; Aziz H; Gaspers S; Walsh T, 2015, Online fair division: Analysing a food bank problem
2015
Gaspers S; Kalinowski T; Narodytska N; Walsh T, 2013, Coalitional Manipulation for Schulze’s Rule
2013
Van Bevern R; Fellows MR; Gaspers S; Rosamond FA, 2013, Myhill-Nerode methods for hypergraphs, http://dx.doi.org/10.1007/978-3-642-45030-3_35
2013
Gaspers S; Szeider S, 2012, Strong Backdoors to Nested Satisfiability
2012
Gaspers S; Liedloff M, 2012, A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set, DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE, http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000303375100003&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=891bb5ab6ba270e68a29b250adbe88d1
2012
Gaspers S; Szeider S, 2011, The Parameterized Complexity of Local Consistency.
2011
Gaspers S; Szeider S, 2011, Kernels for Global Constraints
2011
Gaspers S; Mnich M, 2009, On Feedback Vertex Sets in Tournaments
2009
Gaspers S; Sorkin GB, 2009, A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
2009
Fernau H; Gaspers S; Raible D, Exact Exponential Time Algorithms for Max Internal Spanning Tree, http://arxiv.org/abs/0811.1875v3
Aziz H; Gaspers S; Mattei N; Narodytska N; Walsh T, Strategic aspects of the probabilistic serial rule for the allocation of goods, http://arxiv.org/abs/1401.6523v1
Abu-Khzam FN; Egan J; Gaspers S; Shaw A; Shaw P, On the Parameterized Cluster Editing with Vertex Splitting Problem, http://arxiv.org/abs/1901.00156v1
Gaspers S, From edge-disjoint paths to independent paths, http://arxiv.org/abs/1203.4483v1
Conference Proceedings (Editor of)
add
Gaspers S; Walsh T, (ed.), 2017, 'Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings', Springer, Vol. 10491
2017
Book Chapters
add
Gaspers S; Ordyniak S; Szeider S, 2017, 'Backdoor Sets for CSP', in The Constraint Satisfaction Problem: Complexity and Approximability, edn. Dagstuhl Follow-Ups, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 137 - 157, http://dx.doi.org/10.4230/DFU.Vol7.15301.5
2017
Gaspers S; Walsh T, 2017, 'Preface', in Theory and Applications of Satisfiability Testing – SAT 2017, Springer International Publishing, pp. V - VIII
2017
Gaspers S, 2016, 'Backdoors to SAT.', in Encyclopedia of Algorithms, edn. 2008, Springer Science & Business Media, pp. 167 - 170, http://dx.doi.org/10.1007/978-1-4939-2864-4_781
2016
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
2012
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
2011
Working Papers
add
2017
Gaspers S; Gudmundsson J; Mestre J; Rümmele S, 2017, Barrier coverage with non-uniform lengths to minimize aggregate movements, http://dx.doi.org10.4230/LIPIcs.ISAAC.2017.37
2017
Aziz H; Gaspers S; Mackenzie S; Mattei N; Stursberg P; Walsh T, 2014, Fixing a balanced knockout tournament, http://dx.doi.org
2014
Aziz H; Gaspers S; Gudmundsson J; Mackenzie S; Mattei N; Walsh T, 2014, Computational aspects of Multi-Winner approval voting, http://dx.doi.org
2014
Books
add
Gaspers S, 2010, Exponential Time Algorithms - Structures, Measures, and Bounds., VDM
2010
  • ARC Future Fellowship 2014
  • IJCAI 2013 Most Educational Video Award
  • ARC Discovery Early Career Researcher Award (DECRA) 2012
  • UNSW Vice-Chancellor’s Postdoctoral Research Fellowship 2012 (declined to take up the DECRA instead)
  • ARC Discovery Project for the project DP210103849 "Improved algorithms via random sampling" (with Fedor Fomin and Daniel Lokshtanov), A$ 435,346 (2021–2023)
  • Data61, CSIRO / UNSW Collaborative Research Project on the Computational Complexity of Resource Allocation Problems (with Toby Walsh and Haris Aziz), A$ 198,847 (2016–2018)
  • ARC Discovery Project for the project DP150101134 "Local reoptimization for turbocharging heuristics" (with Joachim Gudmundsson, Michael R Fellows, Julian Mestre, and Fedor Fomin), A$ 355,100 (2015–2017)
  • ARC Future Fellowship for the project FT140100048 “Algorithms for hard graph problems based on auxiliary data”, A$ 711,489 (2014–2018)
  • NICTA / UNSW Collaborative Research Project on the Computational Complexity of Resource Allocation Problems (with Toby Walsh), A$ 379,038 (2012–2016)
  • ARC Discovery Early Career Researcher Award (DECRA) for the project DE120101761 “Solving intractable problems: from practice to theory and back”, A$ 375,000 (2012–2014)

I designed and teach COMP6741 - Algorithms for intractable problems.

I am the academic lead for the GraphAbility Vertically Integrated Project.

I am also a lecturer for COMP3121 - Algorithms and Programming Techniques.