LIPIcs, Volume 57
ESA 2016, August 22-24, 2016, Aarhus, Denmark
Editors: Piotr Sankowski and Christos Zaroliagis
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 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 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 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Dušan Knop, Tomáš Masařík, and Tomáš Toufar. Parameterized Complexity of Fair Vertex Evaluation Problems. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{knop_et_al:LIPIcs.MFCS.2019.33, author = {Knop, Du\v{s}an and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Toufar, Tom\'{a}\v{s}}, title = {{Parameterized Complexity of Fair Vertex Evaluation Problems}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {33:1--33: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.33}, URN = {urn:nbn:de:0030-drops-109775}, doi = {10.4230/LIPIcs.MFCS.2019.33}, annote = {Keywords: Fair objective, metatheorem, fair vertex cover, twin cover, modular width} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Sandra Kiefer and Daniel Neuen. The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kiefer_et_al:LIPIcs.MFCS.2019.45, author = {Kiefer, Sandra and Neuen, Daniel}, title = {{The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {45:1--45:15}, 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.45}, URN = {urn:nbn:de:0030-drops-109893}, doi = {10.4230/LIPIcs.MFCS.2019.45}, annote = {Keywords: Weisfeiler-Leman, separators, first-order logic, counting quantifiers} }
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 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)
Andrew M. Childs, Eddie Schoute, and Cem M. Unsal. Circuit Transformations for Quantum Architectures. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{childs_et_al:LIPIcs.TQC.2019.3, author = {Childs, Andrew M. and Schoute, Eddie and Unsal, Cem M.}, title = {{Circuit Transformations for Quantum Architectures}}, booktitle = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)}, pages = {3:1--3:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-112-2}, ISSN = {1868-8969}, year = {2019}, volume = {135}, editor = {van Dam, Wim and Man\v{c}inska, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.3}, URN = {urn:nbn:de:0030-drops-103958}, doi = {10.4230/LIPIcs.TQC.2019.3}, annote = {Keywords: quantum circuit, quantum architectures, circuit mapping} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee. Planar Maximum Matching: Towards a Parallel Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 21:1-21:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{datta_et_al:LIPIcs.ISAAC.2018.21, author = {Datta, Samir and Kulkarni, Raghav and Kumar, Ashish and Mukherjee, Anish}, title = {{Planar Maximum Matching: Towards a Parallel Algorithm}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {21:1--21:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.21}, URN = {urn:nbn:de:0030-drops-99695}, doi = {10.4230/LIPIcs.ISAAC.2018.21}, annote = {Keywords: maximum matching, planar graphs, parallel complexity, reductions} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Marek Cygan, Artur Czumaj, Marcin Mucha, and Piotr Sankowski. Online Facility Location with Deletions. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 21:1-21:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{cygan_et_al:LIPIcs.ESA.2018.21, author = {Cygan, Marek and Czumaj, Artur and Mucha, Marcin and Sankowski, Piotr}, title = {{Online Facility Location with Deletions}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {21:1--21:15}, 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.21}, URN = {urn:nbn:de:0030-drops-94843}, doi = {10.4230/LIPIcs.ESA.2018.21}, annote = {Keywords: online algorithms, facility location, fully-dynamic online algorithms} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Piotr Sankowski. NC Algorithms for Weighted Planar Perfect Matching and Related Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 97:1-97:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{sankowski:LIPIcs.ICALP.2018.97, author = {Sankowski, Piotr}, title = {{NC Algorithms for Weighted Planar Perfect Matching and Related Problems}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {97:1--97:16}, 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.97}, URN = {urn:nbn:de:0030-drops-91011}, doi = {10.4230/LIPIcs.ICALP.2018.97}, annote = {Keywords: planar graph, NC algorithms, maximum cardinality matching, maximum weight matching, min-cost flow, maximum multiple-source multiple-sink flow, f-factors} }
Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Piotr Sankowski and Piotr Wygocki. Approximate Nearest Neighbors Search Without False Negatives For l_2 For c>sqrt{loglog{n}}. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 63:1-63:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{sankowski_et_al:LIPIcs.ISAAC.2017.63, author = {Sankowski, Piotr and Wygocki, Piotr}, title = {{Approximate Nearest Neighbors Search Without False Negatives For l\underline2 For c\ranglesqrt\{loglog\{n\}\}}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {63:1--63:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.63}, URN = {urn:nbn:de:0030-drops-82189}, doi = {10.4230/LIPIcs.ISAAC.2017.63}, annote = {Keywords: locality sensitive hashing, approximate near neighbor search, high- dimensional, similarity search} }
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 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Robert Krauthgamer and Ohad Trabelsi. Conditional Lower Bounds for All-Pairs Max-Flow. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 20:1-20:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{krauthgamer_et_al:LIPIcs.ICALP.2017.20, author = {Krauthgamer, Robert and Trabelsi, Ohad}, title = {{Conditional Lower Bounds for All-Pairs Max-Flow}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {20:1--20:13}, 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.20}, URN = {urn:nbn:de:0030-drops-74264}, doi = {10.4230/LIPIcs.ICALP.2017.20}, annote = {Keywords: Conditional lower bounds, Hardness in P, All-Pairs Maximum Flow, Strong Exponential Time Hypothesis} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Piotr Sankowski and Karol Wegrzycki. Improved Distance Queries and Cycle Counting by Frobenius Normal Form. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 56:1-56:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{sankowski_et_al:LIPIcs.STACS.2017.56, author = {Sankowski, Piotr and Wegrzycki, Karol}, title = {{Improved Distance Queries and Cycle Counting by Frobenius Normal Form}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {56:1--56:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert 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.2017.56}, URN = {urn:nbn:de:0030-drops-69773}, doi = {10.4230/LIPIcs.STACS.2017.56}, annote = {Keywords: Frobenius Normal Form, Graph Algorithms, All Nodes Shortest Cycles} }
Feedback for Dagstuhl Publishing