OASIcs, Volume 48
ATMOS 2015, September 17, 2015, Patras, Greece
Editors: Giuseppe F. Italiano and Marie Schmidt
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Samir Datta, Asif Khan, and Anish Mukherjee. Dynamic Planar Embedding Is in DynFO. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 39:1-39:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{datta_et_al:LIPIcs.MFCS.2023.39, author = {Datta, Samir and Khan, Asif and Mukherjee, Anish}, title = {{Dynamic Planar Embedding Is in DynFO}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {39:1--39: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.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.39}, URN = {urn:nbn:de:0030-drops-185736}, doi = {10.4230/LIPIcs.MFCS.2023.39}, annote = {Keywords: Dynamic Complexity, Planar graphs, Planar embedding} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Loukas Georgiadis, Giuseppe F. Italiano, and Evangelos Kosinas. Computing the 4-Edge-Connected Components of a Graph: An Experimental Study. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 60:1-60:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{georgiadis_et_al:LIPIcs.ESA.2022.60, author = {Georgiadis, Loukas and Italiano, Giuseppe F. and Kosinas, Evangelos}, title = {{Computing the 4-Edge-Connected Components of a Graph: An Experimental Study}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {60:1--60:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.60}, URN = {urn:nbn:de:0030-drops-169988}, doi = {10.4230/LIPIcs.ESA.2022.60}, annote = {Keywords: Connectivity Cuts, Edge Connectivity, Graph Algorithms} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Loukas Georgiadis, Giuseppe F. Italiano, and Evangelos Kosinas. Computing the 4-Edge-Connected Components of a Graph in Linear Time. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 47:1-47:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{georgiadis_et_al:LIPIcs.ESA.2021.47, author = {Georgiadis, Loukas and Italiano, Giuseppe F. and Kosinas, Evangelos}, title = {{Computing the 4-Edge-Connected Components of a Graph in Linear Time}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {47:1--47:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus 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.2021.47}, URN = {urn:nbn:de:0030-drops-146286}, doi = {10.4230/LIPIcs.ESA.2021.47}, annote = {Keywords: Cuts, Edge Connectivity, Graph Algorithms} }
Published in: LIPIcs, Volume 201, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)
Travis Gagie, Garance Gourdel, and Giovanni Manzini. Compressing and Indexing Aligned Readsets. In 21st International Workshop on Algorithms in Bioinformatics (WABI 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 201, pp. 13:1-13:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{gagie_et_al:LIPIcs.WABI.2021.13, author = {Gagie, Travis and Gourdel, Garance and Manzini, Giovanni}, title = {{Compressing and Indexing Aligned Readsets}}, booktitle = {21st International Workshop on Algorithms in Bioinformatics (WABI 2021)}, pages = {13:1--13:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-200-6}, ISSN = {1868-8969}, year = {2021}, volume = {201}, editor = {Carbone, Alessandra and El-Kebir, Mohammed}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2021.13}, URN = {urn:nbn:de:0030-drops-143660}, doi = {10.4230/LIPIcs.WABI.2021.13}, annote = {Keywords: data compression, compact data structures, FM-index, Burrows-Wheeler Transform, EBWT, XBWT, DNA reads} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Giuseppe F. Italiano, Nicola Prezza, Blerina Sinaimeri, and Rossano Venturini. Compressed Weighted de Bruijn Graphs. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 16:1-16:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{italiano_et_al:LIPIcs.CPM.2021.16, author = {Italiano, Giuseppe F. and Prezza, Nicola and Sinaimeri, Blerina and Venturini, Rossano}, title = {{Compressed Weighted de Bruijn Graphs}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {16:1--16:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.16}, URN = {urn:nbn:de:0030-drops-139675}, doi = {10.4230/LIPIcs.CPM.2021.16}, annote = {Keywords: weighted de Bruijn graphs, k-mer annotation, compressed data structures, partial sums} }
Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)
Loukas Georgiadis, Konstantinos Giannis, Giuseppe F. Italiano, and Evangelos Kosinas. Computing Vertex-Edge Cut-Pairs and 2-Edge Cuts in Practice. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 20:1-20:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{georgiadis_et_al:LIPIcs.SEA.2021.20, author = {Georgiadis, Loukas and Giannis, Konstantinos and Italiano, Giuseppe F. and Kosinas, Evangelos}, title = {{Computing Vertex-Edge Cut-Pairs and 2-Edge Cuts in Practice}}, booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)}, pages = {20:1--20:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-185-6}, ISSN = {1868-8969}, year = {2021}, volume = {190}, editor = {Coudert, David and Natale, Emanuele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.20}, URN = {urn:nbn:de:0030-drops-137920}, doi = {10.4230/LIPIcs.SEA.2021.20}, annote = {Keywords: 2-Connectivity, Graph Algorithms, Split Components} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Loukas Georgiadis, Konstantinos Giannis, Giuseppe F. Italiano, Aikaterini Karanasiou, and Luigi Laura. Dynamic Dominators and Low-High Orders in DAGs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 50:1-50:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{georgiadis_et_al:LIPIcs.ESA.2019.50, author = {Georgiadis, Loukas and Giannis, Konstantinos and Italiano, Giuseppe F. and Karanasiou, Aikaterini and Laura, Luigi}, title = {{Dynamic Dominators and Low-High Orders in DAGs}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {50:1--50:18}, 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.50}, URN = {urn:nbn:de:0030-drops-111715}, doi = {10.4230/LIPIcs.ESA.2019.50}, annote = {Keywords: Connectivity, dominators, low-high orders} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemysław Uznański, and Daniel Wolleb-Graf. Faster Algorithms for All-Pairs Bounded Min-Cuts. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 7:1-7:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{abboud_et_al:LIPIcs.ICALP.2019.7, author = {Abboud, Amir and Georgiadis, Loukas and Italiano, Giuseppe F. and Krauthgamer, Robert and Parotsidis, Nikos and Trabelsi, Ohad and Uzna\'{n}ski, Przemys{\l}aw and Wolleb-Graf, Daniel}, title = {{Faster Algorithms for All-Pairs Bounded Min-Cuts}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {7:1--7:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.7}, URN = {urn:nbn:de:0030-drops-105833}, doi = {10.4230/LIPIcs.ICALP.2019.7}, annote = {Keywords: All-pairs min-cut, k-reachability, network coding, Directed graphs, fine-grained complexity} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Niklas Hjuler, Giuseppe F. Italiano, Nikos Parotsidis, and David Saulpic. Dominating Sets and Connected Dominating Sets in Dynamic Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 35:1-35:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{hjuler_et_al:LIPIcs.STACS.2019.35, author = {Hjuler, Niklas and Italiano, Giuseppe F. and Parotsidis, Nikos and Saulpic, David}, title = {{Dominating Sets and Connected Dominating Sets in Dynamic Graphs}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {35:1--35:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.35}, URN = {urn:nbn:de:0030-drops-102741}, doi = {10.4230/LIPIcs.STACS.2019.35}, annote = {Keywords: Dominating Set, Connected Dominating Set, Dynamic Graph Algorithms} }
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 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 75, 16th International Symposium on Experimental Algorithms (SEA 2017)
Loukas Georgiadis, Giuseppe F. Italiano, and Aikaterini Karanasiou. Approximating the Smallest 2-Vertex-Connected Spanning Subgraph via Low-High Orders. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 9:1-9:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{georgiadis_et_al:LIPIcs.SEA.2017.9, author = {Georgiadis, Loukas and Italiano, Giuseppe F. and Karanasiou, Aikaterini}, title = {{Approximating the Smallest 2-Vertex-Connected Spanning Subgraph via Low-High Orders}}, booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)}, pages = {9:1--9:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-036-1}, ISSN = {1868-8969}, year = {2017}, volume = {75}, editor = {Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.9}, URN = {urn:nbn:de:0030-drops-76299}, doi = {10.4230/LIPIcs.SEA.2017.9}, annote = {Keywords: 2-vertex connectivity, approximation algorithms, directed graphs} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Loukas Georgiadis, Thomas Dueholm Hansen, Giuseppe F. Italiano, Sebastian Krinninger, and Nikos Parotsidis. Decremental Data Structures for Connectivity and Dominators in Directed Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 42:1-42:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{georgiadis_et_al:LIPIcs.ICALP.2017.42, author = {Georgiadis, Loukas and Dueholm Hansen, Thomas and Italiano, Giuseppe F. and Krinninger, Sebastian and Parotsidis, Nikos}, title = {{Decremental Data Structures for Connectivity and Dominators in Directed Graphs}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {42:1--42: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.42}, URN = {urn:nbn:de:0030-drops-74455}, doi = {10.4230/LIPIcs.ICALP.2017.42}, annote = {Keywords: dynamic graph algorithms, decremental algorithms, dominator tree, strong connectivity under failures} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis, and Przemyslaw Uznanski. All-Pairs 2-Reachability in O(n^w log n) Time. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 74:1-74:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{georgiadis_et_al:LIPIcs.ICALP.2017.74, author = {Georgiadis, Loukas and Graf, Daniel and Italiano, Giuseppe F. and Parotsidis, Nikos and Uznanski, Przemyslaw}, title = {{All-Pairs 2-Reachability in O(n^w log n) Time}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {74:1--74:14}, 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.74}, URN = {urn:nbn:de:0030-drops-74510}, doi = {10.4230/LIPIcs.ICALP.2017.74}, annote = {Keywords: 2-reachability, All Dominator Trees, Directed Graphs, Boolean Matrix Multiplication} }
Feedback for Dagstuhl Publishing