Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Jungho Ahn, Jinha Kim, and O-joung Kwon. Unified Almost Linear Kernels for Generalized Covering and Packing Problems on Nowhere Dense Classes. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{ahn_et_al:LIPIcs.ISAAC.2023.5, author = {Ahn, Jungho and Kim, Jinha and Kwon, O-joung}, title = {{Unified Almost Linear Kernels for Generalized Covering and Packing Problems on Nowhere Dense Classes}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {5:1--5:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.5}, URN = {urn:nbn:de:0030-drops-193072}, doi = {10.4230/LIPIcs.ISAAC.2023.5}, annote = {Keywords: kernelization, independent set, dominating set, covering, packing} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Hugo A. Akitaya, Andrei Gonczi, Diane L. Souvaine, Csaba D. Tóth, and Thomas Weighill. Reconfiguration of Polygonal Subdivisions via Recombination. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{a.akitaya_et_al:LIPIcs.ESA.2023.6, author = {A. Akitaya, Hugo and Gonczi, Andrei and Souvaine, Diane L. and T\'{o}th, Csaba D. and Weighill, Thomas}, title = {{Reconfiguration of Polygonal Subdivisions via Recombination}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {6:1--6:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.6}, URN = {urn:nbn:de:0030-drops-186598}, doi = {10.4230/LIPIcs.ESA.2023.6}, annote = {Keywords: configuration space, gerrymandering, polygonal subdivision, recombination} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Haitao Wang and Yiming Zhao. Improved Algorithms for Distance Selection and Related Problems. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 101:1-101:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{wang_et_al:LIPIcs.ESA.2023.101, author = {Wang, Haitao and Zhao, Yiming}, title = {{Improved Algorithms for Distance Selection and Related Problems}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {101:1--101:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.101}, URN = {urn:nbn:de:0030-drops-187544}, doi = {10.4230/LIPIcs.ESA.2023.101}, annote = {Keywords: Geometric optimization, distance selection, Fr\'{e}chet distance, range searching} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
David E. Roberson and Tim Seppelt. Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 101:1-101:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{roberson_et_al:LIPIcs.ICALP.2023.101, author = {Roberson, David E. and Seppelt, Tim}, title = {{Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {101:1--101:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.101}, URN = {urn:nbn:de:0030-drops-181531}, doi = {10.4230/LIPIcs.ICALP.2023.101}, annote = {Keywords: Lasserre hierarchy, homomorphism indistinguishability, Sherali-Adams hierarchy, treewidth, semidefinite programming, linear programming, graph isomorphism} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, and Csaba D. Tóth. Online Spanners in Metric Spaces. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bhore_et_al:LIPIcs.ESA.2022.18, author = {Bhore, Sujoy and Filtser, Arnold and Khodabandeh, Hadi and T\'{o}th, Csaba D.}, title = {{Online Spanners in Metric Spaces}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {18:1--18:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.18}, URN = {urn:nbn:de:0030-drops-169564}, doi = {10.4230/LIPIcs.ESA.2022.18}, annote = {Keywords: spanner, online algorithm, lightness, sparsity, minimum weight} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Jonathan B. Conroy and Csaba D. Tóth. Hop-Spanners for Geometric Intersection Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{conroy_et_al:LIPIcs.SoCG.2022.30, author = {Conroy, Jonathan B. and T\'{o}th, Csaba D.}, title = {{Hop-Spanners for Geometric Intersection Graphs}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {30:1--30:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.30}, URN = {urn:nbn:de:0030-drops-160381}, doi = {10.4230/LIPIcs.SoCG.2022.30}, annote = {Keywords: geometric intersection graph, unit disk graph, hop-spanner} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
János Pach, Gábor Tardos, and Géza Tóth. Disjointness Graphs of Short Polygonal Chains. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 56:1-56:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{pach_et_al:LIPIcs.SoCG.2022.56, author = {Pach, J\'{a}nos and Tardos, G\'{a}bor and T\'{o}th, G\'{e}za}, title = {{Disjointness Graphs of Short Polygonal Chains}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {56:1--56:12}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.56}, URN = {urn:nbn:de:0030-drops-160645}, doi = {10.4230/LIPIcs.SoCG.2022.56}, annote = {Keywords: chi-bounded, disjointness graph} }
Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Duncan Adamson, Vladimir V. Gusev, Dmitriy Malyshev, and Viktor Zamaraev. Faster Exploration of Some Temporal Graphs. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{adamson_et_al:LIPIcs.SAND.2022.5, author = {Adamson, Duncan and Gusev, Vladimir V. and Malyshev, Dmitriy and Zamaraev, Viktor}, title = {{Faster Exploration of Some Temporal Graphs}}, booktitle = {1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)}, pages = {5:1--5:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-224-2}, ISSN = {1868-8969}, year = {2022}, volume = {221}, editor = {Aspnes, James and Michail, Othon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.5}, URN = {urn:nbn:de:0030-drops-159475}, doi = {10.4230/LIPIcs.SAND.2022.5}, annote = {Keywords: Temporal Graphs, Graph Exploration} }
Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Local Certification of Graph Decompositions and Applications to Minor-Free Classes. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bousquet_et_al:LIPIcs.OPODIS.2021.22, author = {Bousquet, Nicolas and Feuilloley, Laurent and Pierron, Th\'{e}o}, title = {{Local Certification of Graph Decompositions and Applications to Minor-Free Classes}}, booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)}, pages = {22:1--22:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-219-8}, ISSN = {1868-8969}, year = {2022}, volume = {217}, editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.22}, URN = {urn:nbn:de:0030-drops-157970}, doi = {10.4230/LIPIcs.OPODIS.2021.22}, annote = {Keywords: Local certification, proof-labeling schemes, locally checkable proofs, graph decompositions, minor-free graphs} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Gabriel Bathie, Nicolas Bousquet, and Théo Pierron. (Sub)linear Kernels for Edge Modification Problems Towards Structured Graph Classes. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bathie_et_al:LIPIcs.IPEC.2021.8, author = {Bathie, Gabriel and Bousquet, Nicolas and Pierron, Th\'{e}o}, title = {{(Sub)linear Kernels for Edge Modification Problems Towards Structured Graph Classes}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {8:1--8:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.8}, URN = {urn:nbn:de:0030-drops-153918}, doi = {10.4230/LIPIcs.IPEC.2021.8}, annote = {Keywords: kernelization, graph editing, split graphs, (sub)linear kernels} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, and Ulysse Prieto. PACE Solver Description: PaSTEC - PAths, Stars and Twins to Edit Towards Clusters. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 29:1-29:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bartier_et_al:LIPIcs.IPEC.2021.29, author = {Bartier, Valentin and Bathie, Gabriel and Bousquet, Nicolas and Heinrich, Marc and Pierron, Th\'{e}o and Prieto, Ulysse}, title = {{PACE Solver Description: PaSTEC - PAths, Stars and Twins to Edit Towards Clusters}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {29:1--29:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.29}, URN = {urn:nbn:de:0030-drops-154129}, doi = {10.4230/LIPIcs.IPEC.2021.29}, annote = {Keywords: cluster editing, exact algorithm, star packing, twins} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, and Ulysse Prieto. PACE Solver Description: μSolver - Heuristic Track. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 33:1-33:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bartier_et_al:LIPIcs.IPEC.2021.33, author = {Bartier, Valentin and Bathie, Gabriel and Bousquet, Nicolas and Heinrich, Marc and Pierron, Th\'{e}o and Prieto, Ulysse}, title = {{PACE Solver Description: \muSolver - Heuristic Track}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {33:1--33:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.33}, URN = {urn:nbn:de:0030-drops-154161}, doi = {10.4230/LIPIcs.IPEC.2021.33}, annote = {Keywords: kernelization, graph editing, clustering, local search} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Brief Announcement: Local Certification of Graph Decompositions and Applications to Minor-Free Classes. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 49:1-49:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bousquet_et_al:LIPIcs.DISC.2021.49, author = {Bousquet, Nicolas and Feuilloley, Laurent and Pierron, Th\'{e}o}, title = {{Brief Announcement: Local Certification of Graph Decompositions and Applications to Minor-Free Classes}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {49:1--49:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.49}, URN = {urn:nbn:de:0030-drops-148515}, doi = {10.4230/LIPIcs.DISC.2021.49}, annote = {Keywords: Local certification, proof-labeling schemes, locally checkable proofs, graph decompositions, minor-free graphs} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Amartya Shankha Biswas, Talya Eden, and Ronitt Rubinfeld. Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 55:1-55:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{biswas_et_al:LIPIcs.APPROX/RANDOM.2021.55, author = {Biswas, Amartya Shankha and Eden, Talya and Rubinfeld, Ronitt}, title = {{Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {55:1--55:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.55}, URN = {urn:nbn:de:0030-drops-147480}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.55}, annote = {Keywords: Sublinear time algorithms, Graph algorithms, Sampling subgraphs, Approximate counting} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Sujoy Bhore and Csaba D. Tóth. Online Euclidean Spanners. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bhore_et_al:LIPIcs.ESA.2021.16, author = {Bhore, Sujoy and T\'{o}th, Csaba D.}, title = {{Online Euclidean Spanners}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {16:1--16:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.16}, URN = {urn:nbn:de:0030-drops-145974}, doi = {10.4230/LIPIcs.ESA.2021.16}, annote = {Keywords: Geometric spanner, (1+\epsilon)-spanner, minimum weight, online algorithm} }
Feedback for Dagstuhl Publishing