LIRMM  Université de Montpellier CNRS 

Ignasi Sau - Research
[Articles and preprints] [Book chapters] [Theses]
Articles and preprints
[Sorted from newer to older research, and not by publication date. Missing pdf's, if any, can be sent on demand]
[Journal and conference versions of the "same" article are merged. See my CV for separate lists of journals/conferences]

  1. Parameterized algorithms for thinness via the cluster module number.
    Flavia Bonomo, Eric Brandwein, and Ignasi Sau.
    • Short version currently under review.

  2. Kernelization dichotomies for hitting subgraphs under structural parameterizations.
    Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau.
    • Full version to be submitted soon.
    • Short version to appear in Proceedings of the 51st International Colloquium on Automata, Languages and Programming (ICALP), Tallinn, Estonia, July 2024.

  3. Dynamic programming on bipartite tree decompositions.
    Lars Jaffke, Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos.
    • Short version in Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC), volume 285 of LIPIcs, pages 26:1-26:22, Amsterdam, the Netherlands, September 2023.
    • Full version currently under review.

  4. On the complexity of the median and closest permutation problems.
    Luís Felipe I. Cunha, Ignasi Sau, and Uéverton S. Souza.
    • Short version currently under review.

  5. New Menger-like dualities in digraphs and applications to half-integral linkages.
    Victor A. Campos, Jonas Costa, Raul Lopes, and Ignasi Sau.
    • Full version currently under review.
    • Short version in Proceedings of the 31st Annual European Symposium on Algorithms (ESA), volume 274 of LIPIcs, pages 30:1-30:18, Amsterdam, the Netherlands, September 2023.

  6. Redicolouring digraphs: directed treewidth and cycle-degeneracy.
    Nicolas Nisse, Lucas Picasarri-Arrieta, and Ignasi Sau.
    • Full version currently under review.

  7. Faster parameterized algorithms for modification problems to minor-closed classes.
    Laure Morelle, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos.
    • Full version currently under review.
    • Short version in Proceedings of the 50th International Colloquium on Automata, Languages and Programming (ICALP), volume 261 of LIPIcs, pages 93:1-93:19, Paderborn, Germany, July 2023.

  8. Compound logics for modification problems.
    Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos.
    • Full version currently under review.
    • Short version in Proceedings of the 50th International Colloquium on Automata, Languages and Programming (ICALP), volume 261 of LIPIcs, pages 61:1-61:21, Paderborn, Germany, July 2023.

  9. Reducing the vertex cover number via edge contractions.
    Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, Uéverton S. Souza and Prafullkumar Tale.
    • Full version in Journal of Computer and System Sciences (JCSS), 136: 63–87, 2023.
    • Short version in Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 241 of LIPIcs, pages 69:1-69:14, Vienna, Austria, August 2022.

  10. FPT algorithms for packing k-safe spanning rooted sub(di)graphs.
    Stéphane Bessy, Florian Hörsch, Ana Karolinna Maia, Dieter Rautenbach, and Ignasi Sau.
    • Full version in Discrete Applied Mathematics (DAM), 346: 80-94, 2024.

  11. k-apices of minor-closed graph classes. II. Parameterized algorithms.
    Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos.
    • Full version in ACM Transactions on Algorithms (TALG), 18(3): 21, pp 1–30, 2022.
    • Short version (entitled "An FPT-algorithm for recognizing k-apices of minor-closed graph classes") in Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP), volume 168 of LIPIcs, pages 95:1-95:20, Saarbrücken, Germany (held online), July 2020.

  12. k-apices of minor-closed graph classes. I. Bounding the obstructions.
    Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos.
    • Full version in Journal of Combinatorial Theory, Series B (JCTB), 161: 180-227, 2023.
    • Short version (entitled "An FPT-algorithm for recognizing k-apices of minor-closed graph classes") in Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP), volume 168 of LIPIcs, pages 95:1-95:20, Saarbrücken, Germany (held online), July 2020. This is the same conference publication as in the above article.

  13. A more accurate view of the Flat Wall Theorem.
    Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos.
    • Full version to appear in Journal of Graph Theory (JGT).

  14. Parameterized complexity of computing maximum minimal blocking and hitting sets.
    Júlio Araújo, Marin Bougeret, Victor A. Campos, and Ignasi Sau.
    • Full version in Algorithmica, 85(2): 444-491, 2023.
    • Short version in the 10th Latin American Workshop on Cliques in Graphs (LAWCG), Curitiba, Brazil, October 2022.

  15. Introducing lop-kernels: a framework for kernelization lower bounds.
    Júlio Araújo, Marin Bougeret, Victor A. Campos, and Ignasi Sau.

  16. Target set selection with maximum activation time.
    Lucas Keiler, Carlos Vinícius G. C. Lima, Ana Karolinna Maia, Rudini Sampaio, and Ignasi Sau.
    • Full version in Discrete Applied Mathematics (DAM), 338: 199-217, 2023.
    • Short version in Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), volume 195 of Procedia Computer Science, pages 86-96, São Paulo, Brazil (held online), May 2021.

  17. Reducing graph transversals via edge contractions.
    Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, and Uéverton S. Souza.
    • Full version in Journal of Computer and System Sciences (JCSS), 120: 62-74, 2021.
    • Short version in Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 170 of LIPIcs, pages 64:1-64:15, Prague, Czech Republic (held online), August 2020.

  18. Hitting forbidden induced subgraphs on bounded treewidth graphs.
    Ignasi Sau and Uéverton S. Souza.
    • Full version in Information and Computation (I&C), 281: 104812, 2021.
    • Short version in Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 170 of LIPIcs, pages 82:1-82:15, Prague, Czech Republic (held online), August 2020.

  19. Coloring problems on bipartite graphs of small diameter.
    Victor A. Campos, Guilherme C. M. Gomes, Allen Ibiapina, Raul Lopes, Ignasi Sau, and Ana Silva.
    • Full version in Electronic Journal of Combinatorics (E-JC), 28(2): 2-14, 2021.

  20. On the complexity of finding large odd induced subgraphs and odd colorings.
    Rémy Belmonte and Ignasi Sau.
    • Full version in Algorithmica, 83(8): 2351-2373, 2021.
    • Short version in Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 12301 of LNCS, pages 67-79, Leeds, U.K. (held online), June 2020.

  21. A unifying model for locally constrained spanning tree problems.
    Luiz Alberto C. Viana, Manoel Campêlo, Ignasi Sau, and Ana Silva.
    • Full version in Journal of Combinatorial Optimization (JOCO), 42(1): 125-150, 2021.

  22. Hitting minors on bounded treewidth graphs. IV. An optimal algorithm.
    Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.

  23. A relaxation of the Directed Disjoint Paths problem: a global congestion metric helps.
    Raul Lopes and Ignasi Sau.
    • Full version in Theoretical Computer Science (TCS), 898: 75-91, 2022.
    • Short version in Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 170 of LIPIcs, pages 68:1-68:15, Prague, Czech Republic (held online), August 2020.

  24. Bridge-depth characterizes which minor-closed structural parameterizations of Vertex Cover admit a polynomial kernel.
    Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau.
    • Full version in SIAM Journal on Discrete Mathematics (SIDMA), 36(401): 2737-2773, 2022.
    • Short version in Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP), volume 168 of LIPIcs, pages 16:1-16:19, Saarbrücken, Germany (held online), July 2020.

  25. Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization.
    Guilherme C. M. Gomes and Ignasi Sau.
    • Full version in Algorithmica, 83(6): 1677-1706, 2021.
    • Short version in Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC), volume 148 of LIPIcs, pages 19:1-19:15, Munich, Germany, September 2019.

  26. Adapting the Directed Grid Theorem into an FPT algorithm.
    Victor A. Campos, Raul Lopes, Ana Karolinna Maia, and Ignasi Sau.
    • Full version in SIAM Journal on Discrete Mathematics (SIDMA), 36(3): 1887-1917, 2022.
    • Short version in Proceedings of the X Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), volume 346 of ENTCS, pages 229-240, Belo Horizonte, Brazil, June 2019.

  27. Hitting minors on bounded treewidth graphs. III. Lower bounds.
    Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in Journal of Computer and System Sciences (JCSS), 109: 56-77, 2020.
    • Some of these results appeared in the short versions of this series published in IPEC 2018 (see Part II) and SODA 2020 (see Part IV).

  28. Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms.
    Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.

  29. Hitting minors on bounded treewidth graphs. I. General upper bounds.
    Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.

  30. Dual parameterization of Weighted Coloring.
    Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinicius F. dos Santos, Ignasi Sau, and Ana Silva.
    • Full version in Algorithmica, 82(8): 2316-2336, 2020.
    • Short version in Proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC), volume 115 of LIPIcs, pages 12:1–12:14, Helsinki, Finland, August 2018.

  31. Counting Gallai 3-colorings of complete graphs.
    Josefran de Oliveira Bastos, Fabricio Siqueira Benevides, Guilherme Oliveira Mota, and Ignasi Sau.
    • Full version in Discrete Mathematics (DM), 342(9): 2618-2631, 2019.

  32. Weighted proper orientations of trees and graphs of bounded treewidth.
    Júlio Araújo, Cláudia Linhares Sales, Ignasi Sau, and Ana Silva.
    • Full version in Theoretical Computer Science (TCS), 771: 39-48, 2019.

  33. A tight Erdös-Pósa function for wheel minors.
    Pierre Aboulker, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond, and Ignasi Sau.
    • Full version in SIAM Journal on Discrete Mathematics (SIDMA), 32(3): 2302-2312, 2018.

  34. Ruling out FPT algorithms for Weighted Coloring on forests.
    Júlio Araújo, Julien Baste, and Ignasi Sau.
    • Full version in Theoretical Computer Science (TCS), 729: 11-19, 2018.
    • Short version in Proceedings of the IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), volume 62 of ENDM, pages 195-200, Marseille, France, September 2017.

  35. On the complexity of finding internally vertex-disjoint long directed paths.
    Júlio Araújo, Victor A. Campos, Ana Karolinna Maia, Ignasi Sau, and Ana Silva.
    • Full version in Algorithmica, 82(6): 1616-1639, 2020.
    • Short version in Proceedings of the 13th Latin American Theoretical INformatics Symposium (LATIN), volume 10807 of LNCS, pages 66-79, Buenos Aires, Argentina, April 2018.

  36. Parameterized complexity of finding a spanning tree with minimum reload cost diameter.
    Julien Baste, Didem Gözüpek, Christophe Paul, Ignasi Sau, Mordechai Shalom, and Dimitrios M. Thilikos.
    • Full version in Networks, 75(3): 259-277, 2020.
    • Short version in Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC), volume 89 of LIPIcs, pages 3:1–3:12, Vienna, Austria, September 2017.

  37. Complexity dichotomies for the Minimum F-Overlay problem.
    Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau, and Rémi Watrigant.
    • Full version in Journal of Discrete Algorithms (JDA), 52: 133-142, 2018.
    • Short version in Proceedings of the 28th International Workshop on Combinatorial Algorithms (IWOCA), volume 10765 of LNCS, pages 116-127, Newcastle, Australia, July 2017.

  38. How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
    Marin Bougeret and Ignasi Sau.
    • Full version in Algorithmica, 81(10): 4043-4068, 2019.
    • Short version in Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC), volume 89 of LIPIcs, pages 10:1–10:13, Vienna, Austria, September 2017.

  39. Uniquely restricted matchings and edge colorings.
    Julien Baste, Dieter Rautenbach, and Ignasi Sau.
    • Full version containing the combinatorial results in Journal of Graph Theory (JGT), 91(3): 251-258, 2019.
    • Full version containing the algorithmic results in Discrete Applied Mathematics (DAM), 267: 30-40, 2019.
    • Short version in Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 10520 LNCS, pages 100-112, Eindhoven, The Netherlands, June 2017.

  40. On the number of labeled graphs of bounded treewidth.
    Julien Baste, Marc Noy, and Ignasi Sau.
    • Full version in European Journal of Combinatorics (EJC), 71: 12-21, 2018.
    • Short version in Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 10520 of LNCS, pages 88-99, Eindhoven, The Netherlands, June 2017.

  41. Maximum cuts in edge-colored graphs.
    Luerbio Faria, Sulamita Klein, Ignasi Sau, Uéverton S. Souza, and Rubens Sucupira.
    • Full version in Discrete Applied Mathematics (DAM), 281: 229-234, 2020.
    • Short version in Proceedings of the IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), volume 62 of ENDM, pages 87-92, Marseille, France, September 2017.
    • Short version (in Portuguese) in XLVIII Simpósio Brasileiro de Pesquisa Operacional (SBPO), Vitória, Brazil, September 2016.
    • Short abstract in XXXVI Congresso da Sociedade Brasileira de Computação - Encontro de Teoria da Computação (CSBC-ETC), Porto Alegre, Brazil, July 2016.

  42. On the (parameterized) complexity of recognizing well-covered (r,l)-graphs.
    Sancrey Rodrigues Alves, Konrad K. Dabrowski, Luerbio Faria, Sulamita Klein, Ignasi Sau, and Uéverton S. Souza.
    • Full version in Theoretical Computer Science (TCS), 746: 36-48, 2018.
    • Short version in Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA), volume 10043 of LNCS, pages 423-437, Hong Kong, China, December 2016.

  43. Parameterized complexity of the MINCCA problem on graphs of bounded decomposability.
    Didem Gözüpek, Sibel Özkan, Christophe Paul, Ignasi Sau, and Mordechai Shalom.
    • Full version in Theoretical Computer Science (TCS), 690: 91-103, 2017.
    • Short version in Proceedings of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 9941 of LNCS, pages 195-206, Istanbul, Turkey, June 2016.

  44. Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees.
    Julien Baste, Christophe Paul, Ignasi Sau, and Celine Scornavacca.
    • Full version in Bulletin of Mathematical Biology (BMAB), 79(4): 920-938, 2017.
    • Short version in Proceedings of the 11th International Conference on Algorithmic Aspects of Information and Management (AAIM), Bergamo, Italy, July 2016.

  45. An FPT 2-approximation for tree-cut decomposition.
    Eun Jung Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in Algorithmica, 80(1): 116-135, 2018.
    • Short version in Proceedings of the 13th Workshop on Approximation and Online Algorithms (WAOA), volume 9499 of LNCS, pages 35-46, Patras, Greece, September 2015.

  46. On the parameterized complexity of the Edge Monitoring problem.
    Julien Baste, Fairouz Beggas, Hamamache Kheddouci, and Ignasi Sau.
    • Full version in Information Processing Letters (IPL), 121: 39-44, 2017.

  47. An O(log OPT)-approximation for covering and packing minor models of Theta_r.
    Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in Algorithmica, 80(4): 1330-1356, 2018.
    • Short version in Proceedings of the 13th Workshop on Approximation and Online Algorithms (WAOA), volume 9499 of LNCS, pages 122-132, Patras, Greece, September 2015.

  48. Minors in graphs of large Theta_r-girth.
    Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in European Journal of Combinatorics (EJC), 65: 106-121, 2017.
    • Short version (entitled "Covering and packing pumpkin models") in Proceedings of the 9th International Colloquium on Graph Theory and Combinatorics (ICGT), Grenoble, France, June-July 2014.

  49. Parameterized algorithms for min-max multiway cut and list digraph homomorphism.
    Eun Jung Kim, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in Journal of Computer and System Sciences (JCSS), 86: 191-206, 2017.
    • Short version in Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC), volume 43 of LIPIcs, pages 78-89, Patras, Greece, September 2015.

  50. Parameterized complexity dichotomy for (r,l)-Vertex Deletion.
    Julien Baste, Luerbio Faria, Sulamita Klein, Ignasi Sau.
    • Full version in Theory of Computing Systems (TOCS), 61(3): 777-794, 2017.

  51. Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs.
    Luerbio Faria, Sulamita Klein, Ignasi Sau, and Rubens Sucupira.
    • Full version in Discrete Mathematics & Theoretical Computer Science (DMTCS), 19(1), 2017.

  52. Explicit linear kernels for packing problems.
    Valentin Garnero, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in Algorithmica, 81(4): 1615-1656, 2019.

  53. On the complexity of computing the k-restricted edge-connectivity of a graph.
    Luis Pedro Montejano and Ignasi Sau.
    • Full version Theoretical Computer Science (TCS), 662: 31-39, 2017.
    • Short version in Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 9224 of LNCS, pages 219-233, Munich, Germany, June 2015.

  54. A polynomial-time algorithm for outerplanar diameter improvement.
    Nathann Cohen, Daniel Gonçalves, Eun Jung Kim, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos, and Mathias Weller.
    • Full version in Journal of Computer and System Sciences (JCSS), 89: 315-327, 2017.
    • Short version in Proceedings of the 10th International Computer Science Symposium in Russia (CSR), volume 9139 of LNCS, pages 123-142, Listvyanka, Russia, July 2015.

  55. Improved FPT algorithms for weighted independent set in bull-free graphs.
    Henri Perret du Cray and Ignasi Sau.
    • Full version in Discrete Mathematics (DM), 341(2): 451-462, 2018.
    • Short version in Proceedings of the 9th International Symposium on Parameterized and Exact Computation (IPEC), volume 8894 of LNCS, pages 282-293, Warsaw, Poland, September 2014.

  56. An edge variant of the Erdös-Pósa property.
    Jean-Florent Raymond, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in Discrete Applied Mathematics (DAM), 339(8): 2027-2035, 2016.
    • Short version in Proceedings of the 9th International Colloquium on Graph Theory and Combinatorics (ICGT), Grenoble, France, June-July 2014.

  57. Explicit linear kernels via dynamic programming.
    Valentin Garnero, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in SIAM Journal on Discrete Mathematics (SIDMA), 29(4): 1864-1894, 2015.
    • Short version in Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS), volume 25 of LIPIcs, pages 312-324, Lyon, France, March 2014.

  58. The role of planarity in connectivity problems parameterized by treewidth.
    Julien Baste and Ignasi Sau.
    • Full version in Theoretical Computer Science (TCS), 570: 1-14, 2015.
    • Short version in Proceedings of the 9th International Symposium on Parameterized and Exact Computation (IPEC), volume 8894 of LNCS, pages 63-74, Warsaw, Poland, September 2014.

  59. A linear kernel for planar red-blue dominating set.
    Valentin Garnero, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in Discrete Applied Mathematics (DAM), 217: 536-547, 2017.
    • Short version in Proceedings of the 12th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW), pages 117-120, Enschede, The Netherlands, May 2013.

  60. Linear kernels and single-exponential algorithms via protrusion decompositions.
    Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar.
    • Full version in ACM Transactions on Algorithms (TALG), 12(2): 21, 2016.
    • Short version in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), volume 7965 of LNCS, pages 613-624, Riga, Latvia, July 2013.

  61. A linear kernel for planar total dominating set.
    Valentin Garnero and Ignasi Sau.
    • Full version in Discrete Mathematics & Theoretical Computer Science (DMTCS), 20(1), 2018.

  62. Parameterized domination in circle graphs.
    Nicolas Bousquet, Daniel Gonçalves, George B. Mertzios, Christophe Paul, Ignasi Sau, and Stéphan Thomassé.
    • Full version in Theory of Computing Systems (TOCS), 54(1): 45-72, 2014.
    • Short version in Proceedings of the 38th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 7551 of LNCS, pages 308-319, Jerusalem, Israel, June 2012.

  63. Hitting and harvesting pumpkins.
    Gwenaël Joret, Christophe Paul, Ignasi Sau, Saket Saurabh, and Stéphan Thomassé.
    • Full version in SIAM Journal on Discrete Mathematics (SIDMA), 28(3): 1363-1390, 2014.
    • Short version in Proceedings of the 19th Annual European Symposium on Algorithms (ESA), volume 6942 of LNCS, pages 394-407, Saarbrücken, Germany, September 2011.

  64. Dynamic programming for H-minor-free graphs (extended abstract).
    Juanjo Rué, Ignasi Sau, and Dimitrios M. Thilikos.
    • Short version in Proceedings of the 18th Annual International Computing and Combinatorics Conference (COCOON), volume 7434 of LNCS, pages 86-97, Sydney, Australia, August 2012.

  65. On approximating the d-girth of a graph.
    David Peleg, Ignasi Sau, and Mordechai Shalom.
    • Full version in Discrete Applied Mathematics (DAM), 161(16-17): 2587-2596, 2013.
    • Short version in Proceedings of the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), volume 6543 of LNCS, pages 467-481, Novy Smokovec, Slovakia, January 2011.

  66. Traffic grooming in star networks via matching techniques.
    Ignasi Sau, Mordechai Shalom, and Shmuel Zaks.
    • Short version in Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 6058 of LNCS, pages 41-56, Sirince, Turkey, June 2010.

  67. Placing regenerators in optical networks to satisfy multiple sets of requests.
    George B. Mertzios, Ignasi Sau, Mordechai Shalom, and Shmuel Zaks.
    • Full version in IEEE/ACM Transactions on Networking (ToN), 20(6): 1870-1879, 2012.
    • Short version in Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), volume 6199 of LNCS, pages 333-344, Bordeaux, France, July 2010. Best paper award of Track C of ICALP'10.

  68. Dynamic programming for graphs on surfaces.
    Juanjo Rué, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in ACM Transactions on Algorithms (TALG), 10(2): 8, 2014.
    • Short version in Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), volume 6198 of LNCS, pages 372-383, Bordeaux, France, July 2010.

  69. Asymptotic enumeration of non-crossing partitions on surfaces.
    Juanjo Rué, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in Discrete Mathematics (DM), 313(5-6): 635-649, 2013.
    • Short version in Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), volume 6198 of LNCS, pages 372-383, Bordeaux, France, July 2010.

  70. Fast minor testing in planar graphs.
    Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in Algorithmica, 64(1): 69-84, 2012.
    • Short version in Proceedings of the 18th Annual European Symposium on Algorithms (ESA), volume 6346 of LNCS, pages 97-109, Liverpool, U.K., September 2010.

  71. Faster parameterized algorithms for minor containment.
    Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in Theoretical Computer Science (TCS), 412(50): 7018-7028, 2011.
    • Short version in Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 6139 of LNCS, pages 322-333, Bergen, Norway, June 2010.

  72. The recognition of tolerance and bounded tolerance graphs.
    George B. Mertzios, Ignasi Sau, and Shmuel Zaks.
    • Full version in SIAM Journal on Computing (SICOMP), 40(5): 1234-1257, 2011.
    • Short version in Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 5 of LIPIcs, pages 858-596, Nancy, France, March 2010.

  73. On self-duality of branchwidth in graphs of bounded genus.
    Ignasi Sau and Dimitrios M. Thilikos.
    • Full version in Discrete Applied Mathematics (DAM), 159(17): 2184-2186, 2011.
    • Short version in Proceedings of the 8th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW), pages 19-22, Paris, France, June 2009.

  74. Edge-partitioning regular graphs for ring traffic grooming with a priori placement of the ADMs.
    Xavier Muñoz, Zhentao Li, and Ignasi Sau.
    • Full version in SIAM Journal on Discrete Mathematics (SIDMA), 25(4): 1490-1505, 2011.
    • First short version (without Zhentao Li) in Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 5344 of LNCS, pages 300-311, Durham University, U.K., July 2008.
    • Second short version (without Xavier Muñoz) in Proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 5911 of LNCS, pages 250-261, Montpellier, France, June 2009. Best student paper award of WG'09.

  75. Parameterized complexity of finding small degree-constrained subgraphs.
    Omid Amini, Ignasi Sau, and Saket Saurabh.
    • Full version in Journal of Discrete Algorithms (JDA), 10: 70-83, 2012.
    • Short version in Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC), volume 5008 of LNCS, pages 13-29, Victoria, Canada, May 2008.

  76. On the approximability of some degree-constrained subgraph problems.
    Omid Amini, David Peleg, Stéphane Pérennes, Ignasi Sau, and Saket Saurabh.
    • Full version in Discrete Applied Mathematics (DAM), 160(12): 1661-1679, 2012.
    • Short version in Proceedings of the 6th Workshop on Approximation and Online Algorithms (WAOA), volume 5426 of LNCS, pages 29-42, Universität Karlsruhe, Germany, September 2008.

  77. Simpler multicoloring of triangle-free hexagonal graphs.
    Ignasi Sau, Petra Sparl and Janez Zerovnik.
    • Full version in Discrete Mathematics (DM), 312(1): 181-187, 2012.
    • Poster in 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Piran, Slovenia, May 2009.

  78. GMPLS label space minimization through hypergraph layouts.
    Jean-Claude Bermond, David Coudert, Joanna Moulierac, Stéphane Pérennes, Ignasi Sau, and Fernando Solano Donado.
    • Full version in Theoretical Computer Science (TCS), 444: 3-16, 2012.
    • Second short version in Proceedings of 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 5869 of LNCS, pages 57-71, Piran, Slovenia, May 2009.
    • First short version (with Hervé Rivano) in Proceedings of IFIP Networking, volume 5550 of LNCS, pages 809-820, Aachen, Germany, May 2009.

  79. Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs.
    Dimitrios M. Thilikos and Ignasi Sau.
    • Full version in Journal of Discrete Algorithms (JDA), 8(3): 330-338, 2010.
    • Short version in Proceedings of DIMAP workshop on Algorithmic Graph Theory (AGT), Electronic Notes in Discrete Mathematics, 32:59-66, University of Warwick, U.K., March 2009.

  80. A new intersection model and improved algorithms for tolerance graphs.
    George B. Mertzios, Ignasi Sau, and Shmuel Zaks.
    • Full version in SIAM Journal on Discrete Mathematics (SIDMA), 23(4):1800-1813, 2009.
    • Short version in Proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 5911 of LNCS, pages 285-295, Montpellier, France, June 2009.

  81. Circuits in graphs through a prescribed set of ordered vertices.
    David Coudert, Frédéric Giroire, and Ignasi Sau.
    • Full version in Journal of Interconnection Networks (JOIN), 11(3-4): 121-141, 2011.
    • Short version in Proceedings of the 20th International Workshop on Combinatorial Algorithms (IWOCA), volume 5874 of LNCS, pages 134-145, Opava, Czech Republic, June 2009.

  82. Weighted coloring on P_4-sparse graphs.
    Júlio César Araújo, Cláudia Linhares-Sales, and Ignasi Sau..
    • Short version in 11es Journées Doctorales en Informatique et Réseaux (JDIR), Sophia Antipolis, France, March 2010.

  83. Drop cost and wavelength optimal two-period grooming with ratio 4.
    Jean-Claude Bermond, Charles J. Colbourn, Lucia Gionfriddo, Gaetano Quattrocchi, and Ignasi Sau.
    • Full version in SIAM Journal on Discrete Mathematics (SIDMA), 24(2): 400-419, 2010.

  84. (l,k)-routing on plane grids.
    Florian Huc, Ignasi Sau, and Janez Zerovnik.
    • Full version in Journal of Interconnection Networks (JOIN), 10(1-2):27-57, 2009.

  85. Hardness and approximation of traffic grooming.
    Omid Amini, Stéphane Pérennes, and Ignasi Sau.
    • Full version in Theoretical Computer Science (TCS), 410(38-40):3751-3760, 2009.
    • Short version in Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC), volume 4835 of LNCS, pages 561-573, Sendai, Japan, December 2007.
    • Communication in 9es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), Ile d'Oléron, France, May 2007.

  86. An optimal permutation routing algorithm for full-duplex hexagonal mesh networks.
    Ignasi Sau and Janez Zerovnik.
    • Full version in Discrete Mathematics & Theoretical Computer Science (DMTCS), 10(3):49-62, 2008.
    • Short version in Proceedings of the International Network Optimization Conference (INOC), Spa, Belgium, April 2007.

  87. Traffic grooming in bidirectional WDM ring networks.
    Jean-Claude Bermond, Xavier Muñoz, and Ignasi Sau.
    • Full version in Networks, 58(1): 20-35, 2011.
    • Short version in Proceedings of the IEEE-LEOS International Conference on Transparent Optical Networks (ICTON), volume 3, pages 19-22, Nottingham, UK, June 2006.
    • Poster in ADONET/COST293 Spring School on Combinatorial Optimization and Communication Networks, Budapest University of Technology and Economics, Hungary, March 2006.

