Conference papers
Fully Dynamic k-Clustering with Fast Update Time and Small Recourse. Sayan Bhattacharya, Martin Costa, Navin Garg, Silvio Lattanzi, Nikos Parotsidis. FOCS 2024
Practical Expander Decomposition. Lars Gottesbüren, Nikos Parotsidis, Maximilian Probst Gutenberg. ESA B 2024.
Dynamic Correlation Clustering in Sublinear Update Time. Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos Parotsidis. ICML 2024 (spotlight). (Full version available on arXiv)
Multi-Swap k-Means++. Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi, Nikos Parotsidis. NeurIPS 2023.
Fully Dynamic k-Clustering in Õ(k) Update Time. Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, Nikos Parotsidis. NeurIPS 2023.
Optimal Decremental Connectivity in Non-Sparse Graphs. Anders Aamand, Adam Karczmarz, Jakub Lacki, Nikos Parotsidis, Peter M. R. Rasmussen, Mikkel Thorup. ICALP 2023.
Faster Computation of 3-Edge-Connected Components in Digraphs. Loukas Georgiadis, Evangelos Kipouridis, Charis Papadopoulos, Nikos Parotsidis. SODA 2023.
Efficient and Stable Fully Dynamic Facility Location. Sayan Bhattacharya, Silvio Lattanzi, Nikos Parotsidis. NeurIPS 2022 (oral).
Near-Optimal Correlation Clustering with Privacy. Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski. NeurIPS 2022. (Full version available on arXiv.)
A Local Search Algorithm for Large Maximum Weight Independent Set Problems. Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe, Nikos Parotsidis, Mauricio G. C. Resende, Quico Spaen. ESA 2022. (Full version available on arXiv.)
Online and Consistent Correlation Clustering. Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos Parotsidis. ICML 2022 (short presentation).
Correlation Clustering in Constant Many Parallel Rounds. Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski. ICML 2021 (long presentation). (Full version available on arXiv.)
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis and Mikkel Thorup. FOCS 2021. (Full version available on arXiv.)
All-Pair LCA in DAGs: Breaking through the O(n^{2.5}) barrier. Fabrizio Grandoni, Giuseppe F. Italiano, Aleksander Łukasiewicz, Nikos Parotsidis, Przemysław Uznański. SODA 2021. (Full version available on arXiv.)
Planar Reachability Under Single Vertex or Edge Failures. Giuseppe F. Italiano, Adam Karczmarz, Nikos Parotsidis. SODA 2021.
An Experimental Study of Algorithms for Computing the Edge Connectivity of a Directed Graph. Loukas Georgiadis, Dionysios Kefalinos, Luigi Laura, Nikos Parotsidis. ALENEX 2021.
Collaborative Procrastination. Aris Anagnostopoulos, Aristides Gionis, Nikos Parotsidis. FUN 2021.
Fully Dynamic Consistent Facility Location. Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David Saulpic, Chris Schwiegelshohn. NeurIPS 2019.
Faster Algorithms for All-Pairs Bounded Min-Cuts. Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemysław Uznanski and Daniel Wolleb-Graf. ICALP A 2019. (Full version available on arXiv.)
Dynamic Algorithms for the Massively Parallel Computation Model. Giuseppe F. Italiano, Silvio Lattanzi, Vahab Mirrokni and Nikos Parotsidis. SPAA 2019. (Full version available on arXiv.)
Dominating Sets and Connected Dominating Sets in Dynamic Graphs. Niklas Hjuler, Giuseppe F. Italiano, Nikos Parotsidis and David Saulpic. STACS 2019. (Available on arXiv.)
Online Reciprocal Recommendation with Theoretical Performance Guarantees. Fabio Vitale, Nikos Parotsidis, Claudio Gentile. NeurIPS 2018. (Full version available on arXiv.)
Incremental Strong Connectivity and 2-Connectivity in Directed Graphs. Loukas Georgiadis, Giuseppe F. Italiano and Nikos Parotsidis. LATIN 2018. (Full version available on arXiv.)
Computing 2-Connected Components and Maximal 2-Connected Subgraphs in Digraphs: An Experimental Study. Loukas Georgiadis, Giuseppe F. Italiano, Aikaterini Karanasiou, Nikos Parotsidis and Nilakantha Paudel. ALENEX 2018.
Balancing Information Exposure in Social Networks. Kiran Garimella, Aristides Gionis, Nikos Parotsidis, Nikolaj Tatti. NIPS 2017. (Full version available on arXiv.)
All-Pairs 2-reachability in O˜(n^ω) Time. Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis, and Przemysław Uznański. ICALP A 2017. (Full version available on arXiv.)
Decremental Data Structures for Connectivity and Dominators in Directed Graphs. Loukas Georgiadis, Thomas Dueholm Hansen, Giuseppe F. Italiano, Sebastian Krinninger, and Nikos Parotsidis. ICALP A 2017. (Full version available on arXiv.)
What's Inside a Bow-Tie: Analyzing the Core of the Web and of Social Networks. Giuseppe F. Italiano, Nikos Parotsidis, and Eugenia Perekhodko. ICISDM 2017.
Strong Connectivity in Directed Graphs under Failures, with Application. Loukas Georgiadis, Giuseppe F. Italiano and Nikos Parotsidis. SODA 2017. (Full version available on arXiv.)
Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs. Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer and Nikos Parotsidis. SODA 2017.
Decremental Single-Source Reachability and Strongly Connected Components in O~(m sqrt(n)) Total Update Time. Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Łącki, and Nikos Parotsidis. FOCS 2016.
Incremental 2-Edge-Connectivity in Directed Graphs. Loukas Georgiadis, Giuseppe F. Italiano, and Nikos Parotsidis. ICALP A 2016. (Full version available on arXiv.)
Centrality-aware Link Recommendations. Nikos Parotsidis, Evaggelia Pitoura, and Panayiotis Tsaparas. WSDM 2016.
Sparse Subgraphs for Strong Connectivity and 2-Connectivity in Directed Graphs. Loukas Georgiadis, Giuseppe F. Italiano, Aikaterini Karanasiou, Charis Papadopoulos, and Nikos Parotsidis. SEA 2016.
Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs. ESA B 2015. Loukas Georgiadis, Giuseppe F. Italiano, Charis Papadopoulos, and Nikos Parotsidis. (Full version available on arXiv.)
Selecting shortcuts for a smaller world. Nikos Parotsidis, Evaggelia Pitoura, and Panayiotis Tsaparas. SDM 2015.
2-Vertex Connectivity in Directed Graphs. Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Nikos Parotsidis. ICALP A 2015 (Invited to the special issue of "Information and Computation" on ICALP 2015). (Full version available on arXiv.)
2-Edge Connectivity in Directed Graphs. Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Nikos Parotsidis. SODA 2015. (Full version appeared in TALG 2016.)
2-Connectivity in Directed Graphs: An experimental Study. William Di Luigi, Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Nikos Parotsidis. ALENEX 2015.
Loop Nesting Forests, Dominators, and Applications. Loukas Georgiadis, Luigi Laura, Nikos Parotsidis and Robert E. Tarjan. SEA 2014.
Dominator Tree Certification and Independent Spanning Trees: An Experimental Study. Loukas Georgiadis, Luigi Laura, Nikos Parotsidis and Robert E. Tarjan. SEA 2013.
Dominators in Directed Graphs: A Survey of Recent Results, Applications, and Open Problems. Loukas Georgiadis and Nikos Parotsidis. ISCIM 2013.
Journal papers
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup. Journal of the ACM, 2024.
New Instances for Maximum Weight Independent Set From a Vehicle Routing Application. Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe, Nikos Parotsidis, Mauricio G. C. Resende, Quico Spaen. Open Research Forum, 2021.
Strong Connectivity in Directed Graphs under Failures, with Applications. Loukas Georgiadis, Giuseppe F. Italiano and Nikos Parotsidis. SICOMP, 2020.
2-vertex connectivity in directed graphs. Information and Computation. Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Nikos Parotsidis. (Special issue of ICALP 2015)
Sparse certificates for 2-connectivity in directed graphs. Loukas Georgiadis, Giuseppe F. Italiano, Aikaterini Karanasiou, Charis Papadopoulos, and Nikos Parotsidis. Theoretical Computer Science, 2017.
2-Edge Connectivity in Directed Graphs. Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Nikos Parotsidis. ACM Transactions on Algorithms, 2016.
Design and implementation of a social networking platform for cloud deployment specialists. Kostas Magoutis, Christos Papoulas, Antonis Papaioannou, Flora Karniavoura, Dimitrios-Georgios Akestoridis, Nikos Parotsidis, Maria Korozi, Asterios Leonidis, Stavroula Ntoa, Constantine Stephanidis. Journal of Internet Services and Applications 2015.
Theses
PhD thesis: Connectivity in Directed Graphs: Static and Dynamic, University of Rome Tor Vergata, 2019.
Master thesis: 2-Connectivity in Directed Graphs, University of Ioannina, 2015.
Bachelor thesis: Κυριαρχία και Συνεκτικότητα σε Στατικά και Δυναμικά Γραφήματα, University of Ioannina, 2013. (In Greek, as you can guess from the title :-))
Other
[Survey] 2-Connectivity in Directed Graphs. Loukas Georgiadis, Giuseppe F. Italiano, and Nikos Parotsidis. Giuseppe F. Italiano's invited talk at ESA 2016.