Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, and Christian Wulff-Nilsen. Constructing Light Spanners Deterministically in Near-Linear Time. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{alstrup_et_al:LIPIcs.ESA.2019.4, author = {Alstrup, Stephen and Dahlgaard, S{\o}ren and Filtser, Arnold and St\"{o}ckel, Morten and Wulff-Nilsen, Christian}, title = {{Constructing Light Spanners Deterministically in Near-Linear Time}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {4:1--4: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.4}, URN = {urn:nbn:de:0030-drops-111255}, doi = {10.4230/LIPIcs.ESA.2019.4}, annote = {Keywords: Spanners, Light Spanners, Efficient Construction, Deterministic Dynamic Distance Oracle} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Søren Dahlgaard. On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{dahlgaard:LIPIcs.ICALP.2016.48, author = {Dahlgaard, S{\o}ren}, title = {{On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {48:1--48:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.48}, URN = {urn:nbn:de:0030-drops-63289}, doi = {10.4230/LIPIcs.ICALP.2016.48}, annote = {Keywords: Conditional lower bounds, Maximum cardinality matching, Diameter in graphs, Hardness in P, Partially dynamic problems, Maximum flow} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Ely Porat. Sublinear Distance Labeling. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{alstrup_et_al:LIPIcs.ESA.2016.5, author = {Alstrup, Stephen and Dahlgaard, S{\o}ren and Knudsen, Mathias B{\ae}k Tejs and Porat, Ely}, title = {{Sublinear Distance Labeling}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {5:1--5:15}, 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.5}, URN = {urn:nbn:de:0030-drops-63479}, doi = {10.4230/LIPIcs.ESA.2016.5}, annote = {Keywords: Graph labeling schemes, Distance labeling, Graph theory, Sparse graphs} }