Book chapters
  1. Traffic Grooming: Combinatorial Results and Practical Resolutions [link to the full book]
    Tibor Cinkler, David Coudert, Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Xavier Muñoz, Ignasi Sau, Mordechai Shalom, and Shmuel Zaks.
    In Graphs and Algorithms in Communication Networks. Studies in Broadband, Optical, Wireless, and Ad Hoc Networks.
    Arie Koster and Xavier Muñoz (editors). EATCS Texts in Theoretical Computer Science, Springer, December 2009.

  2. Permutation Routing and (l,k)-Routing on Plane Grids [link to the full book]
    Ignasi Sau and Janez Zerovnik.
    In Graphs and Algorithms in Communication Networks. Studies in Broadband, Optical, Wireless, and Ad Hoc Networks.
    Arie Koster and Xavier Muñoz (editors). EATCS Texts in Theoretical Computer Science, Springer, December 2009.

Theses

  1. Some Contributions to Parameterized Complexity [.pdf] [Slides (.pdf)]
    Ignasi Sau.
    Habilitation à Diriger des Recherches (HDR), Université de Montpellier, Montpellier, France, June 2018.

  2. Optimization in Graphs under Degree Constraints. Application to Telecommunication Networks [.pdf] [Slides (.pdf)]
    Ignasi Sau.
    Ph.D Thesis, Université de Nice-Sophia Antipolis (UNS) and Universitat Politècnica de Catalunya (UPC), Sophia Antipolis, France, October 2009.

  3. Minimizing the number of ADMs in WDM Optical Rings with Traffic Grooming [.pdf] [Slides (.pdf)]
    Ignasi Sau.
    Master Thesis for the Degree of Telecommunication Engineering in Polytechnical University of Catalonia (UPC), Barcelona, Catalonia, July 2006. Rated 10/10.
Last updated: June 26, 2023 back to Home