Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Liron Cohen, Bruno da Rocha Paiva, Vincent Rahli, and Ayberk Tosun. Inductive Continuity via Brouwer Trees. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cohen_et_al:LIPIcs.MFCS.2023.37, author = {Cohen, Liron and da Rocha Paiva, Bruno and Rahli, Vincent and Tosun, Ayberk}, title = {{Inductive Continuity via Brouwer Trees}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {37:1--37:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.37}, URN = {urn:nbn:de:0030-drops-185718}, doi = {10.4230/LIPIcs.MFCS.2023.37}, annote = {Keywords: Continuity, Dialogue trees, Stateful computations, Intuitionistic Logic, Extensional Type Theory, Constructive Type Theory, Realizability, Theorem proving, Agda} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Eduard Eiben, Diptapriyo Majumdar, and M. S. Ramanujan. Finding a Highly Connected Steiner Subgraph and its Applications. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{eiben_et_al:LIPIcs.MFCS.2023.45, author = {Eiben, Eduard and Majumdar, Diptapriyo and Ramanujan, M. S.}, title = {{Finding a Highly Connected Steiner Subgraph and its Applications}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {45:1--45:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.45}, URN = {urn:nbn:de:0030-drops-185793}, doi = {10.4230/LIPIcs.MFCS.2023.45}, annote = {Keywords: Parameterized Complexity, Steiner Subgraph Extension, p-edge-connected graphs, Matroids, Representative Families} }
Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)
Johanne Cohen, Laurence Pilard, Mikaël Rabie, and Jonas Sénizergues. Making Self-Stabilizing Algorithms for Any Locally Greedy Problem. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cohen_et_al:LIPIcs.SAND.2023.11, author = {Cohen, Johanne and Pilard, Laurence and Rabie, Mika\"{e}l and S\'{e}nizergues, Jonas}, title = {{Making Self-Stabilizing Algorithms for Any Locally Greedy Problem}}, booktitle = {2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)}, pages = {11:1--11:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-275-4}, ISSN = {1868-8969}, year = {2023}, volume = {257}, editor = {Doty, David and Spirakis, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.11}, URN = {urn:nbn:de:0030-drops-179475}, doi = {10.4230/LIPIcs.SAND.2023.11}, annote = {Keywords: Greedy Problem, Ruling Set, Distance-K Coloring, Self-Stabilizing Algorithm} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
David Auger, Pierre Coucheney, and Loric Duhazé. Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{auger_et_al:LIPIcs.MFCS.2022.12, author = {Auger, David and Coucheney, Pierre and Duhaz\'{e}, Loric}, title = {{Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {12:1--12:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.12}, URN = {urn:nbn:de:0030-drops-168103}, doi = {10.4230/LIPIcs.MFCS.2022.12}, annote = {Keywords: Rotor-routing, Rotor Walk, Reachability Problem, Game Theory, Tree-like Multigraph} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, and Pasin Manurangsi. Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{abboud_et_al:LIPIcs.ICALP.2022.7, author = {Abboud, Amir and Cohen-Addad, Vincent and Lee, Euiwoong and Manurangsi, Pasin}, title = {{Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.7}, URN = {urn:nbn:de:0030-drops-163481}, doi = {10.4230/LIPIcs.ICALP.2022.7}, annote = {Keywords: Approximation Algorithms, Complexity, Data Mining, Diversification} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João Ribeiro. Low-Degree Polynomials Extract From Local Sources. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{alrabiah_et_al:LIPIcs.ICALP.2022.10, author = {Alrabiah, Omar and Chattopadhyay, Eshan and Goodman, Jesse and Li, Xin and Ribeiro, Jo\~{a}o}, title = {{Low-Degree Polynomials Extract From Local Sources}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {10:1--10:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.10}, URN = {urn:nbn:de:0030-drops-163519}, doi = {10.4230/LIPIcs.ICALP.2022.10}, annote = {Keywords: Randomness extractors, local sources, samplable sources, AC⁰ circuits, branching programs, low-degree polynomials, Chevalley-Warning} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bilo_et_al:LIPIcs.ICALP.2022.22, author = {Bil\`{o}, Davide and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin}, title = {{Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {22:1--22:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.22}, URN = {urn:nbn:de:0030-drops-163633}, doi = {10.4230/LIPIcs.ICALP.2022.22}, annote = {Keywords: derandomization, diameter, eccentricity, fault-tolerant data structure, sensitivity oracle, space lower bound} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma. Expander Random Walks: The General Case and Limitations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{cohen_et_al:LIPIcs.ICALP.2022.43, author = {Cohen, Gil and Minzer, Dor and Peleg, Shir and Potechin, Aaron and Ta-Shma, Amnon}, title = {{Expander Random Walks: The General Case and Limitations}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {43:1--43:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.43}, URN = {urn:nbn:de:0030-drops-163849}, doi = {10.4230/LIPIcs.ICALP.2022.43}, annote = {Keywords: Expander Graphs, Random Walks, Lower Bounds} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Gil Cohen and Tal Yankovitz. LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 44:1-44:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{cohen_et_al:LIPIcs.ICALP.2022.44, author = {Cohen, Gil and Yankovitz, Tal}, title = {{LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {44:1--44:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.44}, URN = {urn:nbn:de:0030-drops-163858}, doi = {10.4230/LIPIcs.ICALP.2022.44}, annote = {Keywords: Locally Correctable Codes, Locally Decodable Codes, Distance Amplifications} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Streaming Algorithms for Geometric Steiner Forest. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 47:1-47:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{czumaj_et_al:LIPIcs.ICALP.2022.47, author = {Czumaj, Artur and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Vesel\'{y}, Pavel}, title = {{Streaming Algorithms for Geometric Steiner Forest}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {47:1--47:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.47}, URN = {urn:nbn:de:0030-drops-163880}, doi = {10.4230/LIPIcs.ICALP.2022.47}, annote = {Keywords: Steiner forest, streaming, sublinear algorithms, dynamic programming} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Amit Deshpande and Rameshwar Pratap. One-Pass Additive-Error Subset Selection for 𝓁_p Subspace Approximation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{deshpande_et_al:LIPIcs.ICALP.2022.51, author = {Deshpande, Amit and Pratap, Rameshwar}, title = {{One-Pass Additive-Error Subset Selection for 𝓁\underlinep Subspace Approximation}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {51:1--51:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.51}, URN = {urn:nbn:de:0030-drops-163924}, doi = {10.4230/LIPIcs.ICALP.2022.51}, annote = {Keywords: Subspace approximation, streaming algorithms, low-rank approximation, adaptive sampling, volume sampling, subset selection} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ming Ding, Rasmus Kyng, and Peng Zhang. Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 54:1-54:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ding_et_al:LIPIcs.ICALP.2022.54, author = {Ding, Ming and Kyng, Rasmus and Zhang, Peng}, title = {{Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {54:1--54:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.54}, URN = {urn:nbn:de:0030-drops-163950}, doi = {10.4230/LIPIcs.ICALP.2022.54}, annote = {Keywords: Two-Commodity Flow Problems, Linear Programming, Fine-Grained Complexity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Chao Liao, Qingyun Chen, Bundit Laekhanukit, and Yuhao Zhang. Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 89:1-89:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{liao_et_al:LIPIcs.ICALP.2022.89, author = {Liao, Chao and Chen, Qingyun and Laekhanukit, Bundit and Zhang, Yuhao}, title = {{Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {89:1--89:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.89}, URN = {urn:nbn:de:0030-drops-164309}, doi = {10.4230/LIPIcs.ICALP.2022.89}, annote = {Keywords: Directed Steiner Tree, Hardness of Approximation, Fault-Tolerant and Survivable Network Design} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
William M. Hoza. Better Pseudodistributions and Derandomization for Space-Bounded Computation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 28:1-28:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{hoza:LIPIcs.APPROX/RANDOM.2021.28, author = {Hoza, William M.}, title = {{Better Pseudodistributions and Derandomization for Space-Bounded Computation}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {28:1--28:23}, 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.28}, URN = {urn:nbn:de:0030-drops-147217}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.28}, annote = {Keywords: Weighted pseudorandom generator, pseudorandom pseudodistribution, read-once branching program, derandomization, space complexity} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy, David Peleg, and R. Vijayaragunathan. Budgeted Dominating Sets in Uncertain Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{choudhary_et_al:LIPIcs.MFCS.2021.32, author = {Choudhary, Keerti and Cohen, Avi and Narayanaswamy, N. S. and Peleg, David and Vijayaragunathan, R.}, title = {{Budgeted Dominating Sets in Uncertain Graphs}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {32:1--32:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.32}, URN = {urn:nbn:de:0030-drops-144723}, doi = {10.4230/LIPIcs.MFCS.2021.32}, annote = {Keywords: Uncertain graphs, Dominating set, NP-hard, PTAS, treewidth, planar graph} }
Feedback for Dagstuhl Publishing