By Professor Serge Gaspers

Conference Papers

Gaspers S; Naroditskiy V; Narodytska N; Walsh T, 2014, 'Possible and Necessary Winner Problem in Social Polls (extended abstract)', Saint Paul, 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=2485106

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, FRANCE, Paris, pp. 1305 - 1312, presented at International Conference on Autonomous Agents and Multiagent Systems (AAMAS), FRANCE, Paris, 05 May 2014 - 09 May 2014, https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000465207100167&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=891bb5ab6ba270e68a29b250adbe88d1

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

Aziz H; Gaspers S; Mackenzie S; Walsh T, 2014, 'Fair assignment of indivisible objects under ordinal preferences', in Bazzan ALC; Huhns MN; Lomuscio A; Scerri P (eds.), 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014, Elsevier, pp. 1305 - 1312, http://dx.doi.org/10.1016/j.artint.2015.06.002

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

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

Frati F; Gaspers S; Gudmundsson J; Mathieson L, 2013, 'Augmenting Graphs to Minimize the Diameter', 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

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

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

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, presented at FOCS 2013: 54th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, USA, 27 October 2013 - 29 October 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

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

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

Gaspers S; Ordyniak S; Ramanujan MS; Saurabh S; Szeider S, 2013, 'Backdoors to q-Horn', 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

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, http://dl.acm.org/citation.cfm?id=2484920

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

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

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

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

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

Gaspers S; Szeider S, 2011, 'The parameterized complexity of local consistency', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 302 - 316, http://dx.doi.org/10.1007/978-3-642-23786-7_24

Fellows MR; Gaspers S; Rosamond FA, 2010, 'Parameterizing by the number of numbers', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 123 - 134, http://dx.doi.org/10.1007/978-3-642-17493-3_13

Gaspers S; Mnich M, 2010, 'Feedback vertex sets in tournaments', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 267 - 277, http://dx.doi.org/10.1007/978-3-642-15775-2_23

Fernau H; Gaspers S; Raible D, 2010, 'Exact and parameterized algorithms for max internal spanning tree', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 100 - 111, http://dx.doi.org/10.1007/978-3-642-11409-0_9

Fürer M; Gaspers S; Kasiviswanathan SP, 2009, 'An exponential time 2-approximation algorithm for bandwidth', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 173 - 184, http://dx.doi.org/10.1007/978-3-642-11269-0_14

Fomin FV; Gaspers S; Saurabh S; Thomassé S, 2009, 'A linear vertex kernel for Maximum Internal Spanning Tree', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 275 - 282, http://dx.doi.org/10.1007/978-3-642-10631-6_29

Bessy S; Fomin FV; Gaspers S; Paul C; Perez A; Saurabh S; Thomasse S, 2009, 'Kernels for feedback arc set in tournaments', in Leibniz International Proceedings in Informatics, LIPIcs, pp. 37 - 47, http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2305

Gaspers S; Sorkin GB, 2009, 'A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between', in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 606 - 615, http://dx.doi.org/10.1137/1.9781611973068.67

Fernau H; Gaspers S; Kratsch D; Liedloff M; Raible D, 2009, 'Exact exponential-time algorithms for finding bicliques in a graph', in 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2009 - Proceedings of the Conference, pp. 205 - 209

Gaspers S; Kratsch D; Liedloff M, 2008, 'On independent sets and bicliques in graphs', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 171 - 182, http://dx.doi.org/10.1007/978-3-540-92248-3_16

Fomin FV; Gaspers S; Kratsch D; Liedloff M; Saurabh S, 2008, 'Iterative compression and exact algorithms', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 335 - 346, http://dx.doi.org/10.1007/978-3-540-85238-4_27

Gaspers S; Saurabh S; Stepanov AA, 2008, 'A moderately exponential time algorithm for full degree spanning tree', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 479 - 489, http://dx.doi.org/10.1007/978-3-540-79228-4_42

Fomin FV; Gaspers S; Saurabh S, 2007, 'Improved exact algorithms for counting 3- and 4-colorings', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 65 - 74, http://dx.doi.org/10.1007/978-3-540-73545-8_9

Fomin FV; Gaspers S; Saurabh S, 2006, 'Branching and treewidth based exact algorithms', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 16 - 25, http://dx.doi.org/10.1007/11940128_4

Gaspers S; Liedloff M, 2006, 'A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 78 - 89, http://dx.doi.org/10.1007/11917496_8

Gaspers S; Kratsch D; Liedloff M, 2006, 'Exponential time algorithms for the minimum dominating set problem on some graph classes', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 148 - 159, http://dx.doi.org/10.1007/11785293_16

Fomin FV; Gaspers S; Pyatkin AV, 2006, 'Finding a minimum feedback vertex set in time O(1.7548ⁿ)', in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 184 - 191, http://dx.doi.org/10.1007/11847250_17

Conference Proceedings (Editor of)

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

Preprints

Clinch K; Gaspers S; He Z; Saffidine A; Zhang T, 2024, A Piecewise Approach for the Analysis of Exact Algorithms, http://arxiv.org/abs/2402.10015v3

Gaspers S; Li JZ, 2023, Quantum Algorithms for Graph Coloring and other Partitioning, Covering, and Packing Problems, http://arxiv.org/abs/2311.08042v1

Back to profile page