Nombre de documents

69

CV de Ignasi Sau


Article dans une revue29 documents

  • Julien Baste, Fairouz Beggas, Hamamache Kheddouci, Ignasi Sau. On the parameterized complexity of the Edge Monitoring problem. Information Processing Letters, Elsevier, 2017, 121, pp.39-44. <10.1016/j.ipl.2017.01.008>. <lirmm-01487565>
  • Eun Jung Kim, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. Parameterized algorithms for min-max multiway cut and list digraph homomorphism. Journal of Computer and System Sciences, Elsevier, 2017, 86, pp.191-206. <10.1016/j.jcss.2017.01.003>. <lirmm-01487567>
  • Luis Pedro Montejano, Ignasi Sau. On the complexity of computing the k-restricted edge-connectivity of a graph. Theoretical Computer Science, Elsevier, 2017, 662, pp.31-39. <10.1016/j.tcs.2016.12.006>. <lirmm-01481786>
  • Valentin Garnero, Ignasi Sau, Dimitrios M. Thilikos. A linear kernel for planar red–blue dominating set. Discrete Applied Mathematics, Elsevier, 2017, 217, pp.536-547. <10.1016/j.dam.2016.09.045>. <lirmm-01481785>
  • Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos. An edge variant of the Erdős–Pósa property. Discrete Mathematics, Elsevier, 2016, 339 (8), pp.2027-2035. <10.1016/j.disc.2016.03.004>. <lirmm-01347430>
  • Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, et al.. Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions. ACM Transactions on Algorithms, Association for Computing Machinery, 2016, 12 (2), pp.No. 21. <10.1145/2797140>. <lirmm-01288472>
  • Valentin Garnero, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. Explicit Linear Kernels via Dynamic Programming. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2015, 29 (4), pp.1864-1894. <10.1137/140968975>. <lirmm-01263857>
  • Julien Baste, Ignasi Sau. The role of planarity in connectivity problems parameterized by treewidth. Journal of Theoretical Computer Science (TCS), Elsevier, 2015, 570, pp.1-14. <10.1016/j.tcs.2014.12.010>. <lirmm-01272664>
  • Gwénaël Joret, Christophe Paul, Ignasi Sau, Saket Saurabh, Stéphan Thomassé. Hitting and harvesting pumpkins. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2014, 28 (3), pp.1363-1390. <10.1137/120883736>. <hal-01178192>
  • Christophe Paul, Nicolas Bousquet, Daniel Gonçalves, George Mertzios, Ignasi Sau, et al.. Parameterized domination in circle graphs. Theory of Computing Systems, Springer Verlag, 2014, 54 (1), pp.45-72. <10.1007/s00224-013-9478-8>. <hal-01178188>
  • Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos. Dynamic Programming for Graphs on Surfaces. ACM Transactions on Algorithms, Association for Computing Machinery, 2014, 10 (2), pp.Article No. 8. <10.1145/2556952>. <lirmm-01083690>
  • Dimitrios M. Thilikos, Ignasi Sau, Juanjo Rué. Asymptotic enumeration of non-crossing partitions on surfaces. Discrete Mathematics, Elsevier, 2013, pp.635-649. <http://www.sciencedirect.com/science/article/pii/S0012365X1200533X>. <10.1016/j.disc.2012.12.011>. <lirmm-00804780>
  • David Peleg, Ignasi Sau, Mordechai Shalom. On approximating the -girth of a graph. Discrete Applied Mathematics, Elsevier, 2013, 161 (16), pp.2587-2596. <10.1016/j.dam.2013.04.022>. <lirmm-01272717>
  • George B. Mertzios, Ignasi Sau, Mordechai Shalom, Shmuel Zaks. Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests. IEEE/ACM Transactions on Networking, IEEE/ACM, 2012, 20, pp.1-15. <10.1109/TNET.2012.2186462>. <lirmm-00736699>
  • Jean-Claude Bermond, David Coudert, Joanna Moulierac, Stéphane Pérennes, Ignasi Sau, et al.. GMPLS Label Space Minimization through Hypergraph Layouts. Theoretical Computer Science, Elsevier, 2012, 444, pp.3-16. <10.1016/j.tcs.2012.01.033>. <hal-00706260>
  • Omid Amini, Ignasi Sau, Saket Saurabh. Parameterized complexity of finding small degree-constrained subgraphs. Journal of Discrete Algorithms, Elsevier, 2012, 10, pp.70-83. <10.1016/j.jda.2011.05.001>. <lirmm-00736517>
  • Ignasi Sau, Petra Šparl, Janez Žerovnik. Simpler multicoloring of triangle-free hexagonal graphs. Discrete Mathematics, Elsevier, 2012, 312 (1), pp.181-187. <lirmm-00736521>
  • Isolde Adler, Frederic Dorn, Fedor Fomin, Ignasi Sau, Dimitrios M. Thilikos. Fast Minor Testing in Planar Graphs. Algorithmica, Springer Verlag, 2012, 64 (1), pp.69-84. <http://link.springer.com/article/10.1007%2Fs00453-011-9563-9>. <10.1007/s00453-011-9563-9>. <lirmm-00904515>
  • Omid Amini, David Peleg, Stéphane Pérennes, Ignasi Sau, Saket Saurabh. On the approximability of some degree-constrained subgraph problems. Discrete Applied Mathematics, Elsevier, 2012, 160 (2), pp.1661-1679. <10.1016/j.dam.2012.03.025>. <lirmm-00736702>
  • David Coudert, Frédéric Giroire, Ignasi Sau. Circuits in graphs through a prescribed set of ordered vertices. Journal of Interconnection Networks, World Scientific Publishing, 2011, 11 (3-4), pp.121-141. <10.1142/S0219265910002763>. <inria-00585561>
  • Xavier Muñoz, Zhentao Li, Ignasi Sau. Edge-Partitioning Regular Graphs for Ring Traffic Grooming with a Priori Placement of the ADMs. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2011, 25 (4), pp.1490-1505. <10.1137/090775440>. <lirmm-00736697>
  • George B. Mertzios, Ignasi Sau, Shmuel Zaks. The Recognition of Tolerance and Bounded Tolerance Graphs. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2011, 40 (5), pp.1234-1257. <10.1137/090780328>. <lirmm-00736512>
  • Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos. Faster parameterized algorithms for minor containment. Theoretical Computer Science, Elsevier, 2011, 412 (50), pp.7018-7028. <lirmm-00736522>
  • Jean-Claude Bermond, Xavier Muñoz, Ignasi Sau. Traffic grooming in bidirectional WDM ring networks. Networks, Wiley, 2011, 58 (1), pp.20-35. <10.1002/net.20410>. <hal-00643800>
  • Ignasi Sau, Dimitrios M. Thilikos. On self-duality of branchwidth in graphs of bounded genus. Discrete Applied Mathematics, Elsevier, 2011, 159 (17), pp.2184-2186. <10.1016/j.dam.2011.06.028>. <lirmm-00736520>
  • Jean-Claude Bermond, Charles J. Colbourn, Lucia Gionfriddo, Gaetano Quattrocchi, Ignasi Sau. Drop Cost and Wavelength Optimal Two-Period Grooming with Ratio 4. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2010, 24 (2), pp.400-419. <10.1137/080744190>. <lirmm-00736478>
  • Jean-Claude Bermond, Charles J. Colbourn, Lucia Gionfriddo, Gaetano Quattrocchi, Ignasi Sau. DROP COST AND WAVELENGTH OPTIMAL TWO-PERIOD GROOMING WITH RATIO 4∗. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2010, 24 (2), pp.400-419. <inria-00505516>
  • Ignasi Sau, Dimitrios M. Thilikos. Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs. Journal of Discrete Algorithms, Elsevier, 2010, 8 (3), pp.330-338. <10.1016/j.jda.2010.02.002>. <lirmm-00736490>
  • Ignasi Sau, Janez Žerovnik. An optimal permutation routing algorithm on full-duplex hexagonal networks. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (3), pp.49--62. <hal-00972334>

Communication dans un congrès25 documents

  • Julien Baste, Christophe Paul, Ignasi Sau, Celine Scornavacca. Efficient FPT Algorithms for (Strict) Compatibility of Unrooted Phylogenetic Trees. AAIM: Algorithmic Aspects in Information and Management, Jul 2016, Bergamo, Italy. 11th International Conference on Algorithmic Aspects of Information and Management, LNCS (9778), pp.53-64, 2017, <10.1007/s11538-017-0260-y>. <lirmm-01481368>
  • Didem Gözüpek, Sibel Özkan, Christophe Paul, Ignasi Sau, Mordeshai Shalom. Parameterized Complexity of the MINCCA Problem on Graphs of Bounded Decomposability. Graph Theoretical Concepts in Computer Science - WG, 2016, Istanbul, Turkey. International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS (9941), pp.195-206, 2016, WG 2016. <10.1007/978-3-662-53536-3_17>. <lirmm-01481360>
  • Sancrey Rodrigues Alves, Konrad Kazimierz Dabrowski, Luerbio Faria, Sulamita Klein, Ignasi Sau, et al.. On the (Parameterized) Complexity of Recognizing Well-Covered $(r,l)$-graphs. COCOA: Conference on Combinatorial Optimization and Applications, Dec 2016, Hong Kong, China. 10th International Conference on Combinatorial Optimization and Applications, LNCS (10043), pp.423-437, 2016, Combinatorial Optimization and Applications. <10.1007/978-3-319-48749-6_31>. <lirmm-01481787>
  • Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos. An O(log OPT)-approximation for covering and packing minor models of θr. 13th Workshop on Approximation and Online Algorithms, Sep 2015, Patras, Greece. Springer International Publishing, 13th Workshop on Approximation and Online Algorithms (WAOA 2015) ( 9499), pp.122-132, 2015, Lecture Notes in Computer Science. <hal-01218496>
  • Nathann Cohen, Daniel Gonçalves, Kim Eun Jung, Christophe Paul, Ignasi Sau, et al.. A Polynomial-Time Algorithm for Outerplanar Diameter Improvement. International Computer Science Symposium in Russia - CRS, 2015, Irkutsk, Russia. 9139, 2015, Lecture Notes in Computer Science. <hal-01178222>
  • Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos. An $O(log OPT)$-Approximation for Covering/Packing Minor Models of $θ _r$. WAOA: Workshop on Approximation and Online Algorithms, Sep 2015, Patras, Greece. 13th International Workshop on Approximation and Online Algorithms, LNCS (9499), pp.122-132, 2016, <10.1007/978-3-319-28684-6_11>. <lirmm-01481784>
  • Eun Jung Kim, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism. IPEC: International Symposium on Parameterized and Exact Computation, 2015, Patras, Greece. 43, pp.78-89, 2015, Leibniz International Proceedings in Informatics (LIPIcs). <lirmm-01263999>
  • Eun Jung Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. An FPT 2-Approximation for Tree-cut Decomposition. WAOA: International Workshop on Approximation and Online Algorithms, 2015, Patras, Greece. 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers, LNCS (9499), pp.35-46, 2016, Approximation and Online Algorithms. <10.1007/978-3-319-28684-6_4>. <lirmm-01264015>
  • Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos. An edge variant of the Erdős-Pósa property. ICGT: International Colloquium on Graph Theory and Combinatorics, Jun 2014, Grenoble, France. 2014. <lirmm-00904544>
  • Valentin Garnero, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. Explicit linear kernels via dynamic programming. STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2014, Lyon, France. 30th Symposium on Theoretical Aspects of Computer Science, 2014. <hal-01084007>
  • Julien Baste, Ignasi Sau. The role of planarity in connectivity problems parameterized by treewidth. IPEC: International Parameterized and Exact Computation, Sep 2014, Wroclaw, Poland. 9th International Symposium on Parameterized and Exact Computation, LNCS (8894), pp.63-74, 2014, Parameterized and Exact Computation. <10.1007/978-3-319-13524-3_6>. <lirmm-01481432>
  • Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos. Covering and packing pumpkin models. ICGT: International Colloquium on Graph Theory and Combinatorics, Jun 2014, Grenoble, France. ICGT'2014: 9th International colloquium on graph theory and combinatorics, 2014, <http://oc.inpg.fr/conf/icgt2014/>. <lirmm-01083652>
  • Garnero Valentin, Ignasi Sau, Dimitrios M. Thilikos. A linear kernel for planar red-blue dominating set. CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization, May 2013, Enschede, Netherlands. 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp.117-120, 2013, <http://wwwhome.math.utwente.nl/~ctw/index.php?page=home>. <lirmm-00846771>
  • Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, et al.. Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions. Automata, Languages, and Programming. 40th International Colloquium, ICALP 2013, Jul 2013, Riga, Latvia. Automata, Languages, and Programming. 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pp.613-624, 2013, <10.1007/978-3-642-39206-1_52>. <hal-01383776>
  • Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, et al.. Linear Kernels and Single-exponential Algorithms via Protrusion Decompositions. ICALP: International Colloquium on Automata, Languages and Programming, Jul 2013, Riga, Latvia. 1 (7965), pp.613-624, 2013, Lecture Notes in Computer Science. <lirmm-00829999>
  • David Peleg, Ignasi Sau, Mordechai Shalom. On Approximating the d-Girth of a Graph. SOFSEM'11: Theory and Practice of Computer Science, Slovakia. Springer Berlin Heidelberg, 6543, pp.467-481, 2011, LNCS. <10.1007/978-3-642-18381-2_39>. <lirmm-00736705>
  • Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos. Dynamic Programming for H-minor-free Graphs. Gudmundsson, Joachim and Mestre, Julien and Viglas, Taso. COCOON'12: 18th Annual International Computing and Combinatorics Conference, Australia. Springer Berlin Heidelberg, 7434, pp.86-97, 2012, <10.1007/978-3-642-32241-9_8>. <lirmm-00736708>
  • Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos. Fast Minor Testing in Planar Graphs. ESA'10: 18th Annual European Symposium on Algorithms, United Kingdom. pp.97-109, 2010, LNCS. <lirmm-00736769>
  • Nicolas Bousquet, Daniel Gonçalves, George Mertzios, Christophe Paul, Ignasi Sau, et al.. Parameterized Domination in Circle Graphs. WG'12: 38th International Workshop on Graph Theoretic Concepts in Computer Science, Jun 2012, Jerusalem, Israel. LNCS (7551), pp.308-319, 2012, Graph-Theoretic Concepts in Computer Science. <https://sites.google.com/site/wg2012conf/>. <10.1007/978-3-642-34611-8_31>. <lirmm-00738534>
  • Gwénaël Joret, Christophe Paul, Ignasi Sau, Saket Saurabh, Stéphan Thomassé. Hitting and Harvesting Pumpkins. ESA: European Symposium on Algorithms, Sep 2011, Saarbrücken, Germany. 19th European Symposium on Algorithms, LNCS (6942), pp.394-407, 2011, <http://esa2011.mpi-inf.mpg.de>. <lirmm-00642341>
  • George B. Mertzios, Ignasi Sau, Shmuel Zaks. The Recognition of Tolerance and Bounded Tolerance Graphs. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.585-596, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. <inria-00455774>
  • Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos. Dynamic programming for graphs on surfaces. ICALP: International Colloquium on Automata, Languages and Programming, 2010, Bordeaux, France. Springer-Verlag, 37th, pp.372-383, 2010. <lirmm-00736703>
  • David Coudert, Frédéric Giroire, Ignasi Sau. Edge-Simple Circuits Through 10 Ordered Vertices in Square Grids. International Workshop on Combinatorial Algorithms -- IWOCA, Jun 2009, Hradec nad Moravicì, Czech Republic. Springer, 5874, 2009, Lecture Notes in Computer Science. <inria-00429146>
  • Omid Amini, Stéphane Pérennes, Ignasi Sau. Hardness of Approximating the Traffic Grooming Problem. 9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.45-48, 2007. <inria-00176960>
  • Jean-Claude Bermond, David Coudert, Xavier Munoz, Ignasi Sau. Traffic Grooming in Bidirectional WDM Ring Networks. International Conference on Transparent Optical Networks (ICTON), Jun 2006, Nottingham, United Kingdom. IEEE / LEOS, 3, pp.19 - 22, 2006, <10.1109/ICTON.2006.248390>. <inria-00429168>

