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 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 134, 33rd European Conference on Object-Oriented Programming (ECOOP 2019)
Noah Van Es, Quentin Stiévenart, and Coen De Roover. Garbage-Free Abstract Interpretation Through Abstract Reference Counting. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 10:1-10:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{vanes_et_al:LIPIcs.ECOOP.2019.10, author = {Van Es, Noah and Sti\'{e}venart, Quentin and De Roover, Coen}, title = {{Garbage-Free Abstract Interpretation Through Abstract Reference Counting}}, booktitle = {33rd European Conference on Object-Oriented Programming (ECOOP 2019)}, pages = {10:1--10:33}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-111-5}, ISSN = {1868-8969}, year = {2019}, volume = {134}, editor = {Donaldson, Alastair F.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2019.10}, URN = {urn:nbn:de:0030-drops-108022}, doi = {10.4230/LIPIcs.ECOOP.2019.10}, annote = {Keywords: abstract interpretation, abstract garbage collection, reference counting} }
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} }
Feedback for Dagstuhl Publishing