Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Adam Karczmarz and Marcin Smulewicz. On Fully Dynamic Strongly Connected Components. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 68:1-68:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{karczmarz_et_al:LIPIcs.ESA.2023.68, author = {Karczmarz, Adam and Smulewicz, Marcin}, title = {{On Fully Dynamic Strongly Connected Components}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {68:1--68:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.68}, URN = {urn:nbn:de:0030-drops-187211}, doi = {10.4230/LIPIcs.ESA.2023.68}, annote = {Keywords: dynamic strongly connected components, dynamic strong connectivity, dynamic reachability} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Anders Aamand, Adam Karczmarz, Jakub Łącki, Nikos Parotsidis, Peter M. R. Rasmussen, and Mikkel Thorup. Optimal Decremental Connectivity in Non-Sparse Graphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 6:1-6:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{aamand_et_al:LIPIcs.ICALP.2023.6, author = {Aamand, Anders and Karczmarz, Adam and {\L}\k{a}cki, Jakub and Parotsidis, Nikos and Rasmussen, Peter M. R. and Thorup, Mikkel}, title = {{Optimal Decremental Connectivity in Non-Sparse Graphs}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {6:1--6:17}, 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.6}, URN = {urn:nbn:de:0030-drops-180581}, doi = {10.4230/LIPIcs.ICALP.2023.6}, annote = {Keywords: decremental connectivity, dynamic connectivity} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Adam Karczmarz and Piotr Sankowski. Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 84:1-84:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{karczmarz_et_al:LIPIcs.ICALP.2023.84, author = {Karczmarz, Adam and Sankowski, Piotr}, title = {{Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {84:1--84: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.84}, URN = {urn:nbn:de:0030-drops-181363}, doi = {10.4230/LIPIcs.ICALP.2023.84}, annote = {Keywords: dynamic shortest paths, dynamic reachability, dynamic transitive closure} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Adam Karczmarz. Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 83:1-83:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{karczmarz:LIPIcs.ICALP.2021.83, author = {Karczmarz, Adam}, title = {{Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {83:1--83:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.83}, URN = {urn:nbn:de:0030-drops-141521}, doi = {10.4230/LIPIcs.ICALP.2021.83}, annote = {Keywords: Dynamic graph algorithms, minimum weight cycle, dynamic shortest paths} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Adam Karczmarz, Jakub Pawlewicz, and Piotr Sankowski. Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 46:1-46:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{karczmarz_et_al:LIPIcs.SoCG.2021.46, author = {Karczmarz, Adam and Pawlewicz, Jakub and Sankowski, Piotr}, title = {{Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {46:1--46:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.46}, URN = {urn:nbn:de:0030-drops-138454}, doi = {10.4230/LIPIcs.SoCG.2021.46}, annote = {Keywords: unit-disk graphs, shortest paths, distance oracles} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Jacob Holm and Eva Rotenberg. Good r-Divisions Imply Optimal Amortized Decremental Biconnectivity. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 42:1-42:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{holm_et_al:LIPIcs.STACS.2021.42, author = {Holm, Jacob and Rotenberg, Eva}, title = {{Good r-Divisions Imply Optimal Amortized Decremental Biconnectivity}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {42:1--42:18}, 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.42}, URN = {urn:nbn:de:0030-drops-136875}, doi = {10.4230/LIPIcs.STACS.2021.42}, annote = {Keywords: Dynamic graphs, 2-connectivity, graph minors, r-divisions, graph separators} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Panagiotis Charalampopoulos and Adam Karczmarz. Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 31:1-31:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{charalampopoulos_et_al:LIPIcs.ESA.2020.31, author = {Charalampopoulos, Panagiotis and Karczmarz, Adam}, title = {{Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {31:1--31:23}, 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.31}, URN = {urn:nbn:de:0030-drops-128970}, doi = {10.4230/LIPIcs.ESA.2020.31}, annote = {Keywords: dynamic graph algorithms, planar graphs, single-source shortest paths, strong connectivity} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Adam Karczmarz and Jakub Łącki. Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 65:1-65:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{karczmarz_et_al:LIPIcs.ESA.2019.65, author = {Karczmarz, Adam and {\L}\k{a}cki, Jakub}, title = {{Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {65:1--65:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.65}, URN = {urn:nbn:de:0030-drops-111862}, doi = {10.4230/LIPIcs.ESA.2019.65}, annote = {Keywords: shortest paths, dynamic, incremental, decremental, directed graphs, hubs} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Adam Karczmarz and Piotr Sankowski. Min-Cost Flow in Unit-Capacity Planar Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 66:1-66:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{karczmarz_et_al:LIPIcs.ESA.2019.66, author = {Karczmarz, Adam and Sankowski, Piotr}, title = {{Min-Cost Flow in Unit-Capacity Planar Graphs}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {66:1--66:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.66}, URN = {urn:nbn:de:0030-drops-111878}, doi = {10.4230/LIPIcs.ESA.2019.66}, annote = {Keywords: minimum-cost flow, minimum-cost circulation, planar graphs} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, and Eva Rotenberg. Decremental SPQR-trees for Planar Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 46:1-46:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{holm_et_al:LIPIcs.ESA.2018.46, author = {Holm, Jacob and Italiano, Giuseppe F. and Karczmarz, Adam and Lacki, Jakub and Rotenberg, Eva}, title = {{Decremental SPQR-trees for Planar Graphs}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {46:1--46:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.46}, URN = {urn:nbn:de:0030-drops-95091}, doi = {10.4230/LIPIcs.ESA.2018.46}, annote = {Keywords: Graph embeddings, data structures, graph algorithms, planar graphs, SPQR-trees, triconnectivity} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Pawel Gawrychowski and Adam Karczmarz. Improved Bounds for Shortest Paths in Dense Distance Graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 61:1-61:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{gawrychowski_et_al:LIPIcs.ICALP.2018.61, author = {Gawrychowski, Pawel and Karczmarz, Adam}, title = {{Improved Bounds for Shortest Paths in Dense Distance Graphs}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {61:1--61:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.61}, URN = {urn:nbn:de:0030-drops-90654}, doi = {10.4230/LIPIcs.ICALP.2018.61}, annote = {Keywords: shortest paths, dense distance graph, planar graph, Monge matrix} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Eva Rotenberg, and Piotr Sankowski. Contracting a Planar Graph Efficiently. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 50:1-50:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{holm_et_al:LIPIcs.ESA.2017.50, author = {Holm, Jacob and Italiano, Giuseppe F. and Karczmarz, Adam and Lacki, Jakub and Rotenberg, Eva and Sankowski, Piotr}, title = {{Contracting a Planar Graph Efficiently}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {50:1--50:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.50}, URN = {urn:nbn:de:0030-drops-78755}, doi = {10.4230/LIPIcs.ESA.2017.50}, annote = {Keywords: planar graphs, algorithms, data structures, connectivity, coloring} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Adam Karczmarz. A Simple Mergeable Dictionary. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 7:1-7:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{karczmarz:LIPIcs.SWAT.2016.7, author = {Karczmarz, Adam}, title = {{A Simple Mergeable Dictionary}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {7:1--7:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.7}, URN = {urn:nbn:de:0030-drops-60285}, doi = {10.4230/LIPIcs.SWAT.2016.7}, annote = {Keywords: dictionary, mergeable, data structure, merge, split} }
Feedback for Dagstuhl Publishing