default search action
Christian Konrad 0001
Person information
- affiliation: University of Bristol, Bristol, UK
Other persons with the same name
- Christian Konrad 0002 — RWTH Aachen University, Aachen, Germany
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c38]Cezar-Mihail Alexandru, Christian Konrad:
Interval Selection in Sliding Windows. ESA 2024: 8:1-8:17 - [c37]Christian Konrad, Andrew McGregor, Rik Sengupta, Cuong Than:
Matchings in Low-Arboricity Graphs in the Dynamic Graph Stream Model. FSTTCS 2024: 29:1-29:15 - [c36]Christian Konrad, Kheeran K. Naidu
:
An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation. SODA 2024: 2881-2899 - [c35]Sepehr Assadi
O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent Set. STOC 2024: 847-858 - [i25]Christian Konrad, Conor O'Sullivan, Victor Traistaru:
Graph Reconstruction via MIS Queries. CoRR abs/2401.05845 (2024) - [i24]Cezar-Mihail Alexandru, Christian Konrad:
Interval Selection in Sliding Windows. CoRR abs/2405.09338 (2024) - [i23]Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan:
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams. CoRR abs/2407.21005 (2024) - 2023
- [c34]Jacques Dark, Adithya Diddapur, Christian Konrad:
Interval Selection in Data Streams: Weighted Intervals and the Insertion-Deletion Setting. FSTTCS 2023: 24:1-24:17 - [c33]Sanjeev Khanna
Set Cover in the One-pass Edge-arrival Streaming Model. PODS 2023: 127-139 - [c32]Cezar-Mihail Alexandru
Improved Weighted Matching in the Sliding Window Model. STACS 2023: 6:1-6:21 - [c31]Christian Konrad, Kheeran K. Naidu
Maximum Matching via Maximal Matching Queries. STACS 2023: 41:1-41:22 - [i22]Sepehr Assadi, Christian Konrad, Kheeran K. Naidu, Janani Sundaresan:
O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set. CoRR abs/2312.13178 (2023) - 2022
- [j14]Christian Konrad, Tigran Tonoyan:
Guessing fractions of online sequences. Discret. Appl. Math. 308: 147-161 (2022) - [j13]Christian Konrad, Viktor Zamaraev
Distributed minimum vertex coloring and maximum independent set in chordal graphs. Theor. Comput. Sci. 922: 486-502 (2022) - [c30]Sanjeev Khanna, Christian Konrad:
Optimal Bounds for Dominating Set in Graph Streams. ITCS 2022: 93:1-93:23 - [i21]Cezar-Mihail Alexandru, Pavel Dvorák, Christian Konrad, Kheeran K. Naidu:
Closing the Gap between Weighted and Unweighted Matching in the Sliding Window Model. CoRR abs/2204.04717 (2022) - 2021
- [c29]Michael Barlow, Christian Konrad, Charana Nandasena:
Streaming Set Cover in Practice. ALENEX 2021: 181-192 - [c28]Christian Konrad, Kheeran K. Naidu
On Two-Pass Streaming Algorithms for Maximum Bipartite Matching. APPROX-RANDOM 2021: 19:1-19:18 - [c27]Christian Konrad:
Frequent Elements with Witnesses in Data Streams. PODS 2021: 83-95 - [i20]Christian Konrad, Peter Robinson, Viktor Zamaraev:
Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication. CoRR abs/2103.07027 (2021) - [i19]Christian Konrad, Sriram V. Pemmaraju, Talal Riaz, Peter Robinson:
The Complexity of Symmetry Breaking in Massive Graphs. CoRR abs/2105.01833 (2021) - [i18]Christian Konrad, Kheeran K. Naidu:
On Two-Pass Streaming Algorithms for Maximum Bipartite Matching. CoRR abs/2107.07841 (2021) - 2020
- [j12]Artur Czumaj, Christian Konrad:
Detecting cliques in CONGEST networks. Distributed Comput. 33(6): 533-543 (2020) - [j11]Magnús M. Halldórsson
Improved distributed algorithms for coloring interval graphs with application to multicoloring trees. Theor. Comput. Sci. 811: 29-41 (2020) - [j10]Rajiv Gandhi, Magnús M. Halldórsson, Christian Konrad, Guy Kortsarz, Hoon Oh:
Radio aggregation scheduling. Theor. Comput. Sci. 840: 143-153 (2020) - [j9]Magnús M. Halldórsson, Christian Konrad, Tigran Tonoyan:
Limitations of current wireless link scheduling algorithms. Theor. Comput. Sci. 840: 154-165 (2020) - [c26]Jacques Dark
Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams. CCC 2020: 30:1-30:14 - [c25]Lidiya Khalidah binti Khalil, Christian Konrad
Constructing Large Matchings via Query Access to a Maximal Matching Oracle. FSTTCS 2020: 26:1-26:15 - [i17]Jacques Dark, Christian Konrad:
Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams. CoRR abs/2005.11116 (2020) - [i16]Lidiya Khalidah binti Khalil, Christian Konrad:
Constructing Large Matchings via Query Access to a Maximal Matching Oracle. CoRR abs/2009.13409 (2020)
2010 – 2019
- 2019
- [c24]Graham Cormode
Independent Sets in Vertex-Arrival Streams. ICALP 2019: 45:1-45:14 - [c23]Christian Konrad, Viktor Zamaraev
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs. MFCS 2019: 21:1-21:15 - [c22]Christian Konrad, Sriram V. Pemmaraju, Talal Riaz, Peter Robinson:
The Complexity of Symmetry Breaking in Massive Graphs. DISC 2019: 26:1-26:18 - [i15]Christian Konrad:
Streaming Frequent Items with Timestamps and Detecting Large Neighborhoods in Graph Streams. CoRR abs/1911.08832 (2019) - 2018
- [j8]Magnús M. Halldórsson
Computing large independent sets in a single round. Distributed Comput. 31(1): 69-82 (2018) - [j7]Christoph Dürr
The triangle scheduling problem. J. Sched. 21(3): 305-312 (2018) - [j6]Eden Chlamtác, Michael Dinitz
The Densest k-Subhypergraph Problem. SIAM J. Discret. Math. 32(2): 1458-1477 (2018) - [c21]Graham Cormode
Approximating the Caro-Wei Bound for Independent Sets in Graph Streams. ISCO 2018: 101-114 - [c20]Christian Konrad, Tigran Tonoyan:
Preemptively Guessing the Center. ISCO 2018: 277-289 - [c19]Christian Konrad:
A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms. MFCS 2018: 74:1-74:16 - [c18]Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, Ronitt Rubinfeld:
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover. PODC 2018: 129-138 - [c17]Christian Konrad, Viktor Zamaraev
Brief Announcement: Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs. PODC 2018: 159-161 - [c16]Artur Czumaj, Christian Konrad:
Detecting Cliques in CONGEST Networks. DISC 2018: 16:1-16:15 - [i14]Christian Konrad:
MIS in the Congested Clique Model in O(log log Δ) Rounds. CoRR abs/1802.07647 (2018) - [i13]Christian Konrad, Viktor Zamaraev:
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs. CoRR abs/1805.04544 (2018) - [i12]Artur Czumaj, Christian Konrad:
Detecting cliques in CONGEST networks. CoRR abs/1807.01070 (2018) - [i11]Graham Cormode, Jacques Dark, Christian Konrad:
Independent Sets in Vertex-Arrival Streams. CoRR abs/1807.08331 (2018) - 2017
- [j5]Christian Konrad:
SIROCCO 2017 Review. SIGACT News 48(4): 80-86 (2017) - [c15]Magnús M. Halldórsson
Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees. SIROCCO 2017: 247-262 - [i10]Christian Konrad, Tigran Tonoyan:
Preemptive Online Partitioning of Sequences. CoRR abs/1702.06099 (2017) - [i9]Graham Cormode, Jacques Dark, Christian Konrad:
Independent Set Size Approximation in Graph Streams. CoRR abs/1702.08299 (2017) - 2016
- [j4]Yusuke Aoki, Bjarni V. Halldórsson
The minimum vulnerability problem on specific graph classes. J. Comb. Optim. 32(4): 1288-1304 (2016) - [j3]Christian Konrad, Adi Rosén:
Approximating Semi-matchings in Streaming and in Two-Party Communication. ACM Trans. Algorithms 12(3): 32:1-32:21 (2016) - [c14]Eden Chlamtác, Michael Dinitz
The Densest k-Subhypergraph Problem. APPROX-RANDOM 2016: 6:1-6:19 - [c13]Christoph Dürr, Christian Konrad, Marc P. Renault:
On the Power of Advice and Randomization for Online Bipartite Matching. ESA 2016: 37:1-37:16 - [c12]Christian Konrad:
Streaming Partitioning of Sequences and Trees. ICDT 2016: 13:1-13:18 - [c11]Marijke H. L. Bodlaender, Magnús M. Halldórsson
Brief Announcement: Local Independent Set Approximation. PODC 2016: 93-95 - [i8]Christoph Dürr, Zdenek Hanzálek, Christian Konrad, René Sitters, Óscar C. Vásquez, Gerhard J. Woeginger:
The triangle scheduling problem. CoRR abs/1602.04365 (2016) - [i7]Christoph Dürr, Christian Konrad, Marc P. Renault:
On the Power of Advice and Randomization for Online Bipartite Matching. CoRR abs/1602.07154 (2016) - [i6]Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca:
The Densest k-Subhypergraph Problem. CoRR abs/1605.04284 (2016) - 2015
- [c10]Magnús M. Halldórsson, Christian Konrad, Tigran Tonoyan:
Limitations of Current Wireless Scheduling Algorithms. ALGOSENSORS 2015: 71-84 - [c9]Rajiv Gandhi, Magnús M. Halldórsson
Radio Aggregation Scheduling. ALGOSENSORS 2015: 169-182 - [c8]Christian Konrad:
Maximum Matching in Turnstile Streams. ESA 2015: 840-852 - [c7]Magnús M. Halldórsson
Distributed Large Independent Sets in One Round on Bounded-Independence Graphs. DISC 2015: 559-572 - [i5]Christian Konrad:
Maximum Matching in Turnstile Streams. CoRR abs/1505.01460 (2015) - 2014
- [c6]Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson
The Minimum Vulnerability Problem on Graphs. COCOA 2014: 299-313 - [c5]Di Chen, Christian Konrad, Ke Yi, Wei Yu, Qin Zhang
Robust set reconciliation. SIGMOD Conference 2014: 135-146 - [c4]Magnús M. Halldórsson, Christian Konrad:
Distributed Algorithms for Coloring Interval Graphs. DISC 2014: 454-468 - [i4]Christian Konrad, László Kozma:
Streaming Algorithms for Partitioning Integer Sequences. CoRR abs/1404.1732 (2014) - 2013
- [b1]Christian Konrad:
Computations on Massive Data Sets : Streaming Algorithms and Two-party Communication. (Calculs sur des grosses données : algorithmes de streaming et communication entre deux joueurs). University of Paris-Sud, Orsay, France, 2013 - [j2]Christian Konrad, Frédéric Magniez:
Validating XML documents in the streaming model with external memory. ACM Trans. Database Syst. 38(4): 27 (2013) - [c3]Christian Konrad, Adi Rosén:
Approximating Semi-matchings in Streaming and in Two-Party Communication. ICALP (1) 2013: 637-649 - [i3]Christian Konrad, Adi Rosén:
Approximating Semi-Matchings in Streaming and in Two-Party Communication. CoRR abs/1304.6906 (2013) - 2012
- [c2]Christian Konrad, Frédéric Magniez, Claire Mathieu:
Maximum Matching in Semi-streaming with Few Passes. APPROX-RANDOM 2012: 231-242 - [c1]Christian Konrad, Frédéric Magniez:
Validating XML documents in the streaming model with external memory. ICDT 2012: 34-45 - 2011
- [j1]Christian Konrad:
Two-constraint domain decomposition with Space Filling Curves. Parallel Comput. 37(4-5): 203-216 (2011) - [i2]Christian Konrad, Frédéric Magniez, Claire Mathieu:
Maximum Matching in Semi-Streaming with Few Passes. CoRR abs/1112.0184 (2011) - 2010
- [i1]Christian Konrad, Frédéric Magniez:
The Streaming Complexity of Validating XML Documents. CoRR abs/1012.3311 (2010)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-08 01:29 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: