Skip to Main content

Keywords

Co-authors

European projects

Researcher identifiers

Social networks

    Export Publications

    Export the displayed publications:

    External widget

    Number of documents

    116

    Publications of Ignasi Sau


    See also : http://www.lirmm.fr/~sau/Pubs.html


    Journal articles59 documents

    • Julien Baste, Ignasi Sau Valls, Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms. Theoretical Computer Science, Elsevier, 2020, 814, pp.135-152. ⟨10.1016/j.tcs.2020.01.026⟩. ⟨lirmm-02989928⟩
    • Júlio Araújo, Victor Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau Valls, et al.. Dual Parameterization of Weighted Coloring. Algorithmica, Springer Verlag, 2020, 82 (8), pp.2316-2336. ⟨10.1007/s00453-020-00686-7⟩. ⟨lirmm-02989870⟩
    • Luerbio Faria, Sulamita Klein, Ignasi Sau Valls, Uéverton dos Santos Souza, Rubens Sucupira. Maximum cuts in edge-colored graphs. Discrete Applied Mathematics, Elsevier, 2020, 281, pp.229-234. ⟨10.1016/j.dam.2019.02.038⟩. ⟨lirmm-02989852⟩
    • Julien Baste, Ignasi Sau Valls, Dimitrios M. Thilikos. Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2020, 34 (3), pp.1623-1648. ⟨10.1137/19M1287146⟩. ⟨lirmm-02989921⟩
    • Julien Baste, Ignasi Sau Valls, Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. III. Lower bounds. Journal of Computer and System Sciences, Elsevier, 2020, 109, pp.56-77. ⟨10.1016/j.jcss.2019.11.002⟩. ⟨lirmm-02989938⟩
    • Júlio Araújo, Victor Campos, Ana Karolinna Maia de Oliveira, Ignasi Sau Valls, Ana Silva. On the Complexity of Finding Internally Vertex-Disjoint Long Directed Paths. Algorithmica, Springer Verlag, 2020, 82 (6), pp.1616-1639. ⟨10.1007/s00453-019-00659-5⟩. ⟨lirmm-02989813⟩
    • Julien Baste, Didem Gözüpek, Christophe Paul, Ignasi Sau Valls, Mordechai Shalom, et al.. Parameterized complexity of finding a spanning tree with minimum reload cost diameter. Networks, Wiley, 2020, 75 (3), pp.259-277. ⟨10.1002/net.21923⟩. ⟨lirmm-02989889⟩
    • Julio Araujo, Cláudia Linhares Sales, Ignasi Sau Valls, Ana Silva. Weighted proper orientations of trees and graphs of bounded treewidth. Theoretical Computer Science, Elsevier, 2019, 771, pp.39-48. ⟨10.1016/j.tcs.2018.11.013⟩. ⟨lirmm-02410622⟩
    • Julien Baste, Dieter Rautenbach, Ignasi Sau Valls. Approximating maximum uniquely restricted matchings in bipartite graphs. Discrete Applied Mathematics, Elsevier, 2019, 267, pp.30-40. ⟨10.1016/j.dam.2019.04.024⟩. ⟨lirmm-02410617⟩
    • Josefran de Oliveira Bastos, Fabrício Siqueira Benevides, Guilherme Oliveira Mota, Ignasi Sau Valls. Counting Gallai 3-colorings of complete graphs. Discrete Mathematics, Elsevier, 2019, 342 (9), pp.2618-2631. ⟨10.1016/j.disc.2019.05.015⟩. ⟨lirmm-02410619⟩
    • Valentin Garnero, Christophe Paul, Ignasi Sau Valls, Dimitrios M. Thilikos. Explicit Linear Kernels for Packing Problems. Algorithmica, Springer Verlag, 2019, 81 (4), pp.1615-1656. ⟨10.1007/s00453-018-0495-5⟩. ⟨lirmm-02342736⟩
    • Victor Campos, Raul Lopes, Ana Karolinna Maia de Oliviera, Ignasi Sau Valls. Adapting The Directed Grid Theorem into an FPT Algorithm. Electronic Notes in Theoretical Computer Science, Elsevier, 2019, 346, pp.229-240. ⟨10.1016/j.entcs.2019.08.021⟩. ⟨lirmm-02410620⟩
    • Marin Bougeret, Ignasi Sau Valls. How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?. Algorithmica, Springer Verlag, 2019, 81 (10), pp.4043-4068. ⟨10.1007/s00453-018-0468-8⟩. ⟨lirmm-02410618⟩
    • Eun Jung Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau Valls, Dimitrios M. Thilikos. An FPT 2-Approximation for Tree-Cut Decomposition. Algorithmica, Springer Verlag, 2018, 80 (1), pp.116-135. ⟨10.1007/s00453-016-0245-5⟩. ⟨hal-01690385⟩
    • Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau Valls, Dimitrios M. Thilikos. An $O(\log \mathrm {OPT})$-Approximation for Covering and Packing Minor Models of $\theta _r$. Algorithmica, Springer Verlag, 2018, 80 (4), pp.1330-1356. ⟨10.1007/s00453-017-0313-5⟩. ⟨lirmm-01609998⟩
    • Sancrey Rodrigues Alves, Konrad Dabrowski, Luerbio Faria, Sulamita Klein, Ignasi Sau Valls, et al.. On the (Parameterized) Complexity of Recognizing Well-Covered $(r,l)$-graphs. Theoretical Computer Science, Elsevier, 2018, 746, pp.36-48. ⟨10.1016/j.tcs.2018.06.024⟩. ⟨lirmm-03110090⟩
    • Julien Baste, Dieter Rautenbach, Ignasi Sau Valls. Upper bounds on the uniquely restricted chromatic index. Journal of Graph Theory, Wiley, 2018, 91 (3), pp.251-258. ⟨10.1002/jgt.22429⟩. ⟨lirmm-02412578⟩
    • Pierre Aboulker, Samuel Fiorini, Tony Huynh, Gwénaël Joret, Jean-Florent Raymond, et al.. A Tight Erdös-Pósa Function for Wheel Minors. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2018, 32 (3), pp.2302-2312. ⟨10.1137/17M1153169⟩. ⟨hal-01995696⟩
    • Henri Perret Du Cray, Ignasi Sau Valls. Improved FPT algorithms for weighted independent set in bull-free graphs. Discrete Mathematics, Elsevier, 2018, 341 (2), pp.451-462. ⟨10.1016/j.disc.2017.09.012⟩. ⟨hal-01733496⟩
    • Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau Valls, Rémi Watrigant. Complexity dichotomies for the Minimum F -Overlay problem. Journal of Discrete Algorithms, Elsevier, 2018, 52-53, pp.133-142. ⟨10.1016/j.jda.2018.11.010⟩. ⟨hal-01947563⟩
    • Julio Araujo, Julien Baste, Ignasi Sau Valls. Ruling out FPT algorithms for Weighted Coloring on forests. Theoretical Computer Science, Elsevier, 2018, 729, pp.11-19. ⟨10.1016/j.tcs.2018.03.013⟩. ⟨hal-03109986⟩
    • Julien Baste, Marc Noy, Ignasi Sau Valls. On the number of labeled graphs of bounded treewidth. European Journal of Combinatorics, Elsevier, 2018, 71, pp.12-21. ⟨10.1016/j.ejc.2018.02.030⟩. ⟨hal-03109959⟩
    • Valentin Garnero, Ignasi Sau Valls. A Linear Kernel for Planar Total Dominating Set. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2018, 20 (1), ⟨10.23638/DMTCS-20-1-14⟩. ⟨lirmm-03124041⟩
    • Eun Jung Kim, Christophe Paul, Ignasi Sau Valls, 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⟩
    • Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau Valls, Dimitrios M. Thilikos. Minors in graphs of large θr-girth. European Journal of Combinatorics, Elsevier, 2017, 65, pp.106-121. ⟨10.1016/j.ejc.2017.04.011⟩. ⟨hal-01218519v2⟩
    • Didem Gözüpek, Sibel Özkan, Christophe Paul, Ignasi Sau Valls, Mordechai Shalom. Parameterized complexity of the MINCCA problem on graphs of bounded decomposability. Theoretical Computer Science, Elsevier, 2017, 690, pp.91-103. ⟨10.1016/j.tcs.2017.06.013⟩. ⟨lirmm-01630777⟩
    • Luis Pedro Montejano, Ignasi Sau Valls. 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⟩
    • Rubens Sucupira, Luerbio Faria, Sulamita Klein, Ignasi Sau Valls, Uéverton dos Santos Souza. Maximum Cuts in Edge-colored Graphs. Electronic Notes in Discrete Mathematics, Elsevier, 2017, 62, pp.87 - 92. ⟨10.1016/j.endm.2017.10.016⟩. ⟨hal-01733581⟩
    • Julio Araujo, Julien Baste, Ignasi Sau Valls. Ruling out FPT algorithms for Weighted Coloring on forests. Electronic Notes in Discrete Mathematics, Elsevier, 2017, 62, pp.195-200. ⟨10.1016/j.endm.2017.10.034⟩. ⟨hal-01733595⟩
    • Julien Baste, Luerbio Faria, Sulamita Klein, Ignasi Sau Valls. Parameterized Complexity Dichotomy for (r, ℓ)-Vertex Deletion. Theory of Computing Systems, Springer Verlag, 2017, 61 (3), pp.777-794. ⟨10.1007/s00224-016-9716-y⟩. ⟨lirmm-01630773⟩
    • Valentin Garnero, Ignasi Sau Valls, 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⟩
    • Nathann Cohen, Daniel Gonçalves, Eun Jung Kim, Christophe Paul, Ignasi Sau Valls, et al.. A polynomial-time algorithm for Outerplanar Diameter Improvement. Journal of Computer and System Sciences, Elsevier, 2017, 89, pp.315 - 327. ⟨10.1016/j.jcss.2017.05.016⟩. ⟨hal-01592242⟩
    • Julien Baste, Fairouz Beggas, Hamamache Kheddouci, Ignasi Sau Valls. 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, 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⟩
    • Jean-Florent Raymond, Ignasi Sau Valls, 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-01347430v2⟩
    • Julien Baste, Christophe Paul, Ignasi Sau Valls, Celine Scornavacca. Efficient FPT Algorithms for (Strict) Compatibility of Unrooted Phylogenetic Trees. Bulletin of Mathematical Biology, Springer Verlag, 2016, 79 (4), pp.920-938. ⟨10.1007/s11538-017-0260-y⟩. ⟨lirmm-03113710⟩
    • Julien Baste, Ignasi Sau Valls. The role of planarity in connectivity problems parameterized by treewidth. Theoretical Computer Science, Elsevier, 2015, 570, pp.1-14. ⟨10.1016/j.tcs.2014.12.010⟩. ⟨lirmm-01272664⟩
    • Valentin Garnero, Christophe Paul, Ignasi Sau Valls, 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⟩
    • Gwénaël Joret, Christophe Paul, Ignasi Sau Valls, 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 Valls, 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 Valls, Dimitrios M. Thilikos. Dynamic Programming for Graphs on Surfaces. ACM Transactions on Algorithms, Association for Computing Machinery, 2014, 10 (2), pp.8. ⟨10.1145/2556952⟩. ⟨lirmm-01083690⟩
    • Dimitrios M. Thilikos, Ignasi Sau Valls, Juanjo Rué. Asymptotic enumeration of non-crossing partitions on surfaces. Discrete Mathematics, Elsevier, 2013, pp.635-649. ⟨10.1016/j.disc.2012.12.011⟩. ⟨lirmm-00804780⟩
    • David Peleg, Ignasi Sau Valls, Mordechai Shalom. On approximating the $d$-girth of a graph. Discrete Applied Mathematics, Elsevier, 2013, 161 (16-17), pp.2587-2596. ⟨10.1016/j.dam.2013.04.022⟩. ⟨lirmm-01272717⟩
    • Ignasi Sau Valls, 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 V. Fomin, Ignasi Sau Valls, Dimitrios M. Thilikos. Fast Minor Testing in Planar Graphs. Algorithmica, Springer Verlag, 2012, 64 (1), pp.69-84. ⟨10.1007/s00453-011-9563-9⟩. ⟨lirmm-00904515⟩
    • George B. Mertzios, Ignasi Sau Valls, 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⟩
    • Omid Amini, Ignasi Sau Valls, 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⟩
    • Omid Amini, David Peleg, Stéphane Pérennes, Ignasi Sau Valls, 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⟩
    • Jean-Claude Bermond, David Coudert, Joanna Moulierac, Stéphane Pérennes, Ignasi Sau Valls, 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⟩
    • George B. Mertzios, Ignasi Sau Valls, 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⟩
    • Xavier Muñoz, Zhentao Li, Ignasi Sau Valls. 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⟩
    • Ignasi Sau Valls, 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⟩
    • Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau Valls, 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 Valls. Traffic grooming in bidirectional WDM ring networks. Networks, Wiley, 2011, 58 (1), pp.20-35. ⟨10.1002/net.20410⟩. ⟨hal-00643800⟩
    • David Coudert, Frédéric Giroire, Ignasi Sau Valls. 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⟩
    • Ignasi Sau Valls, 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⟩
    • Jean-Claude Bermond, Charles J. Colbourn, Lucia Gionfriddo, Gaetano Quattrocchi, Ignasi Sau Valls. 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 Valls. 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 Valls, 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⟩

    Conference papers40 documents

    • Rémy Belmonte, Ignasi Sau Valls. On the complexity of finding large odd induced subgraphs and odd colorings. 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Jun 2020, Leeds, United Kingdom. pp.67-79, ⟨10.1007/978-3-030-60440-0_6⟩. ⟨lirmm-02991977⟩
    • Ignasi Sau Valls, Uéverton dos Santos Souza. Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs. 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2020, Prague, Czech Republic. pp.82:1-82:15, ⟨10.4230/LIPIcs.MFCS.2020.82⟩. ⟨lirmm-02991913⟩
    • Raul Lopes, Ignasi Sau Valls. A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2020, Prague, Czech Republic. pp.68:1-68:15, ⟨10.4230/LIPIcs.MFCS.2020.68⟩. ⟨lirmm-02991855⟩
    • Marin Bougeret, Bart Jansen, Ignasi Sau Valls. Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel. 47th International Colloquium on Automata, Languages, and Programming (ICALP), Jul 2020, Saarbrücken, Germany. pp.16:1--16:19, ⟨10.4230/LIPIcs.ICALP.2020.16⟩. ⟨lirmm-02991230⟩
    • Ignasi Sau Valls, Giannos Stamoulis, Dimitrios M. Thilikos. An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes. 47th International Colloquium on Automata, Languages, and Programming (ICALP), Jul 2020, Saarbrücken, Germany. pp.95:1-95:20, ⟨10.4230/LIPIcs.ICALP.2020.95⟩. ⟨lirmm-02991704⟩
    • Paloma Lima, Vinicius Fernandes dos Santos, Ignasi Sau Valls, Uéverton dos Santos Souza. Reducing Graph Transversals via Edge Contractions. 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2020, Prague, Czech Republic. pp.64:1-64:15, ⟨10.4230/LIPIcs.MFCS.2020.64⟩. ⟨lirmm-02991812⟩
    • Julien Baste, Ignasi Sau Valls, Dimitrios M. Thilikos. A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary. 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Jan 2020, Salt Lake City, UT, United States. pp.951-970, ⟨10.1137/1.9781611975994.57⟩. ⟨lirmm-02991215⟩
    • Guilherme Gomes, Ignasi Sau Valls. Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization. 14th International Symposium on Parameterized and Exact Computation (IPEC), Sep 2019, Munich, Germany. pp.19:1--19:15, ⟨10.4230/LIPIcs.IPEC.2019.19⟩. ⟨lirmm-02410703⟩
    • Julien Baste, Ignasi Sau Valls, Dimitrios M. Thilikos. A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth. 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Aug 2018, Helsinki, Finland. pp.2:1--2:13, ⟨10.4230/LIPIcs.IPEC.2018.2⟩. ⟨lirmm-02342806⟩
    • Julio Araujo, Victor Campos, Carlos Vinícius G. C. Lima, Vinicius Fernandes dos Santos, Ignasi Sau Valls, et al.. Dual parameterization of Weighted Coloring. 13th International Symposium on Parameterized and Exact Computation (IPEC), Aug 2018, Helsinki, Finland. pp.12:1--12:14, ⟨10.4230/LIPIcs.IPEC.2018.12⟩. ⟨lirmm-02410739⟩
    • Julio Araujo, Victor Campos, Ana Karolinna Maia de Oliveira, Ignasi Sau Valls, Ana Silva. On the complexity of finding internally vertex-disjoint long directed paths. 13th Latin American Symposium on Theoretical Informatics (LATIN), Apr 2018, Buenos Aires, Argentina. pp.66-79, ⟨10.1007/978-3-319-77404-6_6⟩. ⟨lirmm-02410722⟩
    • Julien Baste, Marc Noy, Ignasi Sau Valls. On the Number of Labeled Graphs of Bounded Treewidth. 43rd International on Workshop on Graph-Theoretic Concepts in Computer Science (WG), Jun 2017, Eindhoven, Netherlands. pp.88-99, ⟨10.1007/978-3-319-68705-6_7⟩. ⟨hal-01734085⟩
    • Julien Baste, Dieter Rautenbach, Ignasi Sau Valls. Uniquely Restricted Matchings and Edge Colorings. WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2017, Eindhoven, Netherlands. pp.100-112, ⟨10.1007/978-3-319-68705-6_8⟩. ⟨hal-01734132⟩
    • Marin Bougeret, Ignasi Sau Valls. How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?. 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Sep 2017, Vienne, Austria. pp.10:1--10:13, ⟨10.4230/LIPIcs.IPEC.2017.10⟩. ⟨lirmm-01730228⟩
    • Julien Baste, Ignasi Sau Valls, Dimitrios M. Thilikos. Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth. 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Sep 2017, Vienna, Austria. pp.4:1--4:12, ⟨10.4230/LIPIcs.IPEC.2017.4⟩. ⟨hal-01733845⟩
    • Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau Valls, Rémi Watrigant. Complexity Dichotomies for the Minimum $F$-Overlay Problem. 28th International Workshop on Combinatorial Algorithms (IWOCA), Jul 2017, Newcastle, Australia. pp.116-127, ⟨10.1007/978-3-319-78825-8_10⟩. ⟨hal-01571229⟩
    • Julien Baste, Didem Gözüpek, Ignasi Sau Valls, Mordechai Shalom, Dimitrios M. Thilikos. Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter. 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Sep 2017, Vienna, Austria. pp.3:1--3:12, ⟨10.4230/LIPIcs.IPEC.2017.3⟩. ⟨hal-01733767⟩
    • Didem Gözüpek, Sibel Özkan, Christophe Paul, Ignasi Sau Valls, Mordeshai Shalom. Parameterized Complexity of the MINCCA Problem on Graphs of Bounded Decomposability. WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2016, Istanbul, Turkey. pp.195-206, ⟨10.1007/978-3-662-53536-3_17⟩. ⟨lirmm-01481360⟩
    • Sancrey Rodrigues Alves, Konrad K. Dabrowski, Luerbio Faria, Sulamita Klein, Ignasi Sau Valls, 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. pp.423-437, ⟨10.1007/978-3-319-48749-6_31⟩. ⟨lirmm-01481787⟩
    • Julien Baste, Christophe Paul, Ignasi Sau Valls, Celine Scornavacca. Efficient FPT Algorithms for (Strict) Compatibility of Unrooted Phylogenetic Trees. AAIM: Algorithmic Aspects in Information and Management, Jul 2016, Bergamo, Italy. pp.53-64, ⟨10.1007/978-3-319-41168-2_5⟩. ⟨lirmm-01481368⟩
    • Eun Jung Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau Valls, Dimitrios M. Thilikos. An FPT 2-Approximation for Tree-cut Decomposition. WAOA: Workshop on Approximation and Online Algorithms, Sep 2015, Patras, Greece. pp.35-46, ⟨10.1007/978-3-319-28684-6_4⟩. ⟨lirmm-01264015⟩
    • Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau Valls, 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. pp.122-132, ⟨10.1007/978-3-319-28684-6_11⟩. ⟨hal-01218496⟩
    • Eun Jung Kim, Christophe Paul, Ignasi Sau Valls, Dimitrios M. Thilikos. Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism. 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), Sep 2015, Patras, Greece. pp.78-89, ⟨10.4230/LIPIcs.IPEC.2015.78⟩. ⟨lirmm-01263999⟩
    • Nathann Cohen, Daniel Gonçalves, Eun Jung Kim, Christophe Paul, Ignasi Sau Valls, et al.. A Polynomial-Time Algorithm for Outerplanar Diameter Improvement. CSR: Computer Science in Russia, Jul 2015, Listvyanka, Russia. pp.123-142, ⟨10.1007/978-3-319-20297-6_9⟩. ⟨hal-01178222⟩
    • Julien Baste, Ignasi Sau Valls. The role of planarity in connectivity problems parameterized by treewidth. IPEC: International symposium on Parameterized and Exact Computation, Sep 2014, Wroclaw, Poland. pp.63-74, ⟨10.1007/978-3-319-13524-3_6⟩. ⟨lirmm-01481432⟩
    • Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau Valls, Dimitrios M. Thilikos. Covering and packing pumpkin models. ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. ⟨lirmm-01083652⟩
    • Jean-Florent Raymond, Ignasi Sau Valls, 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. ⟨lirmm-00904544⟩
    • Valentin Garnero, Christophe Paul, Ignasi Sau Valls, Dimitrios M. Thilikos. Explicit linear kernels via dynamic programming. STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2014, Lyon, France. pp.312-324, ⟨10.4230/LIPIcs.STACS.2014.312⟩. ⟨hal-01084007⟩
    • 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. pp.613-624, ⟨10.1007/978-3-642-39206-1_52⟩. ⟨lirmm-00829999⟩
    • Valentin Garnero, Ignasi Sau Valls, 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. pp.117-120. ⟨lirmm-00846771⟩
    • Juanjo Rué, Ignasi Sau Valls, Dimitrios M. Thilikos. Dynamic Programming for $H$-minor-free Graphs. COCOON: Computing and Combinatorics Conference, Aug 2012, Sydney, NSW, Australia. pp.86-97, ⟨10.1007/978-3-642-32241-9_8⟩. ⟨lirmm-00736708⟩
    • Nicolas Bousquet, Daniel Gonçalves, George Mertzios, Christophe Paul, Ignasi Sau Valls, et al.. Parameterized Domination in Circle Graphs. WG'12: 38th International Workshop on Graph Theoretic Concepts in Computer Science, Jun 2012, Jerusalem, Israel. pp.308-319, ⟨10.1007/978-3-642-34611-8_31⟩. ⟨lirmm-00738534⟩
    • David Peleg, Ignasi Sau Valls, Mordechai Shalom. On Approximating the $d$-Girth of a Graph. SOFSEM, Jan 2011, Nový Smokovec, Slovakia. pp.467-481, ⟨10.1007/978-3-642-18381-2_39⟩. ⟨lirmm-00736705⟩
    • Gwénaël Joret, Christophe Paul, Ignasi Sau Valls, Saket Saurabh, Stéphan Thomassé. Hitting and Harvesting Pumpkins. ESA: European Symposium on Algorithms, Sep 2011, Saarbrücken, Germany. pp.394-407. ⟨lirmm-00642341⟩
    • Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau Valls, Dimitrios M. Thilikos. Fast Minor Testing in Planar Graphs. ESA: European Symposium on Algorithms, Sep 2010, Liverpool, United Kingdom. pp.97-109, ⟨10.1007/978-3-642-15775-2_9⟩. ⟨lirmm-00736769⟩
    • Juanjo Rué, Ignasi Sau Valls, Dimitrios M. Thilikos. Dynamic programming for graphs on surfaces. ICALP: International Colloquium on Automata, Languages and Programming, 2010, Bordeaux, France. pp.372-383. ⟨lirmm-00736703⟩
    • George B. Mertzios, Ignasi Sau Valls, Shmuel Zaks. The Recognition of Tolerance and Bounded Tolerance Graphs. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.585-596. ⟨inria-00455774⟩
    • David Coudert, Frédéric Giroire, Ignasi Sau Valls. Edge-Simple Circuits Through 10 Ordered Vertices in Square Grids. International Workshop on Combinatorial Algorithms -- IWOCA, Jun 2009, Hradec nad Moravicì, Czech Republic. ⟨inria-00429146⟩
    • Omid Amini, Stéphane Pérennes, Ignasi Sau Valls. 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. ⟨inria-00176960⟩
    • Jean-Claude Bermond, David Coudert, Xavier Munoz, Ignasi Sau Valls. Traffic Grooming in Bidirectional WDM Ring Networks. International Conference on Transparent Optical Networks (ICTON), Jun 2006, Nottingham, United Kingdom. pp.19 - 22, ⟨10.1109/ICTON.2006.248390⟩. ⟨inria-00429168⟩

    Book sections1 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⟩

    Directions of work or proceedings1 document

    • Ignasi Sau Valls, Dimitrios M. Thilikos. Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers. LNCS (11789), 2019, 978-3-030-30785-1. ⟨10.1007/978-3-030-30786-8⟩. ⟨lirmm-02342784⟩

    Preprints, Working Papers, ...3 documents

    • Luerbio Faria, Sulamita Klein, Ignasi Sau Valls, Rubens Sucupira. Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs. 2016. ⟨lirmm-01272714⟩
    • Luis Pedro Montejano, Ignasi Sau Valls. On the complexity of computing the $k$-restricted edge-connectivity of a graph. 2016. ⟨lirmm-01272707⟩
    • Julien Baste, Luerbio Faria, Sulamita Klein, Ignasi Sau Valls. Parameterized complexity dichotomy for $(r,\ell)$-Vertex Deletion. 2016. ⟨lirmm-01272704⟩

    Reports10 documents

    • Eun Jung Kim, Christophe Paul, Ignasi Sau Valls, 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 Valls, 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 Valls, Rémi Watrigant. Complexity Dichotomies for the Minimum F-Overlay Problem. [Research Report] RR-9045, Inria Sophia Antipolis. 2013, pp.16. ⟨hal-01490535⟩
    • Juanjo Rué, Ignasi Sau Valls, Dimitrios M. Thilikos. Dynamic Programming for Graphs on Surfaces. [Research Report] RR-7166, INRIA. 2009, pp.39. ⟨inria-00443582⟩
    • Jean-Claude Bermond, Charles J. Colbourn, Lucia Gionfriddo, Gaetano Quattrocchi, Ignasi Sau Valls. Drop cost and wavelength optimal two-period grooming with ratio 4. [Research Report] RR-7101, INRIA. 2009, pp.24. ⟨inria-00432801⟩
    • Jean-Claude Bermond, David Coudert, Joanna Moulierac, Stéphane Pérennes, Ignasi Sau Valls, 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 Valls. Circuit visiting 10 ordered vertices in infinite grids. [Research Report] RR-6910, INRIA. 2009. ⟨inria-00378586⟩
    • Omid Amini, Ignasi Sau Valls, Saket Saurabh. Parameterized Complexity of the Smallest Degree Constraint Subgraph Problem. [Research Report] RR-6237, INRIA. 2007, pp.20. ⟨inria-00157970v4⟩
    • Omid Amini, Stéphane Pérennes, Ignasi Sau Valls. Hardness and Approximation of Traffic Grooming. [Research Report] RR-6236, INRIA. 2007, pp.17. ⟨inria-00158341v3⟩

    Theses1 document

    • Ignasi Sau Valls. 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⟩

    Habilitation à diriger des recherches1 document

    • Ignasi Sau Valls. Some Contributions to Parameterized Complexity. Computer Science [cs]. Université de Montpellier, 2018. ⟨tel-02079241⟩