Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Johannes Lengler, Anders Martinsson, Kalina Petrova, Patrick Schnider, Raphael Steiner, Simon Weber, and Emo Welzl. On Connectivity in Random Graph Models with Limited Dependencies. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lengler_et_al:LIPIcs.APPROX/RANDOM.2023.30, author = {Lengler, Johannes and Martinsson, Anders and Petrova, Kalina and Schnider, Patrick and Steiner, Raphael and Weber, Simon and Welzl, Emo}, title = {{On Connectivity in Random Graph Models with Limited Dependencies}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {30:1--30:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.30}, URN = {urn:nbn:de:0030-drops-188556}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.30}, annote = {Keywords: Random Graphs, Independence, Dependency, Connectivity, Threshold, Probabilistic Method} }
Published in: Dagstuhl Reports, Volume 12, Issue 2 (2022)
Anne Auger, Carlos M. Fonseca, Tobias Friedrich, Johannes Lengler, and Armand Gissler. Theory of Randomized Optimization Heuristics (Dagstuhl Seminar 22081). In Dagstuhl Reports, Volume 12, Issue 2, pp. 87-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Article{auger_et_al:DagRep.12.2.87, author = {Auger, Anne and Fonseca, Carlos M. and Friedrich, Tobias and Lengler, Johannes and Gissler, Armand}, title = {{Theory of Randomized Optimization Heuristics (Dagstuhl Seminar 22081)}}, pages = {87--102}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {12}, number = {2}, editor = {Auger, Anne and Fonseca, Carlos M. and Friedrich, Tobias and Lengler, Johannes and Gissler, Armand}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.2.87}, URN = {urn:nbn:de:0030-drops-169325}, doi = {10.4230/DagRep.12.2.87}, annote = {Keywords: black-box optimization, derivative-free optimization, evolutionary and genetic algorithms, randomized search algorithms, stochastic gradient descent, theoretical computer science} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Marc Roth, Johannes Schmitt, and Philip Wellnitz. Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 108:1-108:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{roth_et_al:LIPIcs.ICALP.2021.108, author = {Roth, Marc and Schmitt, Johannes and Wellnitz, Philip}, title = {{Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {108:1--108:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.108}, URN = {urn:nbn:de:0030-drops-141778}, doi = {10.4230/LIPIcs.ICALP.2021.108}, annote = {Keywords: Counting complexity, parameterized complexity, Tutte polynomial} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Daniel Bertschinger, Johannes Lengler, Anders Martinsson, Robert Meier, Angelika Steger, Miloš Trujić, and Emo Welzl. An Optimal Decentralized (Δ + 1)-Coloring Algorithm. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bertschinger_et_al:LIPIcs.ESA.2020.17, author = {Bertschinger, Daniel and Lengler, Johannes and Martinsson, Anders and Meier, Robert and Steger, Angelika and Truji\'{c}, Milo\v{s} and Welzl, Emo}, title = {{An Optimal Decentralized (\Delta + 1)-Coloring Algorithm}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {17:1--17:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.17}, URN = {urn:nbn:de:0030-drops-128837}, doi = {10.4230/LIPIcs.ESA.2020.17}, annote = {Keywords: Decentralized Algorithm, Distributed Computing, Graph Coloring, Randomized Algorithms} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Charlotte Knierim, Johannes Lengler, Pascal Pfister, Ulysse Schaller, and Angelika Steger. The Maximum Label Propagation Algorithm on Sparse Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{knierim_et_al:LIPIcs.APPROX-RANDOM.2019.58, author = {Knierim, Charlotte and Lengler, Johannes and Pfister, Pascal and Schaller, Ulysse and Steger, Angelika}, title = {{The Maximum Label Propagation Algorithm on Sparse Random Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {58:1--58:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.58}, URN = {urn:nbn:de:0030-drops-112731}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.58}, annote = {Keywords: random graphs, distributed algorithms, label propagation algorithms, consensus, community detection} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Karl Bringmann, Ralph Keusch, and Johannes Lengler. Sampling Geometric Inhomogeneous Random Graphs in Linear Time. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bringmann_et_al:LIPIcs.ESA.2017.20, author = {Bringmann, Karl and Keusch, Ralph and Lengler, Johannes}, title = {{Sampling Geometric Inhomogeneous Random Graphs in Linear Time}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {20:1--20: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.20}, URN = {urn:nbn:de:0030-drops-78396}, doi = {10.4230/LIPIcs.ESA.2017.20}, annote = {Keywords: real-world networks, random graph models, sampling algorithms, compression algorithms, hyperbolic random graphs} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Christoph Koch and Johannes Lengler. Bootstrap Percolation on Geometric Inhomogeneous Random Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 147:1-147:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{koch_et_al:LIPIcs.ICALP.2016.147, author = {Koch, Christoph and Lengler, Johannes}, title = {{Bootstrap Percolation on Geometric Inhomogeneous Random Graphs}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {147:1--147:15}, 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.147}, URN = {urn:nbn:de:0030-drops-62918}, doi = {10.4230/LIPIcs.ICALP.2016.147}, annote = {Keywords: Geometric inhomogeneous random graphs, scale-free network, bootstrap percolation, localised infection process, metastability threshold} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Bernd Gärtner, Johannes Lengler, and May Szedlák. Random Sampling with Removal. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{gartner_et_al:LIPIcs.SoCG.2016.40, author = {G\"{a}rtner, Bernd and Lengler, Johannes and Szedl\'{a}k, May}, title = {{Random Sampling with Removal}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {40:1--40:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.40}, URN = {urn:nbn:de:0030-drops-59328}, doi = {10.4230/LIPIcs.SoCG.2016.40}, annote = {Keywords: LP-type problem, violator space, random sampling, sampling with removal} }
Feedback for Dagstuhl Publishing