Department Mathematik
print


Navigationspfad


Inhaltsbereich

Publications of Konstantinos Panagiotou


Books


  • M. Krivelevich, K. Panagiotou, M. Penrose and C. McDiarmid. Random Graphs, Geometry and Asymptotic Structure. Edited by N. Fountoulakis and D. Hefetz, Cambridge University Press, London Mathematical Society Student Texts, 2016.

  • Papers in Journals - Papers marked with (*) have also appeared as an extended abstract in conference proceedings.
    • Scaling Limits of Random Polya Trees (with B. Stufler)
      Accepted: Probability Theory and Related Fields, 2016.
    • The Asymptotic k-SAT Threshold (with A. Coja-Oghlan)
      In: Advances in Mathematics, 228, p. 985-1068, 2016.
    • (*) Asynchronous Rumor Spreading on Random Graphs (with L. Speidel)
      Accepted: Algorithmica, 2016.
    • (*) Efficient Sampling Methods for Discrete Distributions (with K. Bringmann)
      Accepted: Algorithmica, 2016.
    • (*) Scaling Limits for Random Graphs from Subcritical Classes (with B. Stufler and K. Weller)
      In: Annals of Probability, 44(5), p. 3291-3334, 2016.
    • Connectivity Thresholds for Bounded-Size Rules (with H. Einarsson, J. Lengler, F. Mousset and A. Steger)
      In: Annals of Applied Probability, 26(5), p. 3206-3250, 2016.
    • (*) The Multiple-orientability Thresholds for Random Hypergraphs (with N. Fountoulakis and M. Khosla)
      In: Combinatorics, Probability and Computing, 25, p. 870-908, 2016.
    • Randomized Rumor Spreading: the Effect of the Network Topology (with X. Perez-Gimenez, T. Sauerwald and H. Sun)
      In: Combinatorics, Probability and Computing, 24(2), p. 457-479, 2015.
    • Maximizing the Minimum Load for Random Processing Times (with S. Gerke, A. Steger and J. Schwartz)
      In: Transactions on Algorithms, 11(3), Article No. 17, 2015.
    • (*) Faster Rumor Spreading With Multiple Calls (with A. Pourmiri and T. Sauerwald)
      In: Electronic Journal of Combinatorics, 22(1), Article No. P1.23, 2015.
    • Coloring d-Embeddable k-Uniform Hypergraphs (with C. G. Heise, O. Pikhurko and A. Taraz)
      In: Discrete and Computational Geometry, 52(4), p. 663-679, 2014.
    • (*) The Maximum Degree of Random Planar Graphs (with M. Drmota, O. Gimenez, M. Noy and A. Steger)
      In: Proceedings of the London Mathematical Society, 109(3), 892-920, 2014.
    • (*) Multi-target ray searching problems (with S. Angelopoulos and A. Lopez-Ortiz)
      In: Theoretical Computer Science 540, p. 2-12, 2014.
    • On the Connectivity Threshold of Achlioptas Processes (with M. Kang)
      In: Journal of Combinatorics 5(3), p. 291-304, 2014.
    • On the Insertion Time of Cuckoo Hashing (with N. Fountoulakis and A. Steger)
      In: SIAM Journal on Computing, 46(2), p. 2156-2181, 2013.
    • (*) A Central Limit Theorem for the Number of Degree-k Vertices in Random Maps (with M. Drmota)
      In: Algorithmica, 66(4), p. 741-761, 2013.
    • (*) Rumor Spreading on Random Regular Graphs and Expanders (with N. Fountoulakis)
      In: Random Structures and Algorithms, 43(2), p. 201-220, 2013.
    • On the Connectivity of Random Graphs from Addable Classes (with M. Kang)
      In: Journal of Combinatorial Theory, Series B, 103(2), p. 306-312, 2013.
    • (*) Explosive Percolation in Erdös-Renyi-Like Processes (with R. Spöhel, A. Steger and H. Thomas)
      In: Combinatorics, Probability and Computing, 22(1), p. 133-145, 2013.
    • (*) Extremal Subgraphs of Random Graphs (with G. Brightwell and A. Steger)
      In: Random Structures and Algorithms, 41(2), p. 147-178, 2012.
    • (*) Tight Load Thresholds for Cuckoo Hashing (with N. Fountoulakis)
      In: Random Structures and Algorithms, 41(3), p. 306-333, 2012.
    • (*) Vertices of Degree k in Random Unlabeled Trees (with M. Sinha)
      In: Journal of Graph Theory, 69(2), p. 114-130, 2012.
    • 3-connected Cores in Random Planar Graphs (with N. Fountoulakis)
      In: Combinatorics, Probability and Computing, 20(3), p. 381-412, 2011.
    • (*) On Properties of Random Dissections and Triangulations (with N. Bernasconi and A. Steger)
      In: Combinatorica, 30(6), p. 627-654, 2010.
    • (*) Maximal Biconnected Subgraphs of Random Planar Graphs (with A. Steger)
      In: Transactions on Algorithms, 6(2), p. 1-21, 2010. Special issue devoted to SODA '09 best papers.
    • The Degree Sequence of Random Graphs from Subcritical Classes (with N. Bernasconi and A. Steger)
      In: Combinatorics, Probability and Computing, Volume 18, Special Issue 05, p. 647-681, 2009.
    • Tight Bounds for Quasirandom Rumor Spreading (with S. Angelopoulos, B. Doerr and A. Huber)
      In: Electronic Journal of Combinatorics, 16(1), R102, 2009.
    • (*) Optimal Algorithms for k-Search with Application in Option Pricing (with J. Lorenz and A. Steger)
      In: Algorithmica, 55(2), p. 311-328, 2009. Special issue devoted to ESA'07 best papers.
    • A Note on the Chromatic Number of a Dense Random Graph (with A. Steger)
      In: Discrete Mathematics, 309(10), p. 3420-3423, 2009.
    • (*) On the Chromatic Number of Random Graphs (with A. Coja-Oghlan and A. Steger)
      In: Journal of Combinatorial Theory, Series B, 98, p. 980-993, 2008.

    Papers in Conference Proceedings

    • Scaling Limits for Random Graphs from Subcritical Classes (with B. Stufler and K. Weller)
      In: 27th International Conference on Formal Power Series and Algebraic Combinatorics, DMTCS proc. FPSAC '15, p. 745-756, 2015.
    • Internal DLA: Efficient Simulation of a Physical Growth Model (with K. Bringmann, F. Kuhn, U. Peter and H. Thomas)
      In: Proceedings of the 41st Int. Colloquium on Automata, Languages and Programming (ICALP '14), p. 247-258, 2014.
    • Going After the k-SAT Threshold (with A. Coja-Oghlan)
      In: Proceedings of the 45th ACM Symposium on Theory of Computing (STOC'13), p. 705-714, 2013.
    • Asynchronous Rumor Spreading on Random Graphs (with L. Speidel)
      Accepted: Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC '13).
    • Faster Rumor Spreading with Multiple Calls (with A. Pourimi und T. Sauerwald)
      Accepted: Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC '13).
    • Efficient Sampling Methods for Discrete Distributions (with K. Bringmann)
      In: Proceedings of the 39th Int. Colloquium on Automata, Languages and Programming (ICALP '12), p. 133-144, 2012.
    • Random Hyperbolic Graphs: Degree Sequence and Clustering (with L. Gugelmann and U. Peter)
      In: Proceedings of the 39th Int. Colloquium on Automata, Languages and Programming (ICALP '12), p. 573-585.
    • Catching the k-NAESAT Threshold (with A. Coja-Oghlan)
      In: Proceedings of the 44th ACM Symposium on Theory of Computing (STOC'12), p. 899-908.
    • A Probabilistic Analysis of Christofides' Algorithm (with M. Bläser and R. Rao B. V.)
      In: Proceedings of the 13th Scandinavian Symposium on Algorithm Theory (SWAT '12), p. 225-236.
    • Ultra-fast Rumor Spreading in Models of Real-world Networks (with N. Fountoulakis and T. Sauerwald)
      In: Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA '12), p. 1642-1660.
    • The Maximum Degree of Random Planar Graphs (with M. Drmota, O. Gimenez, M. Noy and A. Steger)
      In: Proceedings of the 23rd ACM-SIAM Symp. on Discrete Algorithms (SODA '12), p. 281-287.
    • A Central Limit Theorem for the Number of Degree-k Vertices in Random Maps (with M. Drmota)
      In: Proceedings of Analytic Algorithmics and Combinatorics (ANALCO12), p. 9-17.
    • Approximate Counting of Cycles in Streams (with M. Madhusudan, K. Mehlhorn and H. Sun)
      In: Proc. of the 19th European Symp. on Algorithms (ESA '11), p. 677-688.
    • The Multiple-orientability Thresholds for Random Hypergraphs (with N. Fountoulakis and M. Khosla)
      In: Proc. of the 22nd ACM-SIAM Symp. on Discrete Algorithms (SODA '11), p. 1222-1236.
    • On the Degree Distribution of Random Planar Graphs (with A. Steger)
      In: Proceedings of the 22nd ACM-SIAM Symp. on Discrete Algorithms (SODA '11), p. 1198-1210.
    • Multi-Target Ray Searching Problems (with S. Angelopoulos and A. Lopez-Ortiz)
      In: Algorithms and Data Structures Symp. (WADS '11), Lecture Notes in Computer Science, Volume 6844/2011, p. 37-48.
    • Rumor Spreading on Random Regular Graphs and Expanders (with N. Fountoulakis)
      In: 14th International Workshop on Randomization and Computation (RANDOM '10), p. 560-573.
    • Orientability of Random Hypergraphs and the Power of Multiple Choices (with N. Fountoulakis)
      In: 37th International Colloquium on Automata, Languages and Programming (ICALP '10), p. 348-359.
    • Reliable Broadcasting in Random Networks and the Effect of Density (with N. Fountoulakis and A. Huber)
      In: 29th Conference on Computer Communications (IEEE INFOCOM '10), p. 2552-2560.
    • Vertices of Degree k in Random Maps (with D. Johannsen)
      In: Proc. of the 21th ACM-SIAM Symp. on Discrete Algorithms (SODA '10), p. 1436-1447.
    • Synchrony and Asynchrony in Neural Networks (with F. Kuhn, J. Spencer, A. Steger)
      In: Proc. of the 21th ACM-SIAM Symp. on Discrete Algorithms (SODA '10), p. 949-964.
    • Maximal Biconnected Subgraphs of Random Planar Graphs (with A. Steger)
      In: Proc. of the 20th ACM-SIAM Symp. on Discrete Algorithms (SODA '09), p. 432-440.
    • Blocks in Constrained Random Graphs with Fixed Average Degree
      In: 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC '09), DMTCS Proc. AK, 733-744.
    • On Properties of Random Dissections and Triangulations (with N. Bernasconi and A. Steger)
      In: Proc. of the 19th ACM-SIAM Symp. on Discrete Algorithms (SODA '08), p. 132-141.
    • On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs (with N. Bernasconi and A. Steger)
      In: Proc. of the 12th International Workshop on Randomized Techniques in Computation (RANDOM'08), p. 303-316.
    • On Extremal Subgraphs of Random Graphs (with G. Brightwell and A. Steger)
      In: Proc. of the 18th ACM-SIAM Symp. on Discrete Algorithms (SODA '07), p. 477-485.
    • On the Chromatic Number of Random Graphs (with A. Coja-Oghlan and A. Steger)
      In: 34th International Colloquium on Automata, Languages and Programming (ICALP '07), p. 777-788.
    • Optimal Algorithms for k-Search with Application in Option Pricing (with J. Lorenz and A. Steger)
      In: 15th European Symp. on Algorithms (ESA '07), p. 275-286.
    • Properties of Random Graphs via Boltzmann Samplers (with A. Weissl)
      In: 2007 International Conference on Analysis of Algorithms (AofA'07), DMTCS Proc. AH, p. 159-168.
    • On Adequate Performance Measures for Paging (with A. Souza)
      In: Proc. of the 38th ACM Symp. on Theory of Computing (STOC'06), p. 487-496.

    Other Contributions (Refereed)

    • Discontinuous bootstrap percolation in power-law random graphs (with H. Amini and N. Fountoulakis)
      Accepted for publication in: European Conference on Combinatorics, Graph Theory and Applications (EuroComb '13).
    • Coloring d-Embeddable k-Uniform Hypergraphs (with C. G. Heise, O. Pikhurko and A. Taraz)
      Accepted for publication in: European Conference on Combinatorics, Graph Theory and Applications (EuroComb '13).
    • Explosive Percolation in Erdös-Renyi-Like Processes (with R. Spöhel, A. Steger and H. Thomas)
      In: European Conference on Combinatorics, Graph Theory and Applications (EuroComb '11), Electronic Notes in Discrete Mathematics 38, p. 699-704.
    • Boltzmann Generation for Regular Languages with Shuffle (with A. Darasse, O. Roussel and M. Soria)
      In: Random Generation of Combinatorial Structures (GASCom '10), 2010.
      Click here for the electronic edition.
    • The Speed of Broadcasting in Random Networks: Density Does Not Matter (with N. Fountoulakis and A. Huber)
      Brief Announcement in: 23rd International Symp. on Distributed Computing (DISC '09), Lecture Notes in Computer Science 5805, Springer, 2009, p. 529-530.
    • Vertices of Degree k in Random Unlabeled Trees (with M. Sinha)
      In: European Conference on Combinatorics, Graph Theory and Applications (EuroComb '09), Electronic Notes in Discrete Mathematics, Volume 34, p. 41-45.
    pdf