CNRS  LIRMM AlGCo 

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. 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.
    • Short version currently under review.

  2. Ruling out FPT algorithms for Weighted Coloring on forests.
    Júlio Araújo, Julien Baste, and Ignasi Sau.
    • Full version currently under review.
    • Short version to appear in Proceedings of the IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), ENDM, Marseille, France, September 2017.

  3. Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth.
    Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version in preparation.
    • Short version to appear in Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC), LIPIcs, Vienna, Austria, September 2017.

  4. 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 preparation.
    • Short version to appear in Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC), LIPIcs, Vienna, Austria, September 2017.

  5. 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 preparation.
    • Short version to appear in Proceedings of the 28th International Workshop on Combinatorial Algorithms (IWOCA), LNCS, Newcastle, Australia, July 2017.

  6. How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
    Marin Bougeret and Ignasi Sau.
    • Full version in preparation.
    • Short version to appear in Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC), LIPIcs, Vienna, Austria, September 2017.

  7. Uniquely restricted matchings and edge colorings.
    Julien Baste, Dieter Rautenbach, and Ignasi Sau.
    • Full version currently under review.
    • Short version to appear in Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), LNCS, Eindhoven, The Netherlands, June 2017.

  8. On the number of labeled graphs of bounded treewidth.
    Julien Baste, Marc Noy, and Ignasi Sau.
    • Full version currently under review.
    • Short version to appear in Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), LNCS, Eindhoven, The Netherlands, June 2017.

  9. Finding cuts in edge-colored graphs.
    Luerbio Faria, Sulamita Klein, Ignasi Sau, Uéverton dos Santos Souza, and Rubens Sucupira.
    • Full version in preparation.
    • Short version to appear in Proceedings of the IX Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), ENDM, 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.

  10. 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 dos Santos Souza.
    • Full version currently under review.
    • 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.

  11. 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.

  12. 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.

  13. An FPT 2-approximation for tree-cut decomposition.
    Eun Jung Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version to appear in Algorithmica.
    • 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.

  14. 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.

  15. 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 to appear in Algorithmica.
    • 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.

  16. 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.

  17. 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.

  18. 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.

  19. 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.

  20. Explicit linear kernels for packing problems.
    Valentin Garnero, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version currently under review.

  21. 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.

  22. 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.

  23. Improved FPT algorithms for weighted independent set in bull-free graphs.
    Henri Perret du Cray and Ignasi Sau.
    • Full version to appear in Discrete Mathematics (DM).
    • 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.

  24. 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.

  25. 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.

  26. 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.

  27. 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.

  28. 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.

  29. A linear kernel for planar total dominating set.
    Valentin Garnero and Ignasi Sau.
    • Full version currently under review.

  30. 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.

  31. 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.

  32. Dynamic programming for H-minor-free graphs (extended abstract).
    Juanjo Rué, Ignasi Sau, and Dimitrios M. Thilikos.
    • Full version to be submitted.
    • 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.

  33. 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.

  34. Traffic grooming in star networks via matching techniques.
    Ignasi Sau, Mordechai Shalom, and Shmuel Zaks.
    • Full version to be submitted.
    • 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.

  35. 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.

  36. 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.

  37. 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.

  38. 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.

  39. 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.

  40. 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.

  41. 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.

  42. 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.

  43. 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.

  44. 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.

  45. 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.

  46. 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.
    • First short version (with Hervé Rivano) in Proceedings of IFIP Networking, volume 5550 of LNCS, pages 809-820, Aachen, Germany, May 2009.
    • 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.

  47. 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.

  48. 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.

  49. 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.

  50. 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.

  51. 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.

  52. (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.

  53. 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.

  54. 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.

  55. 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

Theses


Last updated: August 30, 2017 back to Home Visitors