Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue. Minimum-Membership Geometric Set Cover, Revisited. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 11:1-11:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.11, author = {Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket and Xue, Jie}, title = {{Minimum-Membership Geometric Set Cover, Revisited}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {11:1--11:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.11}, URN = {urn:nbn:de:0030-drops-178610}, doi = {10.4230/LIPIcs.SoCG.2023.11}, annote = {Keywords: geometric set cover, geometric optimization, approximation algorithms} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Sayan Bandyapadhyay, William Lochet, and Saket Saurabh. FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 12:1-12:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.12, author = {Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket}, title = {{FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {12:1--12:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.12}, URN = {urn:nbn:de:0030-drops-178628}, doi = {10.4230/LIPIcs.SoCG.2023.12}, annote = {Keywords: Clustering, FPT-approximation} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, and Jie Xue. True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 11:1-11:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2022.11, author = {Bandyapadhyay, Sayan and Lochet, William and Lokshtanov, Daniel and Saurabh, Saket and Xue, Jie}, title = {{True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {11:1--11:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.11}, URN = {urn:nbn:de:0030-drops-160190}, doi = {10.4230/LIPIcs.SoCG.2022.11}, annote = {Keywords: unit-disk graphs, tree decomposition, contraction decomposition, bipartization} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh. Detours in Directed Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 29:1-29:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{fomin_et_al:LIPIcs.STACS.2022.29, author = {Fomin, Fedor V. and Golovach, Petr A. and Lochet, William and Sagunov, Danil and Simonov, Kirill and Saurabh, Saket}, title = {{Detours in Directed Graphs}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {29:1--29:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.29}, URN = {urn:nbn:de:0030-drops-158390}, doi = {10.4230/LIPIcs.STACS.2022.29}, annote = {Keywords: longest path, longest detour, diameter, directed graphs, parameterized complexity} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
William Lochet, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Exploiting Dense Structures in Parameterized Complexity. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 50:1-50:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{lochet_et_al:LIPIcs.STACS.2021.50, author = {Lochet, William and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav}, title = {{Exploiting Dense Structures in Parameterized Complexity}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {50:1--50:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.50}, URN = {urn:nbn:de:0030-drops-136950}, doi = {10.4230/LIPIcs.STACS.2021.50}, annote = {Keywords: Dense graphs, disjoint paths, odd cycle transversal, kernels} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Eduard Eiben, William Lochet, and Saket Saurabh. A Polynomial Kernel for Paw-Free Editing. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 10:1-10:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{eiben_et_al:LIPIcs.IPEC.2020.10, author = {Eiben, Eduard and Lochet, William and Saurabh, Saket}, title = {{A Polynomial Kernel for Paw-Free Editing}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.10}, URN = {urn:nbn:de:0030-drops-133136}, doi = {10.4230/LIPIcs.IPEC.2020.10}, annote = {Keywords: Kernelization, Paw-free graph, H-free editing, graph modification problem} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Fedor V. Fomin, Petr A. Golovach, William Lochet, Pranabendu Misra, Saket Saurabh, and Roohani Sharma. Parameterized Complexity of Directed Spanner Problems. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 12:1-12:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.IPEC.2020.12, author = {Fomin, Fedor V. and Golovach, Petr A. and Lochet, William and Misra, Pranabendu and Saurabh, Saket and Sharma, Roohani}, title = {{Parameterized Complexity of Directed Spanner Problems}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {12:1--12:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.12}, URN = {urn:nbn:de:0030-drops-133156}, doi = {10.4230/LIPIcs.IPEC.2020.12}, annote = {Keywords: Graph spanners, directed graphs, parameterized complexity, kernelization} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Eduard Eiben and William Lochet. A Polynomial Kernel for Line Graph Deletion. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 42:1-42:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{eiben_et_al:LIPIcs.ESA.2020.42, author = {Eiben, Eduard and Lochet, William}, title = {{A Polynomial Kernel for Line Graph Deletion}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {42:1--42:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.42}, URN = {urn:nbn:de:0030-drops-129088}, doi = {10.4230/LIPIcs.ESA.2020.42}, annote = {Keywords: Kernelization, line graphs, H-free editing, graph modification problem} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
William Lochet, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Fault Tolerant Subgraphs with Applications in Kernelization. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 47:1-47:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{lochet_et_al:LIPIcs.ITCS.2020.47, author = {Lochet, William and Lokshtanov, Daniel and Misra, Pranabendu and Saurabh, Saket and Sharma, Roohani and Zehavi, Meirav}, title = {{Fault Tolerant Subgraphs with Applications in Kernelization}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {47:1--47:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.47}, URN = {urn:nbn:de:0030-drops-117326}, doi = {10.4230/LIPIcs.ITCS.2020.47}, annote = {Keywords: sparsification, kernelization, fault tolerant subgraphs, directed feedback arc set, directed edge odd cycle transversal, bounded independence number digraphs} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Pallavi Jain, Lawqueen Kanesh, William Lochet, Saket Saurabh, and Roohani Sharma. Exact and Approximate Digraph Bandwidth. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 18:1-18:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{jain_et_al:LIPIcs.FSTTCS.2019.18, author = {Jain, Pallavi and Kanesh, Lawqueen and Lochet, William and Saurabh, Saket and Sharma, Roohani}, title = {{Exact and Approximate Digraph Bandwidth}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {18:1--18:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.18}, URN = {urn:nbn:de:0030-drops-115802}, doi = {10.4230/LIPIcs.FSTTCS.2019.18}, annote = {Keywords: directed bandwidth, digraph bandwidth, approximation scheme, exact exponential algorithms} }
Feedback for Dagstuhl Publishing