Serge Gaspers

According to our database, Serge Gaspers authored at least 103 papers between 2006 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

A Piecewise Approach for the Analysis of Exact Algorithms.

Katie Clinch, Serge Gaspers, Abdallah Saffidine, Tiankuang Zhang

CoRR, 2024

Quantum Algorithms for Graph Coloring and Other Partitioning, Covering, and Packing Problems.

Serge Gaspers, Jerry Zirui Li

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Blockchain-Enabled Private and Secure Task Allocation Framework.

Ayda Valinezhad Orang, Ali Dorri, Serge Gaspers, Sushmita Ruj

Proceedings of the 16th International Conference on COMmunication Systems & NETworkS, 2024

2023

Faster Graph Coloring in Polynomial Space.

Serge Gaspers, Edward J. Lee

Algorithmica, February, 2023

2022

Stable matching with uncertain pairwise preferences.

Haris Aziz, Péter Biró, Tamás Fleiner, Serge Gaspers, Ronald de Haan, Nicholas Mattei, Baharak Rastegari

Theor. Comput. Sci., 2022

Making the Most of Parallel Composition in Differential Privacy.

Josh Smith, Hassan Jameel Asghar, Gianpaolo Gioiosa, Sirine Mrabet, Serge Gaspers, Paul Tyler

Proc. Priv. Enhancing Technol., 2022

Faster Algorithms for Weak Backdoors.

Serge Gaspers, Andrew Kaploun

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021

On the Complexity of the Smallest Grammar Problem over Fixed Alphabets.

Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid

Theory Comput. Syst., 2021

2020

Stable Matching with Uncertain Linear Preferences.

Haris Aziz, Péter Biró, Serge Gaspers, Ronald de Haan, Nicholas Mattei, Baharak Rastegari

Algorithmica, 2020

Mechanism Design for School Choice with Soft Diversity Constraints.

Haris Aziz, Serge Gaspers, Zhaohong Sun

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 2020

Multiple Levels of Importance in Matching with Distributional Constraints: Extended Abstract.

Haris Aziz, Serge Gaspers, Zhaohong Sun, Makoto Yokoo

Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, 2020

2019

