LIPIcs, Volume 57
ESA 2016, August 22-24, 2016, Aarhus, Denmark
Editors: Piotr Sankowski and Christos Zaroliagis
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Thomas Bläsius, Maximilian Katzmann, and Marcus Wilhelm. Partitioning the Bags of a Tree Decomposition into Cliques. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 3:1-3:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{blasius_et_al:LIPIcs.SEA.2023.3, author = {Bl\"{a}sius, Thomas and Katzmann, Maximilian and Wilhelm, Marcus}, title = {{Partitioning the Bags of a Tree Decomposition into Cliques}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {3:1--3:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.3}, URN = {urn:nbn:de:0030-drops-183533}, doi = {10.4230/LIPIcs.SEA.2023.3}, annote = {Keywords: treewidth, weighted treewidth, algorithm engineering, cliques, clustering, complex networks} }
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 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} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Piotr Sankowski and Christos Zaroliagis. LIPIcs, Volume 57, ESA'16, Complete Volume. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@Proceedings{sankowski_et_al:LIPIcs.ESA.2016, title = {{LIPIcs, Volume 57, ESA'16, Complete Volume}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016}, URN = {urn:nbn:de:0030-drops-65854}, doi = {10.4230/LIPIcs.ESA.2016}, annote = {Keywords: Data Structures, Nonnumerical Algorithms and Problems, Optimization, Discrete Mathematics, Mathematical Software, Algorithms, Problem Solving, Control Methods and Search, Computational Geometry and Object Modeling} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Piotr Sankowski and Christos Zaroliagis. Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 0:i-0:xxiv, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{sankowski_et_al:LIPIcs.ESA.2016.0, author = {Sankowski, Piotr and Zaroliagis, Christos}, title = {{Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {0:i--0:xxiv}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.0}, URN = {urn:nbn:de:0030-drops-63429}, doi = {10.4230/LIPIcs.ESA.2016.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Loukas Georgiadis, Giuseppe F. Italiano, and Nikos Parotsidis. 2-Connectivity in Directed Graphs (Invited Talk). In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 1:1-1:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{georgiadis_et_al:LIPIcs.ESA.2016.1, author = {Georgiadis, Loukas and Italiano, Giuseppe F. and Parotsidis, Nikos}, title = {{2-Connectivity in Directed Graphs}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {1:1--1:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.1}, URN = {urn:nbn:de:0030-drops-63451}, doi = {10.4230/LIPIcs.ESA.2016.1}, annote = {Keywords: 2-edge and 2-vertex connectivity on directed graphs, graph algorithms, dominator trees} }
Feedback for Dagstuhl Publishing