Rapport8 documents

  • Kim Eun Jung, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism. [Research Report] LIRMM. 2015. <lirmm-01225570>
  • Eunjung Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. An FPT 2-Approximation for Tree-Cut Decomposition. [Research Report] LIRMM. 2015. <lirmm-01225569>
  • Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau, Rémi Watrigant. Complexity Dichotomies for the Minimum F-Overlay Problem. [Research Report] 9045, Inria Sophia Antipolis. 2013, pp.16. <hal-01490535>
  • Jean-Claude Bermond, David Coudert, Joanna Moulierac, Stéphane Pérennes, Ignasi Sau, et al.. GMPLS Routing Strategies based on the Design of Hypergraph Layouts. [Research Report] RR-6842, INRIA. 2009. <inria-00360576>
  • Jean-Claude Bermond, David Coudert, Joanna Moulierac, Stéphane Pérennes, Hervé Rivano, et al.. MPLS label stacking on the line network. [Research Report] RR-6803, INRIA. 2009. <inria-00354267>
  • David Coudert, Frédéric Giroire, Ignasi Sau. Circuit visiting 10 ordered vertices in infinite grids. [Research Report] RR-6910, INRIA. 2009. <inria-00378586>
  • Omid Amini, Stéphane Pérennes, Ignasi Sau. Hardness and Approximation of Traffic Grooming. [Research Report] RR-6236, INRIA. 2007, pp.17. <inria-00158341v3>
  • Omid Amini, Ignasi Sau, Saket Saurabh. Parameterized Complexity of the Smallest Degree Constraint Subgraph Problem. [Research Report] RR-6237, INRIA. 2007, pp.20. <inria-00157970v4>