(2P_{2, K₄₎}-Free Graphs are 4-Colorable.

Serge Gaspers, Shenwei Huang

SIAM J. Discret. Math., 2019

Linearly χ-bounding (P6, C4)-free graphs.

Serge Gaspers, Shenwei Huang

J. Graph Theory, 2019

Colouring square-free graphs without long induced paths.

Serge Gaspers, Shenwei Huang, Daniël Paulusma

J. Comput. Syst. Sci., 2019

Exact Algorithms via Monotone Local Search.

Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh

J. ACM, 2019

On the Parameterized Cluster Editing with Vertex Splitting Problem.

Faisal N. Abu-Khzam, Judith Egan, Serge Gaspers, Alexis Shaw, Peter Shaw

CoRR, 2019

Turbocharging Treewidth Heuristics.

Serge Gaspers, Joachim Gudmundsson, Mitchell Jones, Julián Mestre, Stefan Rümmele

Algorithmica, 2019

Enumeration of Preferred Extensions in Almost Oriented Digraphs.

Serge Gaspers, Ray Li

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Minimizing and Computing the Inverse Geodesic Length on Trees.

Serge Gaspers, Joshua Lau

Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

Fair Online Allocation of Perishable Goods and its Application to Electric Vehicle Charging.

Enrico H. Gerding, Alvaro Perez-Diaz, Haris Aziz, Serge Gaspers, Antonia Marcu, Nicholas Mattei, Toby Walsh

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019

From Matching with Diversity Constraints to Matching with Regional Quotas.

Haris Aziz, Serge Gaspers, Zhaohong Sun, Toby Walsh

Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019

Optimal Surveillance of Covert Networks by Minimizing Inverse Geodesic Length.

Serge Gaspers, Kamran Najeebullah

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018

On the number of minimal separators in graphs.

Serge Gaspers, Simon Mackenzie

J. Graph Theory, 2018

A note on the eternal dominating set problem.

Stephen Finbow, Serge Gaspers, Margaret-Ellen Messinger, Paul Ottaway

Int. J. Game Theory, 2018

Fixing balanced knockout and double elimination tournaments.

Haris Aziz, Serge Gaspers, Simon Mackenzie, Nicholas Mattei, Paul Stursberg, Toby Walsh

Artif. Intell., 2018

When is Red-Blue Nonblocker Fixed-Parameter Tractable?

Serge Gaspers, Joachim Gudmundsson, Michael Horton, Stefan Rümmele

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

Cluster Editing with Vertex Splitting.

Faisal N. Abu-Khzam, Judith Egan, Serge Gaspers, Alexis Shaw, Peter Shaw

Proceedings of the Combinatorial Optimization - 5th International Symposium, 2018

Defender Stackelberg Game with Inverse Geodesic Length as Utility Metric.

Haris Aziz, Serge Gaspers, Edward J. Lee, Kamran Najeebullah

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018

Stability and Pareto Optimality in Refugee Allocation Matchings.

Haris Aziz, Jiayin Chen, Serge Gaspers, Zhaohong Sun

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018

Minesweeper with Limited Moves.

Serge Gaspers, Stefan Rümmele, Abdallah Saffidine, Kevin Tran

Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

2017

Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets.

Serge Gaspers, Gregory B. Sorkin

ACM Trans. Algorithms, 2017

Backdoors into heterogeneous classes of SAT and CSP.

Serge Gaspers, Neeldhara Misra, Sebastian Ordyniak, Stefan Szeider, Stanislav Zivný

J. Comput. Syst. Sci., 2017

Linearly $χ$-Bounding $(P_6, C_4)$-Free Graphs.

Serge Gaspers, Shenwei Huang

CoRR, 2017

Linearly \chi χ -Bounding (P_6, C_4) ( P 6 , C 4 ) -Free Graphs.

Serge Gaspers, Shenwei Huang

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2017

Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements.

Serge Gaspers, Joachim Gudmundsson, Julián Mestre, Stefan Rümmele

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

Weakening Covert Networks by Minimizing Inverse Geodesic Length.

Haris Aziz, Serge Gaspers, Kamran Najeebullah

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017

Exact Algorithms via Multivariate Subroutines.

Serge Gaspers, Edward J. Lee

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

The Parameterized Complexity of Positional Games.

Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, Abdallah Saffidine

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Backdoor Sets for CSP.

Serge Gaspers, Sebastian Ordyniak, Stefan Szeider

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016

Backdoors to SAT.

Serge Gaspers

Encyclopedia of Algorithms, 2016

Backdoors to q-Horn.

Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, Stefan Szeider

Algorithmica, 2016

Faster Algorithms to Enumerate Hypergraph Transversals.

Manfred Cochefert, Jean-François Couturier, Serge Gaspers, Dieter Kratsch

Proceedings of the LATIN 2016: Theoretical Informatics, 2016

On Satisfiability Problems with a Linear Structure.

Serge Gaspers, Christos H. Papadimitriou, Sigve Hortemo Sæther, Jan Arne Telle

Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

Interdependent Scheduling Games.

Andrés Abeliuk, Haris Aziz, Gerardo Berbeglia, Serge Gaspers, Petr Kalina, Nicholas Mattei, Dominik Peters, Paul Stursberg, Pascal Van Hentenryck, Toby Walsh

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016

On the Complexity of Grammar-Based Compression over Fixed Alphabets.

Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

On finding optimal polytrees.

Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, Stefan Szeider

Theor. Comput. Sci., 2015

Two desirable fairness concepts for allocation of indivisible objects under ordinal preferences.

Haris Aziz, Serge Gaspers, Simon Mackenzie, Toby Walsh

SIGecom Exch., 2015

Complexity of splits reconstruction for low-degree trees.

Serge Gaspers, Mathieu Liedloff, Maya Jakobine Stein, Karol Suchan

Discret. Appl. Math., 2015

Augmenting Graphs to Minimize the Diameter.

Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson, Luke Mathieson

Algorithmica, 2015

Myhill-Nerode Methods for Hypergraphs.

René van Bevern, Rodney G. Downey, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond

Algorithmica, 2015

Fair assignment of indivisible objects under ordinal preferences.

Haris Aziz, Serge Gaspers, Simon Mackenzie, Toby Walsh

Artif. Intell., 2015

Equilibria Under the Probabilistic Serial Rule.

Haris Aziz, Serge Gaspers, Simon Mackenzie, Nicholas Mattei, Nina Narodytska, Toby Walsh

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Welfare Maximization in Fractional Hedonic Games.

Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Julián Mestre, Hanjo Täubig

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Online Fair Division: Analysing a Food Bank Problem.

Martin Aleksandrov, Haris Aziz, Serge Gaspers, Toby Walsh

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Manipulating the Probabilistic Serial Rule.

Haris Aziz, Serge Gaspers, Simon Mackenzie, Nicholas Mattei, Nina Narodytska, Toby Walsh

Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, 2015

2014

Separate, Measure and Conquer: Faster Algorithms for Max 2-CSP and Counting Dominating Sets.

Serge Gaspers, Gregory B. Sorkin

CoRR, 2014

Strategic aspects of the probabilistic serial rule for the allocation of goods.

Haris Aziz, Serge Gaspers, Nicholas Mattei, Nina Narodytska, Toby Walsh

CoRR, 2014

Guarantees and limits of preprocessing in constraint satisfaction and reasoning.

Serge Gaspers, Stefan Szeider

Artif. Intell., 2014

Fixing a Balanced Knockout Tournament.

Haris Aziz, Serge Gaspers, Simon Mackenzie, Nicholas Mattei, Paul Stursberg, Toby Walsh

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014

Computational Aspects of Multi-Winner Approval Voting.

Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, Toby Walsh

Proceedings of the Multidisciplinary Workshop on Advances in Preference Handling, 2014

2013

An exponential time 2-approximation algorithm for bandwidth.

Martin Fürer, Serge Gaspers, Shiva Prasad Kasiviswanathan

Theor. Comput. Sci., 2013

Feedback Vertex Sets in Tournaments.

Serge Gaspers, Matthias Mnich

J. Graph Theory, 2013

A linear vertex kernel for maximum internal spanning tree.

Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Stéphan Thomassé

J. Comput. Syst. Sci., 2013

Exact and Parameterized Algorithms for Max Internal Spanning Tree.

Daniel Binkele-Raible, Henning Fernau, Serge Gaspers, Mathieu Liedloff

Algorithmica, 2013

Myhill-Nerode Methods for Hypergraphs.

René van Bevern, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

On the Complexity of Global Scheduling Constraints under Structural Restrictions.

Geoffrey Chu, Serge Gaspers, Nina Narodytska, Andreas Schutt, Toby Walsh

Proceedings of the IJCAI 2013, 2013

Strong Backdoors to Bounded Treewidth SAT.

Serge Gaspers, Stefan Szeider

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Possible and necessary winner problem in social polls.

Serge Gaspers, Victor Naroditskiy, Nina Narodytska, Toby Walsh

Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2013

Coalitional manipulation for Schulze's rule.

Serge Gaspers, Thomas Kalinowski, Nina Narodytska, Toby Walsh

Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2013

Ties Matter: Complexity of Manipulation when Tie-Breaking with a Random Vote.

Haris Aziz, Serge Gaspers, Nicholas Mattei, Nina Narodytska, Toby Walsh

Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013

2012

Parameterizing by the Number of Numbers.

Michael R. Fellows, Serge Gaspers, Frances A. Rosamond

Theory Comput. Syst., 2012

A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between.

Serge Gaspers, Gregory B. Sorkin

J. Comput. Syst. Sci., 2012

A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set.

Serge Gaspers, Mathieu Liedloff

Discret. Math. Theor. Comput. Sci., 2012

How applying Myhill-Nerode methods to hypergraphs helps mastering the Art of Trellis Decoding

René van Bevern, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond

CoRR, 2012

From edge-disjoint paths to independent paths

Serge Gaspers

CoRR, 2012

On Independent Sets and Bicliques in Graphs.

Serge Gaspers, Dieter Kratsch, Mathieu Liedloff

Algorithmica, 2012

Strong Backdoors to Nested Satisfiability.

Serge Gaspers, Stefan Szeider

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2012, 2012

k-Gap Interval Graphs.

Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle, Yngve Villanger

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Backdoors to Acyclic SAT.

Serge Gaspers, Stefan Szeider

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Backdoors to Satisfaction.

Serge Gaspers, Stefan Szeider

Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012

Don't Be Strict in Local Search!

Serge Gaspers, Eun Jung Kim, Sebastian Ordyniak, Saket Saurabh, Stefan Szeider

Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012

2011

Kernels for feedback arc set in tournaments.

Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, Stéphan Thomassé

J. Comput. Syst. Sci., 2011

The Parameterized Complexity of Local Consistency.

Serge Gaspers, Stefan Szeider

Electron. Colloquium Comput. Complex., 2011

Kernels for Global Constraints.

Serge Gaspers, Stefan Szeider

Proceedings of the IJCAI 2011, 2011

Multivariate Complexity Theory.

Michael R. Fellows, Serge Gaspers, Frances A. Rosamond

Proceedings of the Computer Science, The Hardware, Software and Heart of It, 2011

2010

Iterative compression and exact algorithms.

Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh

Theor. Comput. Sci., 2010

Parameterized algorithm for eternal vertex cover.

Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Dieter Kratsch, Saket Saurabh

Inf. Process. Lett., 2010

Exact exponential-time algorithms for finding bicliques.

Daniel Binkele-Raible, Henning Fernau, Serge Gaspers, Mathieu Liedloff

Inf. Process. Lett., 2010

Parallel cleaning of a network with brushes.

Serge Gaspers, Margaret-Ellen Messinger, Richard J. Nowakowski, Pawel Pralat

Discret. Appl. Math., 2010

Exponential Time Algorithms - Structures, Measures, and Bounds.

Serge Gaspers

VDM, ISBN: 978-3-639-21825-1, 2010

2009

Exponential time algorithms for the minimum dominating set problem on some graph classes.

Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Ioan Todinca

ACM Trans. Algorithms, 2009

Clean the graph before you draw it!

Serge Gaspers, Margaret-Ellen Messinger, Richard J. Nowakowski, Pawel Pralat

Inf. Process. Lett., 2009

On Two Techniques of Combining Branching and Treewidth.

Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Alexey A. Stepanov

Algorithmica, 2009

Exact and Parameterized Algorithms for Max Internal Spanning Tree.

Henning Fernau, Serge Gaspers, Daniel Raible

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2009

Exact Exponential-Time Algorithms for Finding Bicliques in a Graph.

Henning Fernau, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Daniel Raible

Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2009

2008

Exact Exponential Time Algorithms for Max Internal Spanning Tree

Henning Fernau, Daniel Raible, Serge Gaspers, Alexey A. Stepanov

CoRR, 2008

On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms.

Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin, Igor Razgon

Algorithmica, 2008

A Moderately Exponential Time Algorithm for Full Degree Spanning Tree.

Serge Gaspers, Saket Saurabh, Alexey A. Stepanov

Proceedings of the Theory and Applications of Models of Computation, 2008

2007

Improved Exact Algorithms for Counting 3- and 4-Colorings.

Fedor V. Fomin, Serge Gaspers, Saket Saurabh

Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006

A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs.

Serge Gaspers, Mathieu Liedloff

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes.

Serge Gaspers, Dieter Kratsch, Mathieu Liedloff

Proceedings of the Algorithm Theory, 2006

Finding a Minimum Feedback Vertex Set in Time <i>O</i> (1.7548^<i>n</i>).

Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin

Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006

Branching and Treewidth Based Exact Algorithms.

Fedor V. Fomin, Serge Gaspers, Saket Saurabh

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006