Bougeret, Marin; Jansen, Bart M. P.; Sau, Ignasi Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel. (English) Zbl 1503.05095 SIAM J. Discrete Math. 36, No. 4, 2737-2773 (2022). MSC: 05C70 05C85 05C83 05C75 PDFBibTeX XMLCite \textit{M. Bougeret} et al., SIAM J. Discrete Math. 36, No. 4, 2737--2773 (2022; Zbl 1503.05095) Full Text: DOI arXiv
Belmonte, Rémy; Sau, Ignasi On the complexity of finding large odd induced subgraphs and odd colorings. (English) Zbl 1515.68224 Algorithmica 83, No. 8, 2351-2373 (2021). MSC: 68R10 05C15 05C85 68Q25 68Q27 PDFBibTeX XMLCite \textit{R. Belmonte} and \textit{I. Sau}, Algorithmica 83, No. 8, 2351--2373 (2021; Zbl 1515.68224) Full Text: DOI arXiv
Gomes, Guilherme C. M.; Sau, Ignasi Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization. (English) Zbl 1516.68062 Algorithmica 83, No. 6, 1677-1706 (2021). MSC: 68R10 05C70 05C85 68Q17 68Q27 68W40 PDFBibTeX XMLCite \textit{G. C. M. Gomes} and \textit{I. Sau}, Algorithmica 83, No. 6, 1677--1706 (2021; Zbl 1516.68062) Full Text: DOI arXiv Link
Baste, Julien; Gözüpek, Didem; Paul, Christophe; Sau, Ignasi; Shalom, Mordechai; Thilikos, Dimitrios M. Parameterized complexity of finding a spanning tree with minimum reload cost diameter. (English) Zbl 1528.68148 Networks 75, No. 3, 259-277 (2020). MSC: 68Q27 68Q17 68R10 90C35 PDFBibTeX XMLCite \textit{J. Baste} et al., Networks 75, No. 3, 259--277 (2020; Zbl 1528.68148) Full Text: DOI
Belmonte, Rémy; Sau, Ignasi On the complexity of finding large odd induced subgraphs and odd colorings. (English) Zbl 07636196 Adler, Isolde (ed.) et al., Graph-theoretic concepts in computer science. 46th international workshop, WG 2020, Leeds, UK, June 24–26, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12301, 67-79 (2020). MSC: 68R10 PDFBibTeX XMLCite \textit{R. Belmonte} and \textit{I. Sau}, Lect. Notes Comput. Sci. 12301, 67--79 (2020; Zbl 07636196) Full Text: DOI
Araújo, Júlio; Campos, Victor A.; Maia, Ana Karolinna; Sau, Ignasi; Silva, Ana On the complexity of finding internally vertex-disjoint long directed paths. (English) Zbl 1433.68164 Algorithmica 82, No. 6, 1616-1639 (2020). MSC: 68Q25 05C20 05C38 05C70 05C85 68Q17 68Q27 68R10 PDFBibTeX XMLCite \textit{J. Araújo} et al., Algorithmica 82, No. 6, 1616--1639 (2020; Zbl 1433.68164) Full Text: DOI arXiv
Gomes, Guilherme C. M.; Sau, Ignasi Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization. (English) Zbl 1516.68063 Jansen, Bart M. P. (ed.) et al., 14th international symposium on parameterized and exact computation, IPEC 2019, Munich, Germany, September 11–13, 2019. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 148, Article 19, 15 p. (2019). MSC: 68R10 05C70 05C85 68Q17 68Q27 68W40 PDFBibTeX XMLCite \textit{G. C. M. Gomes} and \textit{I. Sau}, LIPIcs -- Leibniz Int. Proc. Inform. 148, Article 19, 15 p. (2019; Zbl 1516.68063) Full Text: DOI
Baste, Julien; Rautenbach, Dieter; Sau, Ignasi Approximating maximum uniquely restricted matchings in bipartite graphs. (English) Zbl 1419.05173 Discrete Appl. Math. 267, 30-40 (2019). MSC: 05C70 68W25 PDFBibTeX XMLCite \textit{J. Baste} et al., Discrete Appl. Math. 267, 30--40 (2019; Zbl 1419.05173) Full Text: DOI Link
Baste, Julien; Gözüpek, Didem; Paul, Christophe; Sau, Ignasi; Shalom, Mordechai; Thilikos, Dimitrios M. Parameterized complexity of finding a spanning tree with minimum reload cost diameter. (English) Zbl 1443.68119 Lokshtanov, Daniel (ed.) et al., 12th international symposium on parameterized and exact computation, IPEC 2017, Vienna, Austria, September 6–8, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 89, Article 3, 12 p. (2018). MSC: 68R10 68Q17 68Q27 PDFBibTeX XMLCite \textit{J. Baste} et al., LIPIcs -- Leibniz Int. Proc. Inform. 89, Article 3, 12 p. (2018; Zbl 1443.68119) Full Text: DOI arXiv
Araújo, Júlio; Campos, Victor A.; Maia, Ana Karolinna; Sau, Ignasi; Silva, Ana On the complexity of finding internally vertex-disjoint long directed paths. (English) Zbl 1485.68171 Bender, Michael A. (ed.) et al., Latin 2018: theoretical informatics. 13th Latin American symposium, Buenos Aires, Argentina, April 16–19, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10807, 66-79 (2018). MSC: 68R10 05C20 68Q17 68Q25 68Q27 PDFBibTeX XMLCite \textit{J. Araújo} et al., Lect. Notes Comput. Sci. 10807, 66--79 (2018; Zbl 1485.68171) Full Text: DOI arXiv
Alves, Sancrey Rodrigues; Dabrowski, Konrad K.; Faria, Luerbio; Klein, Sulamita; Sau, Ignasi; Souza, Uéverton S. On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph. (English) Zbl 1400.68078 Theor. Comput. Sci. 746, 36-48 (2018). MSC: 68Q25 05C70 68Q17 PDFBibTeX XMLCite \textit{S. R. Alves} et al., Theor. Comput. Sci. 746, 36--48 (2018; Zbl 1400.68078) Full Text: DOI
Kim, Eun Jung; Oum, Sang-il; Paul, Christophe; Sau, Ignasi; Thilikos, Dimitrios M. An FPT 2-approximation for tree-cut decomposition. (English) Zbl 1386.68221 Algorithmica 80, No. 1, 116-135 (2018). MSC: 68W25 05C05 05C70 05C85 68Q25 PDFBibTeX XMLCite \textit{E. J. Kim} et al., Algorithmica 80, No. 1, 116--135 (2018; Zbl 1386.68221) Full Text: DOI arXiv
du Cray, Henri Perret; Sau, Ignasi Improved FPT algorithms for weighted independent set in bull-free graphs. (English) Zbl 1376.05155 Discrete Math. 341, No. 2, 451-462 (2018). MSC: 05C85 05C15 68Q25 PDFBibTeX XMLCite \textit{H. P. du Cray} and \textit{I. Sau}, Discrete Math. 341, No. 2, 451--462 (2018; Zbl 1376.05155) Full Text: DOI
Baste, Julien; Rautenbach, Dieter; Sau, Ignasi Uniquely restricted matchings and edge colorings. (English) Zbl 1483.05171 Bodlaender, Hans L. (ed.) et al., Graph-theoretic concepts in computer science. 43rd international workshop, WG 2017, Eindhoven, The Netherlands, June 21–23, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10520, 100-112 (2017). MSC: 05C85 05C15 05C70 68W25 PDFBibTeX XMLCite \textit{J. Baste} et al., Lect. Notes Comput. Sci. 10520, 100--112 (2017; Zbl 1483.05171) Full Text: DOI arXiv
Baste, Julien; Faria, Luerbio; Klein, Sulamita; Sau, Ignasi Parameterized complexity dichotomy for \((r, \ell)\)-Vertex Deletion. (English) Zbl 1378.68057 Theory Comput. Syst. 61, No. 3, 777-794 (2017). MSC: 68Q25 68Q17 68R10 PDFBibTeX XMLCite \textit{J. Baste} et al., Theory Comput. Syst. 61, No. 3, 777--794 (2017; Zbl 1378.68057) Full Text: DOI arXiv
Gözüpek, Didem; Özkan, Sibel; Paul, Christophe; Sau, Ignasi; Shalom, Mordechai Parameterized complexity of the MinCCA problem on graphs of bounded decomposability. (English) Zbl 1372.68126 Theor. Comput. Sci. 690, 91-103 (2017). MSC: 68Q25 05C15 05C85 68Q17 PDFBibTeX XMLCite \textit{D. Gözüpek} et al., Theor. Comput. Sci. 690, 91--103 (2017; Zbl 1372.68126) Full Text: DOI arXiv
Kim, Eun Jung; Paul, Christophe; Sau, Ignasi; Thilikos, Dimitrios M. Parameterized algorithms for min-max multiway cut and list digraph homomorphism. (English) Zbl 1370.68131 J. Comput. Syst. Sci. 86, 191-206 (2017). MSC: 68Q25 05C85 PDFBibTeX XMLCite \textit{E. J. Kim} et al., J. Comput. Syst. Sci. 86, 191--206 (2017; Zbl 1370.68131) Full Text: DOI Link
Baste, Julien; Beggas, Fairouz; Kheddouci, Hamamache; Sau, Ignasi On the parameterized complexity of the edge monitoring problem. (English) Zbl 1404.68080 Inf. Process. Lett. 121, 39-44 (2017). MSC: 68R10 05C85 68Q17 68Q25 PDFBibTeX XMLCite \textit{J. Baste} et al., Inf. Process. Lett. 121, 39--44 (2017; Zbl 1404.68080) Full Text: DOI
Montejano, Luis Pedro; Sau, Ignasi On the complexity of computing the \(k\)-restricted edge-connectivity of a graph. (English) Zbl 1356.68107 Theor. Comput. Sci. 662, 31-39 (2017). MSC: 68Q25 05C40 05C85 68Q17 PDFBibTeX XMLCite \textit{L. P. Montejano} and \textit{I. Sau}, Theor. Comput. Sci. 662, 31--39 (2017; Zbl 1356.68107) Full Text: DOI arXiv
Alves, Sancrey Rodrigues; Dabrowski, Konrad K.; Faria, Luerbio; Klein, Sulamita; Sau, Ignasi; dos Santos Souza, Uéverton On the (parameterized) complexity of recognizing well-covered \((r,\ell)\)-graphs. (English) Zbl 1483.68247 Chan, T-H. Hubert (ed.) et al., Combinatorial optimization and applications. 10th international conference, COCOA 2016, Hong Kong, China, December 16–18, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10043, 423-437 (2016). MSC: 68R10 05C69 05C70 68Q17 68Q25 68Q27 PDFBibTeX XMLCite \textit{S. R. Alves} et al., Lect. Notes Comput. Sci. 10043, 423--437 (2016; Zbl 1483.68247) Full Text: DOI arXiv Link
Gözüpek, Didem; Özkan, Sibel; Paul, Christophe; Sau, Ignasi; Shalom, Mordechai Parameterized complexity of the MINCCA problem on graphs of bounded decomposability. (English) Zbl 1417.68068 Heggernes, Pinar (ed.), Graph-theoretic concepts in computer science. 42nd international workshop, WG 2016, Istanbul, Turkey, June 22–24, 2016. Revised selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 9941, 195-206 (2016). MSC: 68Q25 05C15 05C85 68Q17 PDFBibTeX XMLCite \textit{D. Gözüpek} et al., Lect. Notes Comput. Sci. 9941, 195--206 (2016; Zbl 1417.68068) Full Text: DOI arXiv
Baste, Julien; Paul, Christophe; Sau, Ignasi; Scornavacca, Celine Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees. (English) Zbl 1480.92142 Dondi, Riccardo (ed.) et al., Algorithmic aspects in information and management. 11th international conference, AAIM 2016, Bergamo, Italy, July 18–20, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9778, 53-64 (2016). MSC: 92D15 05C90 PDFBibTeX XMLCite \textit{J. Baste} et al., Lect. Notes Comput. Sci. 9778, 53--64 (2016; Zbl 1480.92142) Full Text: DOI arXiv
Montejano, Luis Pedro; Sau, Ignasi On the complexity of computing the \(k\)-restricted edge-connectivity of a graph. (English) Zbl 1417.68071 Mayr, Ernst W. (ed.), Graph-theoretic concepts in computer science. 41st international workshop, WG 2015, Garching, Germany, June 17–19, 2015. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 9224, 219-233 (2016). MSC: 68Q25 05C40 05C85 68Q17 PDFBibTeX XMLCite \textit{L. P. Montejano} and \textit{I. Sau}, Lect. Notes Comput. Sci. 9224, 219--233 (2016; Zbl 1417.68071) Full Text: DOI
Kim, Eun Jung; Paul, Christophe; Sau, Ignasi; Thilikos, Dimitrios M. Parameterized algorithms for MIN-MAX multiway cut and List digraph homomorphism. (English) Zbl 1378.68084 Husfeldt, Thore (ed.) et al., 10th international symposium on parameterized and exact computation, IPEC 2015, Patras, Greece, September 16–18, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-92-7). LIPIcs – Leibniz International Proceedings in Informatics 43, 78-89 (2015). MSC: 68Q25 05C85 68R10 PDFBibTeX XMLCite \textit{E. J. Kim} et al., LIPIcs -- Leibniz Int. Proc. Inform. 43, 78--89 (2015; Zbl 1378.68084) Full Text: DOI arXiv
Kim, Eunjung; Oum, Sang-il; Paul, Christophe; Sau, Ignasi; Thilikos, Dimitrios M. An FPT 2-approximation for tree-cut decomposition. (English) Zbl 1386.68222 Sanità, Laura (ed.) et al., Approximation and online algorithms. 13th international workshop, WAOA 2015, Patras, Greece, September 17–18, 2015. Revised selected papers. Cham: Springer (ISBN 978-3-319-28683-9/pbk; 978-3-319-28684-6/ebook). Lecture Notes in Computer Science 9499, 35-46 (2015). MSC: 68W25 05C05 05C70 05C85 68Q25 PDFBibTeX XMLCite \textit{E. Kim} et al., Lect. Notes Comput. Sci. 9499, 35--46 (2015; Zbl 1386.68222) Full Text: DOI arXiv
Cray, Henri; Sau, Ignasi Improved FPT algorithms for weighted independent set in bull-free graphs. (English) Zbl 1456.68066 Cygan, Marek (ed.) et al., Parameterized and exact computation. 9th international symposium, IPEC 2014, Wroclaw, Poland, September 10–12, 2014. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 8894, 282-293 (2014). MSC: 68Q27 05C15 05C69 05C85 68W40 PDFBibTeX XMLCite \textit{H. Cray} and \textit{I. Sau}, Lect. Notes Comput. Sci. 8894, 282--293 (2014; Zbl 1456.68066) Full Text: DOI arXiv
Joret, Gwenaël; Paul, Christophe; Sau, Ignasi; Saurabh, Saket; Thomassé, Stéphan Hitting and harvesting pumpkins. (English) Zbl 1305.05221 SIAM J. Discrete Math. 28, No. 3, 1363-1390 (2014). MSC: 05C85 05C83 68Q25 68W25 PDFBibTeX XMLCite \textit{G. Joret} et al., SIAM J. Discrete Math. 28, No. 3, 1363--1390 (2014; Zbl 1305.05221) Full Text: DOI arXiv
Peleg, David; Sau, Ignasi; Shalom, Mordechai On approximating the \(d\)-girth of a graph. (English) Zbl 1285.05041 Discrete Appl. Math. 161, No. 16-17, 2587-2596 (2013). MSC: 05C10 05C07 05C35 05C38 68Q17 68W20 68W25 PDFBibTeX XMLCite \textit{D. Peleg} et al., Discrete Appl. Math. 161, No. 16--17, 2587--2596 (2013; Zbl 1285.05041) Full Text: DOI
Adler, Isolde; Dorn, Frederic; Fomin, Fedor V.; Sau, Ignasi; Thilikos, Dimitrios M. Fast minor testing in planar graphs. (English) Zbl 1254.05185 Algorithmica 64, No. 1, 69-84 (2012). Reviewer: Ján Plesník (Bratislava) MSC: 05C83 05C10 05C85 90C39 PDFBibTeX XMLCite \textit{I. Adler} et al., Algorithmica 64, No. 1, 69--84 (2012; Zbl 1254.05185) Full Text: DOI Link
Amini, Omid; Sau, Ignasi; Saurabh, Saket Parameterized complexity of finding small degree-constrained subgraphs. (English) Zbl 1242.68119 J. Discrete Algorithms 10, 70-83 (2012). MSC: 68Q25 05C85 90C39 PDFBibTeX XMLCite \textit{O. Amini} et al., J. Discrete Algorithms 10, 70--83 (2012; Zbl 1242.68119) Full Text: DOI
Mertzios, George B.; Sau, Ignasi; Zaks, Shmuel The recognition of tolerance and bounded tolerance graphs. (English) Zbl 1235.05098 SIAM J. Comput. 40, No. 5, 1234-1257 (2011). MSC: 05C62 68Q25 68R10 05C17 PDFBibTeX XMLCite \textit{G. B. Mertzios} et al., SIAM J. Comput. 40, No. 5, 1234--1257 (2011; Zbl 1235.05098) Full Text: DOI Link
Joret, Gwenaël; Paul, Christophe; Sau, Ignasi; Saurabh, Saket; Thomassé, Stéphan Hitting and harvesting pumpkins. (English) Zbl 1346.68111 Demetrescu, Camil (ed.) et al., Algorithms – ESA 2011. 19th annual European symposium, Saarbrücken, Germany, September 5–9, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-23718-8/pbk). Lecture Notes in Computer Science 6942, 394-407 (2011). MSC: 68Q25 05C75 05C83 05C85 68W25 PDFBibTeX XMLCite \textit{G. Joret} et al., Lect. Notes Comput. Sci. 6942, 394--407 (2011; Zbl 1346.68111) Full Text: DOI arXiv
Peleg, David; Sau, Ignasi; Shalom, Mordechai On approximating the \(d\)-girth of a graph. (English) Zbl 1298.68297 Černá, Ivana (ed.) et al., SOFSEM 2011: Theory and practice of computer science. 37th conference on current trends in theory and practice of computer science, Nový Smokovec, Slovakia, January 22–28, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-18380-5/pbk). Lecture Notes in Computer Science 6543, 467-481 (2011). MSC: 68W25 05C35 68Q17 PDFBibTeX XMLCite \textit{D. Peleg} et al., Lect. Notes Comput. Sci. 6543, 467--481 (2011; Zbl 1298.68297) Full Text: DOI
Sau, Ignasi; Thilikos, Dimitrios M. Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs. (English) Zbl 1192.90239 J. Discrete Algorithms 8, No. 3, 330-338 (2010). MSC: 90C35 PDFBibTeX XMLCite \textit{I. Sau} and \textit{D. M. Thilikos}, J. Discrete Algorithms 8, No. 3, 330--338 (2010; Zbl 1192.90239) Full Text: DOI
Sau, Ignasi; Thilikos, Dimitrios M. Subexponential parameterized algorithms for bounded-degree connected subgraph problems on planar graphs. (English) Zbl 1267.05271 Koster, Arie (ed.) et al., DIMAP workshop on algorithmic graph theory. Extended abstracts from the workshop held at the University of Warwick, Coventry, UK, March 23–25, 2009. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 32, 59-66 (2009). MSC: 05C85 PDFBibTeX XMLCite \textit{I. Sau} and \textit{D. M. Thilikos}, Electron. Notes Discrete Math. 32, 59--66 (2009; Zbl 1267.05271) Full Text: DOI