Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, and Martin Schirneck. Fault-Tolerant ST-Diameter Oracles. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 24:1-24:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bilo_et_al:LIPIcs.ICALP.2023.24, author = {Bil\`{o}, Davide and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Krogmann, Simon and Schirneck, Martin}, title = {{Fault-Tolerant ST-Diameter Oracles}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {24:1--24:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.24}, URN = {urn:nbn:de:0030-drops-180762}, doi = {10.4230/LIPIcs.ICALP.2023.24}, annote = {Keywords: diameter oracles, distance sensitivity oracles, space lower bounds, fault-tolerant data structures} }
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.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)
Diptarka Chakraborty, Kushagra Chatterjee, and Keerti Choudhary. Pairwise Reachability Oracles and Preservers Under Failures. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 35:1-35:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{chakraborty_et_al:LIPIcs.ICALP.2022.35, author = {Chakraborty, Diptarka and Chatterjee, Kushagra and Choudhary, Keerti}, title = {{Pairwise Reachability Oracles and Preservers Under Failures}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {35:1--35:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.35}, URN = {urn:nbn:de:0030-drops-163768}, doi = {10.4230/LIPIcs.ICALP.2022.35}, annote = {Keywords: Fault-tolerant, Reachability Oracle, Reachability Preservers, Graph sparsification, Lower bounds} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Davide Bilò, Katrin Casel, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, J.A. Gregor Lagodzinski, Martin Schirneck, and Simon Wietheger. Fixed-Parameter Sensitivity Oracles. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 23:1-23:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bilo_et_al:LIPIcs.ITCS.2022.23, author = {Bil\`{o}, Davide and Casel, Katrin and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Lagodzinski, J.A. Gregor and Schirneck, Martin and Wietheger, Simon}, title = {{Fixed-Parameter Sensitivity Oracles}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {23:1--23:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.23}, URN = {urn:nbn:de:0030-drops-156196}, doi = {10.4230/LIPIcs.ITCS.2022.23}, annote = {Keywords: data structures, distance preservers, distance sensitivity oracles, fault tolerance, fixed-parameter tractability, k-path, vertex cover} }
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.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} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Amotz Bar-Noy, Keerti Choudhary, Avi Cohen, David Peleg, and Dror Rawitz. Minimum Neighboring Degree Realization in Graphs and Trees. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 10:1-10:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{barnoy_et_al:LIPIcs.ESA.2020.10, author = {Bar-Noy, Amotz and Choudhary, Keerti and Cohen, Avi and Peleg, David and Rawitz, Dror}, title = {{Minimum Neighboring Degree Realization in Graphs and Trees}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {10:1--10: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.10}, URN = {urn:nbn:de:0030-drops-128765}, doi = {10.4230/LIPIcs.ESA.2020.10}, annote = {Keywords: Graph realization, neighborhood profile, graph algorithms, degree sequences} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Greg Bodwin, Keerti Choudhary, Merav Parter, and Noa Shahar. New Fault Tolerant Subset Preservers. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 15:1-15:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{bodwin_et_al:LIPIcs.ICALP.2020.15, author = {Bodwin, Greg and Choudhary, Keerti and Parter, Merav and Shahar, Noa}, title = {{New Fault Tolerant Subset Preservers}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {15:1--15:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.15}, URN = {urn:nbn:de:0030-drops-124222}, doi = {10.4230/LIPIcs.ICALP.2020.15}, annote = {Keywords: Subset Preservers, Distances, Fault-tolerance} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Diptarka Chakraborty and Keerti Choudhary. New Extremal Bounds for Reachability and Strong-Connectivity Preservers Under Failures. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 25:1-25:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chakraborty_et_al:LIPIcs.ICALP.2020.25, author = {Chakraborty, Diptarka and Choudhary, Keerti}, title = {{New Extremal Bounds for Reachability and Strong-Connectivity Preservers Under Failures}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {25:1--25:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.25}, URN = {urn:nbn:de:0030-drops-124327}, doi = {10.4230/LIPIcs.ICALP.2020.25}, annote = {Keywords: Preservers, Strong-connectivity, Reachability, Fault-tolerant, Graph sparsification} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Graph Realizations: Maximum Degree in Vertex Neighborhoods. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 10:1-10:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{barnoy_et_al:LIPIcs.SWAT.2020.10, author = {Bar-Noy, Amotz and Choudhary, Keerti and Peleg, David and Rawitz, Dror}, title = {{Graph Realizations: Maximum Degree in Vertex Neighborhoods}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {10:1--10:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.10}, URN = {urn:nbn:de:0030-drops-122572}, doi = {10.4230/LIPIcs.SWAT.2020.10}, annote = {Keywords: Graph realization, neighborhood profile, extremum-degree} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Efficiently Realizing Interval Sequences. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 47:1-47:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{barnoy_et_al:LIPIcs.ISAAC.2019.47, author = {Bar-Noy, Amotz and Choudhary, Keerti and Peleg, David and Rawitz, Dror}, title = {{Efficiently Realizing Interval Sequences}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {47:1--47:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.47}, URN = {urn:nbn:de:0030-drops-115430}, doi = {10.4230/LIPIcs.ISAAC.2019.47}, annote = {Keywords: Graph realization, graphic sequence, interval sequence} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Surender Baswana, Shiv Gupta, and Ayush Tulsyan. Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 65:1-65:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{baswana_et_al:LIPIcs.MFCS.2019.65, author = {Baswana, Surender and Gupta, Shiv and Tulsyan, Ayush}, title = {{Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {65:1--65:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.65}, URN = {urn:nbn:de:0030-drops-110096}, doi = {10.4230/LIPIcs.MFCS.2019.65}, annote = {Keywords: Depth first search, DFS, Dynamic graph algorithms, Fault tolerant} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Davide Bilò, Keerti Choudhary, Luciano Gualà, Stefano Leucci, Merav Parter, and Guido Proietti. Efficient Oracles and Routing Schemes for Replacement Paths. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 13:1-13:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{bilo_et_al:LIPIcs.STACS.2018.13, author = {Bil\`{o}, Davide and Choudhary, Keerti and Gual\`{a}, Luciano and Leucci, Stefano and Parter, Merav and Proietti, Guido}, title = {{Efficient Oracles and Routing Schemes for Replacement Paths}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {13:1--13:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.13}, URN = {urn:nbn:de:0030-drops-85249}, doi = {10.4230/LIPIcs.STACS.2018.13}, annote = {Keywords: Fault tolerant, Shortest path, Oracle, Routing} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Surender Baswana, Keerti Choudhary, and Liam Roditty. An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 72:1-72:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{baswana_et_al:LIPIcs.ICALP.2017.72, author = {Baswana, Surender and Choudhary, Keerti and Roditty, Liam}, title = {{An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {72:1--72:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.72}, URN = {urn:nbn:de:0030-drops-74168}, doi = {10.4230/LIPIcs.ICALP.2017.72}, annote = {Keywords: Fault tolerant, Directed graph, Strongly connected components} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Keerti Choudhary. An Optimal Dual Fault Tolerant Reachability Oracle. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 130:1-130:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{choudhary:LIPIcs.ICALP.2016.130, author = {Choudhary, Keerti}, title = {{An Optimal Dual Fault Tolerant Reachability Oracle}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {130:1--130:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.130}, URN = {urn:nbn:de:0030-drops-62659}, doi = {10.4230/LIPIcs.ICALP.2016.130}, annote = {Keywords: Fault tolerant, Directed graph, Reachability oracle, Labeling scheme} }
Feedback for Dagstuhl Publishing