Serge Gaspers

Jump to Journal publications, publications in the proceedings of refereed Conferences, Technical Reports, or Theses

Journal

• Iterative Compression and Exact Algorithms (with Fedor V. Fomin, Dieter Kratsch, Mathieu Liedloff, and Saket Saurabh),
  submitted.
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree (with Saket Saurabh and Alexey A. Stepanov),
  submitted.
  [pdf]
• Parallel Cleaning of a Network with Brushes (with Margaret-Ellen Messinger, Pawel Pralat, and Richard J. Nowakowski),
  submitted.
  [pdf]
• Clean the Graph Before You Draw It! (with Margaret-Ellen Messinger, Pawel Pralat, and Richard J. Nowakowski),
  Information Processing Letters, to appear.
  [pdf]
• Exponential time algorithms for the minimum dominating set problem on some graph classes (with Dieter Kratsch, Mathieu Liedloff, and Ioan Todinca),
  ACM Transactions on Algorithms, to appear.
• On Two Techniques of Combining Branching and Treewidth (with Fedor V. Fomin, Saket Saurabh, and Alexey A. Stepanov)
  Algorithmica, to appear
  [pdf]
• On the minimum feedback vertex set problem: Exact and enumeration algorithms (with Fedor V. Fomin, Artem V. Pyatkin, and Igor Razgon)
  Algorithmica 52 (2008), pp. 293–307
  [pdf]

Conference Proceedings

• A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between (with Gregory B. Sorkin),
  SODA 2009: Proceedings of the 20th annual ACM-SIAM Symposium on Discrete Algorithms, to appear.
  [pdf]
• Iterative Compression and Exact Algorithms (with Fedor V. Fomin, Dieter Kratsch, Mathieu Liedloff, and Saket Saurabh),
  MFCS 2008: Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, Springer LNCS 5162, pp. 335 - 346.
  [pdf]
• On Independent Sets and Bicliques in Graphs (with Dieter Kratsch and Mathieu Liedloff),
  WG 2008: Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science, Springer LNCS 5344, pp. 171 - 182.
  [pdf]
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree (with Saket Saurabh and Alexey A. Stepanov),
  TAMC 2008: Proceedings of the 5th Annual Conference on Theory and Applications of Models of Computation, Springer LNCS 4978, pp. 479 - 489.
  see journal version above
• Improved Exact Algorithms for Counting 3- and 4-Colorings (with Fedor V. Fomin and Saket Saurabh),
  COCOON 2007: Proceedings of the 13th Annual International Computing and Combinatorics Conference, Springer LNCS 4598, pp. 65 - 74.
  [pdf]
• Branching and Treewidth Based Exact Algorithms (with Fedor V. Fomin and Saket Saurabh),
  ISAAC 2006: Proceedings of the 17th International Symposium on Algorithms and Computation, Springer LNCS 4288, pp. 16 - 25,
  received the Best Student Paper Award.
  see journal version above: On Two Techniques of Combining Branching and Treewidth
• Finding a Minimum Feedback Vertex Set in time O(1.7548ⁿ) (with Fedor V. Fomin and Artem V. Pyatkin),
  IWPEC 2006: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation, Springer LNCS 4169, pp. 184 - 191.
  see journal version above: On the minimum feedback vertex set problem: Exact and enumeration algorithms
• A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs (with Mathieu Liedloff),
  WG 2006: Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, Springer LNCS 4271, pp. 78 - 89.
• Exponential time algorithms for the minimum dominating set problem on some graph classes (with Dieter Kratsch and Mathieu Liedloff),
  SWAT 2006: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory, Springer LNCS 4059, pp. 148 - 159.

Technical Reports

• Exact Exponential Time Algorithms for Max Internal Spanning Tree (with Henning Fernau, Daniel Raible, and Alexey A. Stepanov),
  ArXiv Report CoRR abs/0811.1875 (2008).
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs (with Mathieu Liedloff),
  Report No 344, January 2007, Department of Informatics, University of Bergen, Bergen, Norway.
  [pdf]
• On Two Techniques of Combining Branching and Treewidth (with Fedor V. Fomin, Saket Saurabh, and Alexey A. Stepanov),
  Report No 337, December 2006, Department of Informatics, University of Bergen, Bergen, Norway.
  [pdf]
• Finding a Minimum Feedback Vertex Set in time O(1.7548ⁿ) (with Fedor V. Fomin and Artem V. Pyatkin),
  Report No 324, April 2006, Department of Informatics, University of Bergen, Bergen, Norway.
  [pdf]
• Exponential time algorithms for the minimum dominating set problem on some graph classes (with Dieter Kratsch and Mathieu Liedloff),
  Report No 322, April 2006, Department of Informatics, University of Bergen, Bergen, Norway.
  [pdf]

Theses

• Exponential Time Algorithms: Structures, Measures, and Bounds,
  PhD thesis, December 2008, University of Bergen, Norway, Advisor: Fedor V. Fomin, Committee: Thore Husfedt, Ryan Williams, Dag Haugland
  [pdf screen] [pdf print]
• Algorithmes exponentiels (in French),
  Master Thesis (DEA Informatique de Lorraine), June 2005, Ecole Doctorale IAEM Lorraine, Advisor: Dieter Kratsch, LITA, University of Metz, France.
  [pdf]
• Algorithmes pour le problème de domination d'un graphe (in French),
  Maîtrise Thesis (Maîtrise Informatique), June 2004, Advisor: Dieter Kratsch, LITA, University of Metz, France.
  [pdf]
• Création d'un Firewall (in French),
  Mémoire de fin d'études (DUT en Informatique), June 2002, Advisor: Paul Yans, Centre Universitaire de Luxembourg, Luxembourg.
  [pdf]