Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja. Decremental Matching in General Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{assadi_et_al:LIPIcs.ICALP.2022.11, author = {Assadi, Sepehr and Bernstein, Aaron and Dudeja, Aditi}, title = {{Decremental Matching in General Graphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {11:1--11:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.11}, URN = {urn:nbn:de:0030-drops-163528}, doi = {10.4230/LIPIcs.ICALP.2022.11}, annote = {Keywords: Dynamic algorithms, matching, primal-dual algorithms} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Sepehr Assadi and Aditi Dudeja. Ruling Sets in Random Order and Adversarial Streams. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{assadi_et_al:LIPIcs.DISC.2021.6, author = {Assadi, Sepehr and Dudeja, Aditi}, title = {{Ruling Sets in Random Order and Adversarial Streams}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {6:1--6:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.6}, URN = {urn:nbn:de:0030-drops-148086}, doi = {10.4230/LIPIcs.DISC.2021.6}, annote = {Keywords: Symmetry breaking, Ruling sets, Lower bounds, Communication Complexity} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Aaron Bernstein, Aditi Dudeja, and Seth Pettie. Incremental SCC Maintenance in Sparse Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bernstein_et_al:LIPIcs.ESA.2021.14, author = {Bernstein, Aaron and Dudeja, Aditi and Pettie, Seth}, title = {{Incremental SCC Maintenance in Sparse Graphs}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {14:1--14:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.14}, URN = {urn:nbn:de:0030-drops-145950}, doi = {10.4230/LIPIcs.ESA.2021.14}, annote = {Keywords: Directed Graphs, Strongly Connected Components, Dynamic Graph Algorithms} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Aaron Bernstein and Aditi Dudeja. Online Matching with Recourse: Random Edge Arrivals. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bernstein_et_al:LIPIcs.FSTTCS.2020.11, author = {Bernstein, Aaron and Dudeja, Aditi}, title = {{Online Matching with Recourse: Random Edge Arrivals}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {11:1--11:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.11}, URN = {urn:nbn:de:0030-drops-132521}, doi = {10.4230/LIPIcs.FSTTCS.2020.11}, annote = {Keywords: matchings, edge-arrival, online model} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Rahul Ilango. Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 34:1-34:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{ilango:LIPIcs.ITCS.2020.34, author = {Ilango, Rahul}, title = {{Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0\lbrackp\rbrack}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {34:1--34:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.34}, URN = {urn:nbn:de:0030-drops-117191}, doi = {10.4230/LIPIcs.ITCS.2020.34}, annote = {Keywords: Minimum Circuit Size Problem, reductions, NP-completeness, circuit lower bounds} }
Feedback for Dagstuhl Publishing