Agrawal, Akanksha; Knudsen, Kristine V. K.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav The parameterized complexity of guarding almost convex polygons. (English) Zbl 07802594 Discrete Comput. Geom. 71, No. 2, 358-398 (2024). MSC: 68-XX 65L10 65L12 65L20 65L70 PDFBibTeX XMLCite \textit{A. Agrawal} et al., Discrete Comput. Geom. 71, No. 2, 358--398 (2024; Zbl 07802594) Full Text: DOI
Lokshtanov, Daniel; Misra, Pranabendu; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav An ETH-tight algorithm for bidirected Steiner connectivity. (English) Zbl 07789730 Morin, Pat (ed.) et al., Algorithms and data structures. 18th international symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14079, 588-604 (2023). MSC: 68P05 68Wxx PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., Lect. Notes Comput. Sci. 14079, 588--604 (2023; Zbl 07789730) Full Text: DOI
Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav Polynomial kernel for interval vertex deletion. (English) Zbl 07753162 ACM Trans. Algorithms 19, No. 2, Article No. 11, 68 p. (2023). MSC: 68-XX PDFBibTeX XMLCite \textit{A. Agrawal} et al., ACM Trans. Algorithms 19, No. 2, Article No. 11, 68 p. (2023; Zbl 07753162) Full Text: DOI
Didimo, Walter; Gupta, Siddharth; Kindermann, Philipp; Liotta, Giuseppe; Wolff, Alexander; Zehavi, Meirav Parameterized approaches to orthogonal compaction. (English) Zbl 07726599 Gąsieniec, Leszek (ed.), SOFSEM 2023: theory and practice of computer science. 48th international conference on current trends in theory and practice of computer science, SOFSEM 2023, Nový Smokovec, Slovakia, January 15–18, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13878, 111-125 (2023). MSC: 68R10 68Q27 PDFBibTeX XMLCite \textit{W. Didimo} et al., Lect. Notes Comput. Sci. 13878, 111--125 (2023; Zbl 07726599) Full Text: DOI arXiv
Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number. (English) Zbl 07704069 Algorithmica 85, No. 7, 2065-2086 (2023). MSC: 68Wxx 05Cxx 05C20 05C85 68Q25 68R05 68W40 97K20 97P20 PDFBibTeX XMLCite \textit{P. Misra} et al., Algorithmica 85, No. 7, 2065--2086 (2023; Zbl 07704069) Full Text: DOI
Gupta, Siddharth; Sa’ar, Guy; Zehavi, Meirav Grid recognition: classical and parameterized computational perspectives. (English) Zbl 07695009 J. Comput. Syst. Sci. 136, 17-62 (2023). MSC: 68-XX PDFBibTeX XMLCite \textit{S. Gupta} et al., J. Comput. Syst. Sci. 136, 17--62 (2023; Zbl 07695009) Full Text: DOI arXiv
Bhore, Sujoy; Carmi, Paz; Kolay, Sudeshna; Zehavi, Meirav Parameterized study of Steiner tree on unit disk graphs. (English) Zbl 07677079 Algorithmica 85, No. 1, 133-152 (2023). MSC: 68Wxx 05Cxx PDFBibTeX XMLCite \textit{S. Bhore} et al., Algorithmica 85, No. 1, 133--152 (2023; Zbl 07677079) Full Text: DOI arXiv
Saurabh, Saket; Zehavi, Meirav Parameterized complexity of multi-node hubs. (English) Zbl 07601249 J. Comput. Syst. Sci. 131, 64-85 (2023). MSC: 68R10 68Q27 PDFBibTeX XMLCite \textit{S. Saurabh} and \textit{M. Zehavi}, J. Comput. Syst. Sci. 131, 64--85 (2023; Zbl 07601249) Full Text: DOI
Golovach, Petr A. (ed.); Zehavi, Meirav (ed.) Special issue dedicated to the 16th international symposium on parameterized and exact computation. (English) Zbl 07608285 Algorithmica 84, No. 11, 3107-3109 (2022). MSC: 68Wxx 05Cxx 00Bxx PDFBibTeX XMLCite \textit{P. A. Golovach} (ed.) and \textit{M. Zehavi} (ed.), Algorithmica 84, No. 11, 3107--3109 (2022; Zbl 07608285) Full Text: DOI
Zehavi, Meirav Parameterized analysis and crossing minimization problems. (English) Zbl 1507.68232 Comput. Sci. Rev. 45, Article ID 100490, 14 p. (2022). MSC: 68R10 68Q27 68W05 68-01 68-02 PDFBibTeX XMLCite \textit{M. Zehavi}, Comput. Sci. Rev. 45, Article ID 100490, 14 p. (2022; Zbl 1507.68232) Full Text: DOI
Gupta, Sushmita; Roy, Sanjukta; Saurabh, Saket; Zehavi, Meirav Resolute control: forbidding candidates from winning an election is hard. (English) Zbl 07533865 Theor. Comput. Sci. 915, 74-89 (2022). MSC: 68Qxx PDFBibTeX XMLCite \textit{S. Gupta} et al., Theor. Comput. Sci. 915, 74--89 (2022; Zbl 07533865) Full Text: DOI
Agrawal, Akanksha; Kolay, Sudeshna; Zehavi, Meirav Parameter analysis for guarding terrains. (English) Zbl 07495630 Algorithmica 84, No. 4, 961-981 (2022). MSC: 68Wxx 05Cxx PDFBibTeX XMLCite \textit{A. Agrawal} et al., Algorithmica 84, No. 4, 961--981 (2022; Zbl 07495630) Full Text: DOI
Gupta, Siddharth; Sa’ar, Guy; Zehavi, Meirav Grid recognition: classical and parameterized computational perspectives. (English) Zbl 07788610 Ahn, Hee-Kap (ed.) et al., 32nd international symposium on algorithms and computation, ISAAC 2021, Fukuoka, Japan, December 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 212, Article 37, 15 p. (2021). MSC: 68Wxx PDFBibTeX XMLCite \textit{S. Gupta} et al., LIPIcs -- Leibniz Int. Proc. Inform. 212, Article 37, 15 p. (2021; Zbl 07788610) Full Text: DOI
Lokshtanov, Daniel; Misra, Pranabendu; Ramanujan, M. S.; Saurabh, Saket; Zehavi, Meirav FPT-approximation for FPT problems. (English) Zbl 07788352 Marx, Dániel (ed.), Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10–13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 199-218 (2021). MSC: 68Wxx PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., in: Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10--13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 199--218 (2021; Zbl 07788352) Full Text: DOI
Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav Efficient computation of representative weight functions with applications to parameterized counting (extended version). (English) Zbl 07788351 Marx, Dániel (ed.), Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10–13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 179-198 (2021). MSC: 68Wxx PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., in: Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10--13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 179--198 (2021; Zbl 07788351) Full Text: DOI
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Multiplicative parameterization above a guarantee. (English) Zbl 1495.68103 ACM Trans. Comput. Theory 13, No. 3, Paper No. 18, 16 p. (2021). MSC: 68Q27 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., ACM Trans. Comput. Theory 13, No. 3, Paper No. 18, 16 p. (2021; Zbl 1495.68103) Full Text: DOI
Fomin, Fedor V.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav ETH-tight algorithms for long path and cycle on unit disk graphs. (English) Zbl 1499.68366 J. Comput. Geom. 12, No. 2, 126-148 (2021). MSC: 68U05 05C62 05C85 68Q25 68W40 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., J. Comput. Geom. 12, No. 2, 126--148 (2021; Zbl 1499.68366) Full Text: DOI arXiv
Fomin, Fedor V.; Lokshtanov, Daniel; Mihajlin, Ivan; Saurabh, Saket; Zehavi, Meirav Computation of Hadwiger number and related contraction problems. Tight lower bounds. (English) Zbl 1495.68169 ACM Trans. Comput. Theory 13, No. 2, Article No. 10, 25 p. (2021). MSC: 68R10 68Q17 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., ACM Trans. Comput. Theory 13, No. 2, Article No. 10, 25 p. (2021; Zbl 1495.68169) Full Text: DOI arXiv
Gupta, Sushmita; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav Popular matching in roommates setting is NP-hard. (English) Zbl 1495.68093 ACM Trans. Comput. Theory 13, No. 2, Article No. 9, 20 p. (2021). MSC: 68Q17 05C70 91B68 PDFBibTeX XMLCite \textit{S. Gupta} et al., ACM Trans. Comput. Theory 13, No. 2, Article No. 9, 20 p. (2021; Zbl 1495.68093) Full Text: DOI arXiv
Golovach, Petr A. (ed.); Zehavi, Meirav (ed.) 16th international symposium on parameterized and exact computation, IPEC 2021, Lisbon, Portugal, September 8–10, 2021. (English) Zbl 1482.68023 LIPIcs – Leibniz International Proceedings in Informatics 214. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-216-7). xvii, 35 articles, not consecutively paged, electronic only, open access (2021). MSC: 68-06 68Q25 68Q27 68Wxx 00B25 PDFBibTeX XMLCite \textit{P. A. Golovach} (ed.) and \textit{M. Zehavi} (ed.), 16th international symposium on parameterized and exact computation, IPEC 2021, Lisbon, Portugal, September 8--10, 2021. Wadern: Schloss Dagstuhl -- Leibniz Zentrum für Informatik (2021; Zbl 1482.68023) Full Text: DOI Link
Björklund, Andreas; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav Approximate counting of \(k\)-paths: simpler, deterministic, and in polynomial space. (English) Zbl 07475106 ACM Trans. Algorithms 17, No. 3, Article No. 26, 44 p. (2021). MSC: 68-XX PDFBibTeX XMLCite \textit{A. Björklund} et al., ACM Trans. Algorithms 17, No. 3, Article No. 26, 44 p. (2021; Zbl 07475106) Full Text: DOI
Gutin, Gregory; Wahlström, Magnus; Zehavi, Meirav \(r\)-simple \(k\)-path and related problems parameterized by \(k/r\). (English) Zbl 07471495 ACM Trans. Algorithms 17, No. 1, Article No. 10, 64 p. (2021). MSC: 68Q27 05C38 05C70 05C85 68Q17 68R10 PDFBibTeX XMLCite \textit{G. Gutin} et al., ACM Trans. Algorithms 17, No. 1, Article No. 10, 64 p. (2021; Zbl 07471495) Full Text: DOI arXiv
Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav Parameterized algorithms. (English) Zbl 07469247 Roughgarden, Tim (ed.), Beyond the worst-case analysis of algorithms. Cambridge: Cambridge University Press. 27-51 (2021). MSC: 68W40 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., in: Beyond the worst-case analysis of algorithms. Cambridge: Cambridge University Press. 27--51 (2021; Zbl 07469247) Full Text: DOI Link
Gupta, Sushmita; Roy, Sanjukta; Saurabh, Saket; Zehavi, Meirav Balanced stable marriage: how close is close enough? (English) Zbl 1517.68144 Theor. Comput. Sci. 883, 19-43 (2021). MSC: 68Q27 91B68 PDFBibTeX XMLCite \textit{S. Gupta} et al., Theor. Comput. Sci. 883, 19--43 (2021; Zbl 1517.68144) Full Text: DOI arXiv
Madathil, Jayakrishnan; Sharma, Roohani; Zehavi, Meirav A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs. (English) Zbl 1516.68068 Algorithmica 83, No. 6, 1861-1884 (2021). MSC: 68R10 05C20 05C70 05C85 68Q27 PDFBibTeX XMLCite \textit{J. Madathil} et al., Algorithmica 83, No. 6, 1861--1884 (2021; Zbl 1516.68068) Full Text: DOI Link
Bessy, Stéphane; Bougeret, Marin; Krithika, R.; Sahu, Abhishek; Saurabh, Saket; Thiebaut, Jocelyn; Zehavi, Meirav Packing arc-disjoint cycles in tournaments. (English) Zbl 1512.68193 Algorithmica 83, No. 5, 1393-1420 (2021). MSC: 68R10 05C20 05C38 05C70 05C85 68Q27 PDFBibTeX XMLCite \textit{S. Bessy} et al., Algorithmica 83, No. 5, 1393--1420 (2021; Zbl 1512.68193) Full Text: DOI Link
Agrawal, Akanksha; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Simultaneous feedback edge set: a parameterized perspective. (English) Zbl 1512.68117 Algorithmica 83, No. 2, 753-774 (2021). MSC: 68Q27 05C85 68Q17 68R10 68W40 PDFBibTeX XMLCite \textit{A. Agrawal} et al., Algorithmica 83, No. 2, 753--774 (2021; Zbl 1512.68117) Full Text: DOI Link
Fomin, Fedor V.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav ETH-tight algorithms for long path and cycle on unit disk graphs. (English) Zbl 07760173 Cabello, Sergio (ed.) et al., 36th international symposium on computational geometry, SoCG 2020, Zürich, Switzerland (virtual conference), June 23–26, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 164, Article 44, 18 p. (2020). MSC: 68U05 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., LIPIcs -- Leibniz Int. Proc. Inform. 164, Article 44, 18 p. (2020; Zbl 07760173) Full Text: DOI
Agrawal, Akanksha; Knudsen, Kristine V. K.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav The parameterized complexity of guarding almost convex polygons. (English) Zbl 07760132 Cabello, Sergio (ed.) et al., 36th international symposium on computational geometry, SoCG 2020, Zürich, Switzerland (virtual conference), June 23–26, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 164, Article 3, 16 p. (2020). MSC: 68U05 68Q25 68-06 68W25 PDFBibTeX XMLCite \textit{A. Agrawal} et al., LIPIcs -- Leibniz Int. Proc. Inform. 164, Article 3, 16 p. (2020; Zbl 07760132) Full Text: DOI arXiv
Bhore, Sujoy; Carmi, Paz; Kolay, Sudeshna; Zehavi, Meirav Parameterized study of Steiner tree on unit disk graphs. (English) Zbl 07759281 Albers, Susanne (ed.), 17th Scandinavian symposium and workshops on algorithm theory, SWAT 2020, Tórshavn, Faroe Islands, June 22–24, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 162, Article 13, 18 p. (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{S. Bhore} et al., LIPIcs -- Leibniz Int. Proc. Inform. 162, Article 13, 18 p. (2020; Zbl 07759281) Full Text: DOI
Agrawal, Akanksha; Kolay, Sudeshna; Zehavi, Meirav Parameter analysis for guarding terrains. (English) Zbl 07759272 Albers, Susanne (ed.), 17th Scandinavian symposium and workshops on algorithm theory, SWAT 2020, Tórshavn, Faroe Islands, June 22–24, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 162, Article 4, 18 p. (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{A. Agrawal} et al., LIPIcs -- Leibniz Int. Proc. Inform. 162, Article 4, 18 p. (2020; Zbl 07759272) Full Text: DOI
Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems. (English) Zbl 07678783 ACM Trans. Algorithms 16, No. 4, Article No. 51, 38 p. (2020). MSC: 68-XX PDFBibTeX XMLCite \textit{A. Agrawal} et al., ACM Trans. Algorithms 16, No. 4, Article No. 51, 38 p. (2020; Zbl 07678783) Full Text: DOI
Lochet, William; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav Fault tolerant subgraphs with applications in kernelization. (English) Zbl 07650395 Vidick, Thomas (ed.), 11th innovations in theoretical computer science conference, ITCS 2020, Seattle, Washington, USA, January 12–14, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 151, Article 47, 22 p. (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{W. Lochet} et al., LIPIcs -- Leibniz Int. Proc. Inform. 151, Article 47, 22 p. (2020; Zbl 07650395) Full Text: DOI
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Parameterization above a multiplicative guarantee. (English) Zbl 07650387 Vidick, Thomas (ed.), 11th innovations in theoretical computer science conference, ITCS 2020, Seattle, Washington, USA, January 12–14, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 151, Article 39, 13 p. (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{F. V. Fomin} et al., LIPIcs -- Leibniz Int. Proc. Inform. 151, Article 39, 13 p. (2020; Zbl 07650387) Full Text: DOI
Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav Efficient graph minors theory and parameterized algorithms for (planar) disjoint paths. (English) Zbl 07604208 Fomin, Fedor V. (ed.) et al., Treewidth, kernels, and algorithms. Essays dedicated to Hans L. Bodlaender on the occasion of his 60th birthday. Cham: Springer. Lect. Notes Comput. Sci. 12160, 112-128 (2020). MSC: 68-XX PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., Lect. Notes Comput. Sci. 12160, 112--128 (2020; Zbl 07604208) Full Text: DOI arXiv
Agrawal, Akanksha; Zehavi, Meirav Parameterized analysis of art gallery and terrain guarding. (English) Zbl 07603910 Fernau, Henning, Computer science – theory and applications. 15th international computer science symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12159, 16-29 (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Agrawal} and \textit{M. Zehavi}, Lect. Notes Comput. Sci. 12159, 16--29 (2020; Zbl 07603910) Full Text: DOI
Golovach, Petr A.; Krithika, R.; Sahu, Abhishek; Saurabh, Saket; Zehavi, Meirav Graph Hamiltonicity parameterized by proper interval deletion set. (English) Zbl 07600768 Kohayakawa, Yoshiharu (ed.) et al., Latin 2020: theoretical informatics. 14th Latin American symposium, São Paulo, Brazil, January 5–8, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12118, 104-115 (2020). MSC: 68Qxx 68Rxx 68Wxx PDFBibTeX XMLCite \textit{P. A. Golovach} et al., Lect. Notes Comput. Sci. 12118, 104--115 (2020; Zbl 07600768) Full Text: DOI
Gupta, Sushmita; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav Popular matching in roommates setting is NP-hard. (English) Zbl 1468.68105 Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 130, 107-112 (2020). MSC: 68Q17 05C70 91B68 PDFBibTeX XMLCite \textit{S. Gupta} et al., Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 130, 107--112 (2020; Zbl 1468.68105) Full Text: Link
Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav Covering small independent sets and separators with applications to parameterized algorithms. (English) Zbl 1484.68325 ACM Trans. Algorithms 16, No. 3, Article No. 32, 31 p. (2020). MSC: 68W20 05C69 68R10 68W05 68W40 PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., ACM Trans. Algorithms 16, No. 3, Article No. 32, 31 p. (2020; Zbl 1484.68325) Full Text: DOI arXiv
Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav Approximation schemes via width/weight trade-offs on minor-free graphs. (English) Zbl 07304165 Chawla, Shuchi (ed.), Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2299-2318 (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{F. V. Fomin} et al., in: Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5--8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2299--2318 (2020; Zbl 07304165) Full Text: DOI
Lokshtanov, Daniel; Ramanujan, M. S.; Saurab, Saket; Zehavi, Meirav Parameterized complexity and approximability of directed odd cycle transversal. (English) Zbl 07304158 Chawla, Shuchi (ed.), Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2181-2200 (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., in: Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5--8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2181--2200 (2020; Zbl 07304158) Full Text: DOI arXiv
Fomin, Fedor V.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Hitting topological minors is FPT. (English) Zbl 07298330 Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM). 1317-1326 (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{F. V. Fomin} et al., in: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC '20, Chicago, IL, USA, June 22--26, 2020. New York, NY: Association for Computing Machinery (ACM). 1317--1326 (2020; Zbl 07298330) Full Text: DOI arXiv
Lokshtanov, Daniel; Misra, Pranabendu; Pilipczuk, Michał; Saurabh, Saket; Zehavi, Meirav An exponential time parameterized algorithm for planar disjoint paths. (English) Zbl 07298329 Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM). 1307-1316 (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., in: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC '20, Chicago, IL, USA, June 22--26, 2020. New York, NY: Association for Computing Machinery (ACM). 1307--1316 (2020; Zbl 07298329) Full Text: DOI arXiv
Komusiewicz, Christian; de Oliveira Oliveira, Mateus; Zehavi, Meirav Revisiting the parameterized complexity of maximum-duo preservation string mapping. (English) Zbl 1464.68445 Theor. Comput. Sci. 847, 27-38 (2020). MSC: 68W32 68Q27 68W20 68W40 92D10 PDFBibTeX XMLCite \textit{C. Komusiewicz} et al., Theor. Comput. Sci. 847, 27--38 (2020; Zbl 1464.68445) Full Text: DOI Link
Gupta, Siddharth; Sa’ar, Guy; Zehavi, Meirav The parameterized complexity of motion planning for snake-like robots. (English) Zbl 1490.68121 J. Artif. Intell. Res. (JAIR) 69, 191-229 (2020). MSC: 68Q27 68R10 68T40 PDFBibTeX XMLCite \textit{S. Gupta} et al., J. Artif. Intell. Res. (JAIR) 69, 191--229 (2020; Zbl 1490.68121) Full Text: DOI arXiv
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Going far from degeneracy. (English) Zbl 1451.05229 SIAM J. Discrete Math. 34, No. 3, 1587-1601 (2020). MSC: 05C85 05C12 05C38 68Q17 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., SIAM J. Discrete Math. 34, No. 3, 1587--1601 (2020; Zbl 1451.05229) Full Text: DOI arXiv
Gupta, Sushmita; Roy, Sanjukta; Saurabh, Saket; Zehavi, Meirav Quadratic vertex kernel for rainbow matching. (English) Zbl 1435.68236 Algorithmica 82, No. 4, 881-897 (2020). MSC: 68R10 05C15 05C70 05C85 68Q27 PDFBibTeX XMLCite \textit{S. Gupta} et al., Algorithmica 82, No. 4, 881--897 (2020; Zbl 1435.68236) Full Text: DOI
Madathil, Jayakrishnan; Saurabh, Saket; Zehavi, Meirav Fixed-parameter tractable algorithm and polynomial kernel for Max-Cut Above Spanning Tree. (English) Zbl 1434.68748 Theory Comput. Syst. 64, No. 1, 62-100 (2020). MSC: 68W40 05C85 68Q27 68R10 PDFBibTeX XMLCite \textit{J. Madathil} et al., Theory Comput. Syst. 64, No. 1, 62--100 (2020; Zbl 1434.68748) Full Text: DOI
Madathil, Jayakrishnan; Sharma, Roohani; Zehavi, Meirav A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs. (English) Zbl 1516.68069 Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 28, 14 p. (2019). MSC: 68R10 05C20 05C70 05C85 68Q27 PDFBibTeX XMLCite \textit{J. Madathil} et al., LIPIcs -- Leibniz Int. Proc. Inform. 138, Article 28, 14 p. (2019; Zbl 1516.68069) Full Text: DOI
Bessy, Stéphane; Bougeret, Marin; Krithika, R.; Sahu, Abhishek; Saurabh, Saket; Thiebaut, Jocelyn; Zehavi, Meirav Packing arc-disjoint cycles in tournaments. (English) Zbl 07561671 Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 27, 14 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{S. Bessy} et al., LIPIcs -- Leibniz Int. Proc. Inform. 138, Article 27, 14 p. (2019; Zbl 07561671) Full Text: DOI
Fomin, Fedor V.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Decomposition of map graphs with applications. (English) Zbl 07561553 Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 60, 15 p. (2019). MSC: 68Nxx 68Qxx PDFBibTeX XMLCite \textit{F. V. Fomin} et al., LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 60, 15 p. (2019; Zbl 07561553) Full Text: DOI arXiv
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav Covering vectors by spaces in perturbed graphic matroids and their duals. (English) Zbl 07561552 Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 59, 13 p. (2019). MSC: 68Nxx 68Qxx PDFBibTeX XMLCite \textit{F. V. Fomin} et al., LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 59, 13 p. (2019; Zbl 07561552) Full Text: DOI arXiv
Björklund, Andreas; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav Approximate counting of \(k\)-paths: deterministic and in polynomial space. (English) Zbl 07561517 Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 24, 15 p. (2019). MSC: 68Nxx 68Qxx PDFBibTeX XMLCite \textit{A. Björklund} et al., LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 24, 15 p. (2019; Zbl 07561517) Full Text: DOI
Agrawal, Akanksha; Guśpiel, Grzegorz; Madathil, Jayakrishnan; Saurabh, Saket; Zehavi, Meirav Connecting the dots (with Minimum Crossings). (English) Zbl 07559207 Barequet, Gill (ed.) et al., 35th international symposium on computational geometry, SoCG 2019, Portland, Oregon, USA, June 18–21, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 129, Article 7, 17 p. (2019). MSC: 68U05 PDFBibTeX XMLCite \textit{A. Agrawal} et al., LIPIcs -- Leibniz Int. Proc. Inform. 129, Article 7, 17 p. (2019; Zbl 07559207) Full Text: DOI
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Going far from degeneracy. (English) Zbl 07525484 Bender, Michael A. (ed.) et al., 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 144, Article 47, 14 p. (2019). MSC: 68Wxx PDFBibTeX XMLCite \textit{F. V. Fomin} et al., LIPIcs -- Leibniz Int. Proc. Inform. 144, Article 47, 14 p. (2019; Zbl 07525484) Full Text: DOI
Saurabh, Saket; Zehavi, Meirav Parameterized complexity of multi-node hubs. (English) Zbl 1520.68051 Paul, Christophe (ed.) et al., 13th international symposium on parameterized and exact computation, IPEC 2018, August 22–24, 2018, Helsinki, Finland. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 115, Article 8, 14 p. (2019). MSC: 68Q27 68R10 PDFBibTeX XMLCite \textit{S. Saurabh} and \textit{M. Zehavi}, LIPIcs -- Leibniz Int. Proc. Inform. 115, Article 8, 14 p. (2019; Zbl 1520.68051) Full Text: DOI
Lokshtanov, Daniel; Ramanujan, M. S.; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav Wannabe bounded treewidth graphs admit a polynomial kernel for DFVS. (English) Zbl 07152233 Friggstad, Zachary (ed.) et al., Algorithms and data structures. 16th international symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11646, 523-537 (2019). MSC: 68P05 68Wxx PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., Lect. Notes Comput. Sci. 11646, 523--537 (2019; Zbl 07152233) Full Text: DOI
Gupta, Sushmita; Roy, Sanjukta; Saurabh, Saket; Zehavi, Meirav Balanced stable marriage: how close is close enough? (English) Zbl 1517.68143 Friggstad, Zachary (ed.) et al., Algorithms and data structures. 16th international symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11646, 423-437 (2019). MSC: 68Q27 91B68 PDFBibTeX XMLCite \textit{S. Gupta} et al., Lect. Notes Comput. Sci. 11646, 423--437 (2019; Zbl 1517.68143) Full Text: DOI arXiv
Agrawal, Akanksha; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav Split contraction: the untold story. (English) Zbl 1496.68260 ACM Trans. Comput. Theory 11, No. 3, Article No. 18, 22 p. (2019). MSC: 68R10 05C83 68Q17 68Q27 PDFBibTeX XMLCite \textit{A. Agrawal} et al., ACM Trans. Comput. Theory 11, No. 3, Article No. 18, 22 p. (2019; Zbl 1496.68260) Full Text: DOI
Fomin, Fedor V.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Finding, hitting and packing cycles in subexponential time on unit disk graphs. (English) Zbl 1441.68178 Discrete Comput. Geom. 62, No. 4, 879-911 (2019). MSC: 68R10 05C62 68Q27 68U05 68W40 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., Discrete Comput. Geom. 62, No. 4, 879--911 (2019; Zbl 1441.68178) Full Text: DOI Link
Lokshtanov, Daniel; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav Balanced judicious bipartition is fixed-parameter tractable. (English) Zbl 1425.05129 SIAM J. Discrete Math. 33, No. 4, 1878-1911 (2019). MSC: 05C70 05C35 68Q25 PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., SIAM J. Discrete Math. 33, No. 4, 1878--1911 (2019; Zbl 1425.05129) Full Text: DOI arXiv
Bang-Jensen, J.; Knudsen, Kristine V. K.; Saurabh, Saket; Zehavi, Meirav The parameterized complexity landscape of finding 2-partitions of digraphs. (English) Zbl 1434.68205 Theor. Comput. Sci. 795, 108-114 (2019). MSC: 68Q27 68R10 PDFBibTeX XMLCite \textit{J. Bang-Jensen} et al., Theor. Comput. Sci. 795, 108--114 (2019; Zbl 1434.68205) Full Text: DOI
Gupta, Sushmita; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav Popular matching in roommates setting is NP-hard. (English) Zbl 1432.68163 Chan, Timothy M. (ed.), Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6–9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2810-2822 (2019). MSC: 68Q17 05C70 91B68 PDFBibTeX XMLCite \textit{S. Gupta} et al., in: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6--9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2810--2822 (2019; Zbl 1432.68163) Full Text: DOI arXiv
Gutin, Gregory; Wahlström, Magnus; Zehavi, Meirav On \(r\)-simple \(k\)-path and related problems parameterized by \(k/r\). (English) Zbl 1432.68194 Chan, Timothy M. (ed.), Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6–9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1750-1769 (2019). MSC: 68Q27 05C38 05C70 05C85 68Q17 68R10 PDFBibTeX XMLCite \textit{G. Gutin} et al., in: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6--9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1750--1769 (2019; Zbl 1432.68194) Full Text: DOI
Agrawal, Akanksha; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav Interval vertex deletion admits a polynomial kernel. (English) Zbl 1432.68185 Chan, Timothy M. (ed.), Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6–9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1711-1730 (2019). MSC: 68Q27 05C62 05C85 PDFBibTeX XMLCite \textit{A. Agrawal} et al., in: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6--9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1711--1730 (2019; Zbl 1432.68185) Full Text: DOI
Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity. (English) Zbl 1431.68100 Chan, Timothy M. (ed.), Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6–9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1035-1054 (2019). MSC: 68R10 05C62 05C85 68Q27 68W25 68W40 PDFBibTeX XMLCite \textit{F. Panolan} et al., in: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6--9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1035--1054 (2019; Zbl 1431.68100) Full Text: DOI
Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Parameterized computational geometry via decomposition theorems. (English) Zbl 1434.68615 Das, Gautam K. (ed.) et al., WALCOM: algorithms and computation. 13th international conference, WALCOM 2019, Guwahati, India, February 27 – March 2, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11355, 15-27 (2019). MSC: 68U05 05C62 68R10 68Q27 PDFBibTeX XMLCite \textit{F. Panolan} et al., Lect. Notes Comput. Sci. 11355, 15--27 (2019; Zbl 1434.68615) Full Text: DOI
Meesum, Syed M.; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Rank vertex cover as a natural problem for algebraic compression. (English) Zbl 1419.05203 SIAM J. Discrete Math. 33, No. 3, 1277-1296 (2019). MSC: 05C85 68R10 PDFBibTeX XMLCite \textit{S. M. Meesum} et al., SIAM J. Discrete Math. 33, No. 3, 1277--1296 (2019; Zbl 1419.05203) Full Text: DOI arXiv
Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket; Zehavi, Meirav Packing cycles faster than Erdős-Pósa. (English) Zbl 1419.05202 SIAM J. Discrete Math. 33, No. 3, 1194-1215 (2019). MSC: 05C85 05C38 05C30 68Q25 68W05 68W25 68W40 PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., SIAM J. Discrete Math. 33, No. 3, 1194--1215 (2019; Zbl 1419.05202) Full Text: DOI arXiv
Krithika, R.; Sahu, Abhishek; Saurabh, Saket; Zehavi, Meirav The parameterized complexity of cycle packing: indifference is not an issue. (English) Zbl 1429.68195 Algorithmica 81, No. 9, 3803-3841 (2019). MSC: 68R10 05C38 05C70 05C85 68Q27 PDFBibTeX XMLCite \textit{R. Krithika} et al., Algorithmica 81, No. 9, 3803--3841 (2019; Zbl 1429.68195) Full Text: DOI
Pinter, Ron Y.; Shachnai, Hadas; Zehavi, Meirav Improved parameterized algorithms for network query problems. (English) Zbl 1421.68141 Algorithmica 81, No. 6, 2270-2316 (2019). MSC: 68R10 05C85 68W25 68W40 PDFBibTeX XMLCite \textit{R. Y. Pinter} et al., Algorithmica 81, No. 6, 2270--2316 (2019; Zbl 1421.68141) Full Text: DOI
Gupta, Sushmita; Roy, Sanjukta; Saurabh, Saket; Zehavi, Meirav Parameterized algorithms and kernels for rainbow matching. (English) Zbl 1422.68188 Algorithmica 81, No. 4, 1684-1698 (2019). MSC: 68R10 05C70 05C85 68Q25 PDFBibTeX XMLCite \textit{S. Gupta} et al., Algorithmica 81, No. 4, 1684--1698 (2019; Zbl 1422.68188) Full Text: DOI Link
Fomin, Fedor V.; Le, Tien-Nam; Lokshtanov, Daniel; Saurabh, Saket; Thomassé, Stéphan; Zehavi, Meirav Subquadratic kernels for implicit 3-{Hitting Set} and 3-{Set Packing} problems. (English) Zbl 1454.68101 ACM Trans. Algorithms 15, No. 1, Article No. 13, 44 p. (2019). MSC: 68R10 68Q27 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., ACM Trans. Algorithms 15, No. 1, Article No. 13, 44 p. (2019; Zbl 1454.68101) Full Text: DOI
Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav Feedback vertex set inspired kernel for chordal vertex deletion. (English) Zbl 1454.68088 ACM Trans. Algorithms 15, No. 1, Article No. 11, 28 p. (2019). MSC: 68R10 05C38 05C85 68Q27 PDFBibTeX XMLCite \textit{A. Agrawal} et al., ACM Trans. Algorithms 15, No. 1, Article No. 11, 28 p. (2019; Zbl 1454.68088) Full Text: DOI arXiv
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav Clique-width. III: Hamiltonian cycle and the odd case of graph coloring. (English) Zbl 1458.05245 ACM Trans. Algorithms 15, No. 1, Article No. 9, 27 p. (2019). MSC: 05C85 05C15 05C45 05C69 68Q17 68Q27 68R10 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., ACM Trans. Algorithms 15, No. 1, Article No. 9, 27 p. (2019; Zbl 1458.05245) Full Text: DOI
Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Parameterized algorithms for list \(K\)-cycle. (English) Zbl 1418.68106 Algorithmica 81, No. 3, 1267-1287 (2019). MSC: 68Q25 05C15 05C38 05C85 68W20 PDFBibTeX XMLCite \textit{F. Panolan} et al., Algorithmica 81, No. 3, 1267--1287 (2019; Zbl 1418.68106) Full Text: DOI
Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav Kernelization. Theory of parameterized preprocessing. (English) Zbl 1426.68003 Cambridge: Cambridge University Press (ISBN 978-1-107-05776-0/hbk; 978-1-107-41515-7/ebook). xiv, 515 p. (2019). Reviewer: Efstratios Rappos (Aubonne) MSC: 68-02 68P01 68Q17 68Q25 68R10 68W01 90C27 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., Kernelization. Theory of parameterized preprocessing. Cambridge: Cambridge University Press (2019; Zbl 1426.68003) Full Text: DOI
Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number. (English) Zbl 1528.68311 Ganguly, Sumit (ed.) et al., 38th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2018, Ahmedabad, India, December 11–13, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 122, Article 35, 19 p. (2018). MSC: 68R10 05C20 68Q27 PDFBibTeX XMLCite \textit{P. Misra} et al., LIPIcs -- Leibniz Int. Proc. Inform. 122, Article 35, 19 p. (2018; Zbl 1528.68311) Full Text: DOI
Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems. (English) Zbl 1499.68395 Blais, Eric (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 21st international workshop, APPROX 2018, and 22nd international workshop, RANDOM 2018 August 20–22, 2018, Princeton, USA. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 116, Article 1, 15 p. (2018). MSC: 68W25 05C22 05C85 68R10 68W20 PDFBibTeX XMLCite \textit{A. Agrawal} et al., LIPIcs -- Leibniz Int. Proc. Inform. 116, Article 1, 15 p. (2018; Zbl 1499.68395) Full Text: DOI arXiv
Lokshtanov, Daniel; Ramanujan, M. S.; Saurabh, Saket; Zehavi, Meirav Reducing CMSO model checking to highly connected graphs. (English) Zbl 1499.68203 Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 135, 14 p. (2018). MSC: 68Q60 03B70 68Q27 68R10 PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., LIPIcs -- Leibniz Int. Proc. Inform. 107, Article 135, 14 p. (2018; Zbl 1499.68203) Full Text: DOI arXiv
Lokshtanov, Daniel; Ramanujan, M. S.; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav Brief announcement: Treewidth modulator: emergency exit for DFVS. (English) Zbl 1499.68284 Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 110, 4 p. (2018). MSC: 68R10 68Q27 PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., LIPIcs -- Leibniz Int. Proc. Inform. 107, Article 110, 4 p. (2018; Zbl 1499.68284) Full Text: DOI
Lokshtanov, Daniel; Misra, Pranabendu; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Quasipolynomial representation of transversal matroids with applications in parameterized complexity. (English) Zbl 1462.68081 Karlin, Anna R. (ed.), 9th innovations in theoretical computer science conference, ITCS 2018, Cambridge, MA, USA, January 11–14, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 94, Article 32, 13 p. (2018). MSC: 68Q25 05B35 68Q27 PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., LIPIcs -- Leibniz Int. Proc. Inform. 94, Article 32, 13 p. (2018; Zbl 1462.68081) Full Text: DOI
Lokshtanov, Daniel; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav Balanced judicious bipartition is fixed-parameter tractable. (English) Zbl 1491.05148 Lokam, Satya (ed.) et al., 37th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2017, IIT Kanpur, India, December 12–14, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 93, Article 40, 15 p. (2018). MSC: 05C70 05C35 68Q27 PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., LIPIcs -- Leibniz Int. Proc. Inform. 93, Article 40, 15 p. (2018; Zbl 1491.05148) Full Text: DOI
Krithika, R.; Sahu, Abhishek; Saurabh, Saket; Zehavi, Meirav The parameterized complexity of cycle packing: indifference is not an issue. (English) Zbl 1504.68175 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, 712-726 (2018). MSC: 68R10 05C85 68Q27 68W05 68W40 PDFBibTeX XMLCite \textit{R. Krithika} et al., Lect. Notes Comput. Sci. 10807, 712--726 (2018; Zbl 1504.68175) Full Text: DOI
Agrawal, Akanksha; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav Parameterised algorithms for deletion to classes of DAGs. (English) Zbl 1430.68170 Theory Comput. Syst. 62, No. 8, 1880-1909 (2018). MSC: 68R10 05C85 68Q27 PDFBibTeX XMLCite \textit{A. Agrawal} et al., Theory Comput. Syst. 62, No. 8, 1880--1909 (2018; Zbl 1430.68170) Full Text: DOI
Madathil, Jayakrishnan; Saurabh, Saket; Zehavi, Meirav Max-Cut Above Spanning Tree is fixed-parameter tractable. (English) Zbl 1434.68747 Fomin, Fedor V. (ed.) et al., Computer science – theory and applications. 13th international computer science symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10846, 244-256 (2018). MSC: 68W40 05C85 68Q27 68R10 PDFBibTeX XMLCite \textit{J. Madathil} et al., Lect. Notes Comput. Sci. 10846, 244--256 (2018; Zbl 1434.68747) Full Text: DOI
Ashok, Pradeesha; Fomin, Fedor V.; Kolay, Sudeshna; Saurabh, Saket; Zehavi, Meirav Exact algorithms for terrain guarding. (English) Zbl 1454.68153 ACM Trans. Algorithms 14, No. 2, Article No. 25, 20 p. (2018). MSC: 68U05 68Q27 68W25 68W40 PDFBibTeX XMLCite \textit{P. Ashok} et al., ACM Trans. Algorithms 14, No. 2, Article No. 25, 20 p. (2018; Zbl 1454.68153) Full Text: DOI Link
Fomin, Fedor V.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Long directed \((s,t)\)-path: FPT algorithm. (English) Zbl 1478.68233 Inf. Process. Lett. 140, 8-12 (2018). MSC: 68R10 05C38 05C85 68Q27 68W40 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., Inf. Process. Lett. 140, 8--12 (2018; Zbl 1478.68233) Full Text: DOI
Gutin, Gregory; Reidl, Felix; Wahlström, Magnus; Zehavi, Meirav Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials. (English) Zbl 1391.68055 J. Comput. Syst. Sci. 95, 69-85 (2018). MSC: 68Q25 05C15 05C31 05C50 05C69 05C85 PDFBibTeX XMLCite \textit{G. Gutin} et al., J. Comput. Syst. Sci. 95, 69--85 (2018; Zbl 1391.68055) Full Text: DOI arXiv Link
Fomin, Fedor V.; Lokshtanov, Daniel; Meesum, S. M.; Saurabh, Saket; Zehavi, Meirav Matrix rigidity from the viewpoint of parameterized complexity. (English) Zbl 1394.68177 SIAM J. Discrete Math. 32, No. 2, 966-985 (2018). Reviewer: Gema Maria Diaz Toca (Murcia) MSC: 68Q25 05C50 15A03 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., SIAM J. Discrete Math. 32, No. 2, 966--985 (2018; Zbl 1394.68177) Full Text: DOI
Adil, Deeksha; Gupta, Sushmita; Roy, Sanjukta; Saurabh, Saket; Zehavi, Meirav Parameterized algorithms for stable matching with ties and incomplete lists. (English) Zbl 1392.68196 Theor. Comput. Sci. 723, 1-10 (2018). MSC: 68Q25 91B68 PDFBibTeX XMLCite \textit{D. Adil} et al., Theor. Comput. Sci. 723, 1--10 (2018; Zbl 1392.68196) Full Text: DOI
Bang-Jensen, Jørgen; Basavaraju, Manu; Vitting Klinkby, Kristine; Misra, Pranabendu; Ramanujan, M. S.; Saurabh, Saket; Zehavi, Meirav Parameterized algorithms for survivable network design with uniform demands. (English) Zbl 1403.90559 Czumaj, Artur (ed.), Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). 2838-2850 (2018). MSC: 90C27 68W40 90C35 PDFBibTeX XMLCite \textit{J. Bang-Jensen} et al., in: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7--10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2838--2850 (2018; Zbl 1403.90559) Full Text: Link
Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav Covering small independent sets and separators with applications to parameterized algorithms. (English) Zbl 1403.68337 Czumaj, Artur (ed.), Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). 2785-2800 (2018). MSC: 68W20 05C69 68R10 68W40 PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., in: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7--10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2785--2800 (2018; Zbl 1403.68337) Full Text: arXiv Link
Le, Tien-Nam; Lokshtanov, Daniel; Saurabh, Saket; Thomassé, Stéphan; Zehavi, Meirav Subquadratic kernels for implicit 3-hitting set and 3-set packing problems. (English) Zbl 1403.68167 Czumaj, Artur (ed.), Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). 331-342 (2018). MSC: 68R10 68Q25 PDFBibTeX XMLCite \textit{T.-N. Le} et al., in: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7--10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 331--342 (2018; Zbl 1403.68167) Full Text: Link
Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth. (English) Zbl 1403.68164 Czumaj, Artur (ed.), Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). 262-273 (2018). MSC: 68R10 05C15 68Q17 68Q25 PDFBibTeX XMLCite \textit{P. A. Golovach} et al., in: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7--10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 262--273 (2018; Zbl 1403.68164) Full Text: Link
Agrawal, Akanksha; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav Kernels for deletion to classes of acyclic digraphs. (English) Zbl 1380.68207 J. Comput. Syst. Sci. 92, 9-21 (2018). MSC: 68Q25 05C20 68R10 PDFBibTeX XMLCite \textit{A. Agrawal} et al., J. Comput. Syst. Sci. 92, 9--21 (2018; Zbl 1380.68207) Full Text: DOI Link
Zehavi, Meirav The \(k\)-leaf spanning tree problem admits a klam value of 39. (English) Zbl 1373.05040 Eur. J. Comb. 68, 175-203 (2018). MSC: 05C05 05C85 68Q25 PDFBibTeX XMLCite \textit{M. Zehavi}, Eur. J. Comb. 68, 175--203 (2018; Zbl 1373.05040) Full Text: DOI arXiv
Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket; Zehavi, Meirav Packing cycles faster than Erdős-Pósa. (English) Zbl 1441.05210 Chatzigiannakis, Ioannis (ed.) et al., 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 80, Article 71, 15 p. (2017). MSC: 05C85 05C30 05C38 05C70 68Q27 68W05 68W25 68W40 PDFBibTeX XMLCite \textit{D. Lokshtanov} et al., LIPIcs -- Leibniz Int. Proc. Inform. 80, Article 71, 15 p. (2017; Zbl 1441.05210) Full Text: DOI
Fomin, Fedor V.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav Finding, hitting and packing cycles in subexponential time on unit disk graphs. (English) Zbl 1441.68179 Chatzigiannakis, Ioannis (ed.) et al., 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 80, Article 65, 15 p. (2017). MSC: 68R10 05C62 68Q27 68U05 68W40 PDFBibTeX XMLCite \textit{F. V. Fomin} et al., LIPIcs -- Leibniz Int. Proc. Inform. 80, Article 65, 15 p. (2017; Zbl 1441.68179) Full Text: DOI arXiv
Gupta, Sushmita; Roy, Sanjukta; Saurabh, Saket; Zehavi, Meirav Parameterized algorithms and kernels for rainbow matching. (English) Zbl 1435.68237 Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 71, 13 p. (2017). MSC: 68R10 05C15 05C70 05C85 68Q27 PDFBibTeX XMLCite \textit{S. Gupta} et al., LIPIcs -- Leibniz Int. Proc. Inform. 83, Article 71, 13 p. (2017; Zbl 1435.68237) Full Text: DOI