Pré-publication, Document de travail5 documents

  • Luis Pedro Montejano, Ignasi Sau. On the complexity of computing the $k$-restricted edge-connectivity of a graph. 15 pages, 3 figures. 2016. <lirmm-01272707>
  • Julien Baste, Luerbio Faria, Sulamita Klein, Ignasi Sau. Parameterized complexity dichotomy for $(r,\ell)$-Vertex Deletion. 16 pages, 2 figures. 2016. <lirmm-01272704>
  • Luerbio Faria, Sulamita Klein, Ignasi Sau, Rubens Sucupira. Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs. 18 pages, 3 figures. 2016. <lirmm-01272714>
  • Eunjung Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. An FPT 2-Approximation for Tree-Cut Decomposition. 17 pages, 3 figures. 2016. <lirmm-01272709>
  • Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos. Minors in graphs of large θr-girth. Some of the results of this paper have been presented in WAOA 2015. 2015. <hal-01218519>

Chapitre d'ouvrage1 document

  • Tibor Cinkler, David Coudert, Michele Flammini, Gianpiero Monaco, Luca Moscardelli, et al.. Traffic Grooming: Combinatorial Results and Practical Resolutions.. Arie Koster and Xavier Muñoz. Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks., XXVII, Springer, pp.63-94, 2010, EATCS Texts in Theoretical Computer Science, 978-3-642-02249-4. <10.1007/978-3-642-02250-0>. <inria-00530964>

Thèse1 document

  • Ignasi Sau. Optimization in Graphs under Degree Constraints. Application to Telecommunication Networks. Mathematics [math]. Université Nice Sophia Antipolis; Universitat Politécnica de Catalunya, 2009. English. <tel-00429092>