Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)
Jacques Dark, Adithya Diddapur, and Christian Konrad. Interval Selection in Data Streams: Weighted Intervals and the Insertion-Deletion Setting. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dark_et_al:LIPIcs.FSTTCS.2023.24, author = {Dark, Jacques and Diddapur, Adithya and Konrad, Christian}, title = {{Interval Selection in Data Streams: Weighted Intervals and the Insertion-Deletion Setting}}, booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)}, pages = {24:1--24:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-304-1}, ISSN = {1868-8969}, year = {2023}, volume = {284}, editor = {Bouyer, Patricia and Srinivasan, Srikanth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.24}, URN = {urn:nbn:de:0030-drops-193976}, doi = {10.4230/LIPIcs.FSTTCS.2023.24}, annote = {Keywords: Streaming Algorithms, Interval Selection, Weighted Intervals, Insertion-deletion Streams} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Cezar-Mihail Alexandru, Pavel Dvořák, Christian Konrad, and Kheeran K. Naidu. Improved Weighted Matching in the Sliding Window Model. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{alexandru_et_al:LIPIcs.STACS.2023.6, author = {Alexandru, Cezar-Mihail and Dvo\v{r}\'{a}k, Pavel and Konrad, Christian and Naidu, Kheeran K.}, title = {{Improved Weighted Matching in the Sliding Window Model}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {6:1--6:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.6}, URN = {urn:nbn:de:0030-drops-176585}, doi = {10.4230/LIPIcs.STACS.2023.6}, annote = {Keywords: Sliding window algorithms, Streaming algorithms, Maximum-weight matching} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Christian Konrad, Kheeran K. Naidu, and Arun Steward. Maximum Matching via Maximal Matching Queries. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 41:1-41:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{konrad_et_al:LIPIcs.STACS.2023.41, author = {Konrad, Christian and Naidu, Kheeran K. and Steward, Arun}, title = {{Maximum Matching via Maximal Matching Queries}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {41:1--41:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.41}, URN = {urn:nbn:de:0030-drops-176935}, doi = {10.4230/LIPIcs.STACS.2023.41}, annote = {Keywords: Maximum Matching, Query Model, Algorithms, Lower Bounds} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Moran Feldman and Ariel Szarf. Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 33:1-33:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{feldman_et_al:LIPIcs.APPROX/RANDOM.2022.33, author = {Feldman, Moran and Szarf, Ariel}, title = {{Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {33:1--33:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.33}, URN = {urn:nbn:de:0030-drops-171559}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.33}, annote = {Keywords: Maximum matching, semi-streaming algorithms, multi-pass algorithms} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Kheeran K. Naidu and Vihan Shah. Space Optimal Vertex Cover in Dynamic Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{naidu_et_al:LIPIcs.APPROX/RANDOM.2022.53, author = {Naidu, Kheeran K. and Shah, Vihan}, title = {{Space Optimal Vertex Cover in Dynamic Streams}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {53:1--53:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.53}, URN = {urn:nbn:de:0030-drops-171753}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.53}, annote = {Keywords: Graph Streaming Algorithms, Vertex Cover, Dynamic Streams, Approximation Algorithm} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Sanjeev Khanna and Christian Konrad. Optimal Bounds for Dominating Set in Graph Streams. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 93:1-93:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{khanna_et_al:LIPIcs.ITCS.2022.93, author = {Khanna, Sanjeev and Konrad, Christian}, title = {{Optimal Bounds for Dominating Set in Graph Streams}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {93:1--93:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.93}, URN = {urn:nbn:de:0030-drops-156894}, doi = {10.4230/LIPIcs.ITCS.2022.93}, annote = {Keywords: Streaming algorithms, communication complexity, information complexity, dominating set} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Christian Konrad and Kheeran K. Naidu. On Two-Pass Streaming Algorithms for Maximum Bipartite Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{konrad_et_al:LIPIcs.APPROX/RANDOM.2021.19, author = {Konrad, Christian and Naidu, Kheeran K.}, title = {{On Two-Pass Streaming Algorithms for Maximum Bipartite Matching}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {19:1--19:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.19}, URN = {urn:nbn:de:0030-drops-147128}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.19}, annote = {Keywords: Data streaming, matchings, lower bounds} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Lidiya Khalidah binti Khalil and Christian Konrad. Constructing Large Matchings via Query Access to a Maximal Matching Oracle. 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. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{khalil_et_al:LIPIcs.FSTTCS.2020.26, author = {Khalil, Lidiya Khalidah binti and Konrad, Christian}, title = {{Constructing Large Matchings via Query Access to a Maximal Matching Oracle}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {26:1--26:15}, 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.26}, URN = {urn:nbn:de:0030-drops-132673}, doi = {10.4230/LIPIcs.FSTTCS.2020.26}, annote = {Keywords: Maximum matching approximation, Query model, Streaming algorithms} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Jacques Dark and Christian Konrad. Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{dark_et_al:LIPIcs.CCC.2020.30, author = {Dark, Jacques and Konrad, Christian}, title = {{Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {30:1--30:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.30}, URN = {urn:nbn:de:0030-drops-125824}, doi = {10.4230/LIPIcs.CCC.2020.30}, annote = {Keywords: Maximum matching, Minimum vertex cover, Dynamic graph streams, Communication complexity, Lower bounds} }
Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)
Christian Konrad, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. The Complexity of Symmetry Breaking in Massive Graphs. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{konrad_et_al:LIPIcs.DISC.2019.26, author = {Konrad, Christian and Pemmaraju, Sriram V. and Riaz, Talal and Robinson, Peter}, title = {{The Complexity of Symmetry Breaking in Massive Graphs}}, booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)}, pages = {26:1--26:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-126-9}, ISSN = {1868-8969}, year = {2019}, volume = {146}, editor = {Suomela, Jukka}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.26}, URN = {urn:nbn:de:0030-drops-113337}, doi = {10.4230/LIPIcs.DISC.2019.26}, annote = {Keywords: communication complexity, information theory, k-machine model, maximal independent set, ruling set, streaming algorithms} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Christian Konrad and Viktor Zamaraev. Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{konrad_et_al:LIPIcs.MFCS.2019.21, author = {Konrad, Christian and Zamaraev, Viktor}, title = {{Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {21:1--21:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.21}, URN = {urn:nbn:de:0030-drops-109651}, doi = {10.4230/LIPIcs.MFCS.2019.21}, annote = {Keywords: local model, approximation algorithms, minimum vertex coloring, maximum independent set, chordal graphs} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Graham Cormode, Jacques Dark, and Christian Konrad. Independent Sets in Vertex-Arrival Streams. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cormode_et_al:LIPIcs.ICALP.2019.45, author = {Cormode, Graham and Dark, Jacques and Konrad, Christian}, title = {{Independent Sets in Vertex-Arrival Streams}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {45:1--45:14}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.45}, URN = {urn:nbn:de:0030-drops-106212}, doi = {10.4230/LIPIcs.ICALP.2019.45}, annote = {Keywords: streaming algorithms, independent set size, lower bounds} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Artur Czumaj and Christian Konrad. Detecting Cliques in CONGEST Networks. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{czumaj_et_al:LIPIcs.DISC.2018.16, author = {Czumaj, Artur and Konrad, Christian}, title = {{Detecting Cliques in CONGEST Networks}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {16:1--16:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.16}, URN = {urn:nbn:de:0030-drops-98057}, doi = {10.4230/LIPIcs.DISC.2018.16}, annote = {Keywords: Lower bounds, CONGEST, subgraph detection, two-party communication} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Christian Konrad. A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 74:1-74:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{konrad:LIPIcs.MFCS.2018.74, author = {Konrad, Christian}, title = {{A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {74:1--74:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.74}, URN = {urn:nbn:de:0030-drops-96560}, doi = {10.4230/LIPIcs.MFCS.2018.74}, annote = {Keywords: Matchings, augmenting paths, streaming algorithms, random order} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Eden Chlamtac, Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca. The Densest k-Subhypergraph Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{chlamtac_et_al:LIPIcs.APPROX-RANDOM.2016.6, author = {Chlamtac, Eden and Dinitz, Michael and Konrad, Christian and Kortsarz, Guy and Rabanca, George}, title = {{The Densest k-Subhypergraph Problem}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {6:1--6:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.6}, URN = {urn:nbn:de:0030-drops-66298}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.6}, annote = {Keywords: Hypergraphs, Approximation algorithms} }
Feedback for Dagstuhl Publishing