Staff profile

George Mertzios received his Degree ("Diplom") in Mathematics with minor Computer Science (1.2, "Excellent") from the Technische Universitaet Muenchen in 2005, and his PhD in Computer Science from the RWTH Aachen University, Germany, in 2009. During 2010-11 he worked as a postdoctorate researcher at the Department of Computer Science in Technion - Israel Institute of Technology and at the Caesarea Rothschild Institute for Computer Science in the University of Haifa, Israel. From June to July 2012 he was an Invited Assistant Professor at the Laboratoire Bordelais de Recherche en Informatique (LaBRI) of University of Bordeaux/CNRS, France. From 2011 to 2015 he was a Lecturer in Computer Science at Durham University. From 2015 to 2017 he was a Senior Lecturer, and since 2017 he is an Associate Professor in Computer Science at Durham. His research areas include Efficient Graph Algorithms, Temporal (Dynamically Changing) Graphs, Computational and Parameterized Complexity, Evolutionary Graph Theory, and Algorithmic Game Theory.

Email

george (dot) mertzios (at) durham.ac.uk

For more details refer to my home page:
https://mertzios.net/

• Efficient Algorithms & Computational Complexity
• Foundations of Networks & Algorithmic Graph Theory
• Evolutionary Graph Theory
• Parameterized Complexity
• Combinatorial Optimization

• ACiD: Algorithms and Complexity

• 2013: Principal Investigator (PI) on the EPSRC-funded grant "Algorithmic Aspects of Intersection Graph Models". Total Grant Value: £121000 (EPSRC contribution: £96800). More details at: http://gow.epsrc.ac.uk/NGBOViewGrant.aspx?GrantRef=EP/K022660/1

Chapter in book

• Fluschnik, T., Mertzios, G.B. & Nichterlein, A. (2018). Kernelization Lower Bounds for Finding Constant-Size Subgraphs. In Sailing Routes in the World of Computation. 14th Conference on Computability in Europe, CiE 2018, Kiel, Germany, July 30 – August 3, 2018, Proceedings. Manea, F., Miller, R. & Nowotka, D. Cham: Springer. 10936: 183-193.
• Mertzios, G.B. (2015). Multitolerance Graphs. In Encyclopedia of Algorithms. Kao, Ming-Yang Springer.
• Mertzios, G.B. (2015). Approximating Fixation Probabilities in the Generalized Moran Process. In Encyclopedia of Algorithms. Kao, Ming-Yang Springer. 1-6.
• Mertzios, G.B., Nikoletseas, S., Raptopoulos, C. & Spirakis, P.G. (2014). Determining Majority in Networks with Local Interactions and Very Small Local Memory. In Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. Esparza, Javier, Fraigniaud, Pierre, Husfeldt, Thore & Koutsoupias, Elias Berlin, Heidelberg: Springer. 8572: 871-882.
• Díaz, J. & Mertzios, G.B. (2014). Minimum Bisection Is NP-hard on Unit Disk Graphs. In Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II. Csuhaj-Varjú, Erzsébet Dietzfelbinger, Martin & Ésik, Zoltán Berlin, Heidelberg: Springer. 8635: 251-262.
• Felsner, S. Knauer, K., Mertzios, G.B. & Ueckerdt, T. (2014). Intersection Graphs of L-Shapes and Segments in the Plane. In Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II. Csuhaj-Varjú, Erzsébet, Dietzfelbinger, Martin & Ésik, Zoltán Berlin, Heidelberg: Springer. 8635: 299-310.
• Mertzios, G.B. & Spirakis, P.G. (2013). Strong Bounds for Evolution in Networks. In Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II. Fomin, Fedor V., Freivalds, Rūsiņš, Kwiatkowska, Marta & Peleg, David Berlin, Heidelberg: Springer. 7966: 669-680.
• Felsner, S., Mertzios, G.B. & Mustata, I. (2013). On the Recognition of Four-Directional Orthogonal Ray Graphs. In Mathematical Foundations of Computer Science 2013: 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings. Chatterjee, Krishnendu & Sgall, Jirí Berlin, Heidelberg: Springer. 8087: 373-384.
• Mertzios, G.B. (2013). The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial. In Algorithms – ESA 2013: 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings. Bodlaender, Hans L. & Italiano, Giuseppe F. Berlin, Heidelberg: Springer. 8125: 719-730.
• Mertzios, G.B. & Spirakis, P.G. (2013). Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs. In SOFSEM 2013: Theory and Practice of Computer Science: 39th International Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 26-31, 2013. Proceedings. Boas, Peter van Emde, Groen, Frans C. A., Italiano, Giuseppe F., Nawrocki, Jerzy & Sack, Harald Berlin, Heidelberg: Springer. 7741: 332-343.
• Mertzios, G.B., Michail, O., Chatzigiannakis, I. & Spirakis, P.G. (2013). Temporal Network Optimization Subject to Connectivity Constraints. In Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II. Fomin, Fedor V., Freivalds, Rūsiņš, Kwiatkowska, Marta & Peleg, David Berlin, Heidelberg: Springer. 7966: 657-668.

Conference Paper

• Friedetzky, T., Kutner, D., Mertzios, G.B., Stewart, I.A. & Trehan, A. (2023), Payment scheduling in the Interval Debt Model, Lecture Notes in Computer Science 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023). Novy Smokovec, Slovakia, Springer.
• Klobas, N., Mertzios, G.B., Molter, H. & Spirakis, P.G. (2022), The complexity of computing optimum labelings for temporal connectivity, Leibniz International Proceedings in Informatics (LIPIcs) 241: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Vienna, Austria, Dagstuhl, 62:1-62:15.
• Hamm, T., Klobas, N., Mertzios, G.B. & Spirakis, P.G. (2022), The complexity of temporal vertex cover in small-degree graphs, 36: 36th AAAI Conference on Artificial Intelligence (AAAI 2022). Vancouver, BC, Association for the Advancement of Artificial Intelligence, 10193-10201.
• Mertzios, G.B., Michail, O., Skretas, G., Spirakis, P.G. & Theofilatos, M. (2022), The complexity of growing a graph, Lecture Notes in Computer Science 18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS). Potsdam, Germany, Springer.
• Mertzios, G.B., Molter, H., Renken, M., Spirakis, P.G. & Zschoche, P. (2021), The complexity of transitively orienting temporal graphs, in Bonchi, F. & Puglisi, S.J. eds, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Tallinn, Estonia, Dagstuhl, 75:1-75:18.
• Heeger, K., Hermelin, D., Mertzios, G.B., Molter, H., Niedermeier, R. & Shabtay, D. (2021), Equitable scheduling on a single machine, 35: 35th AAAI Conference on Artificial Intelligence (AAAI). Vancouver, Canada, Association for the Advancement of Artificial Intelligence.
• Klobas, N., Mertzios, G.B., Molter, H., Niedermeier, R. & Zschoche, P. (2021), Interference-free walks in time: temporally disjoint paths, 30th International Joint Conference on Artificial Intelligence (IJCAI-21). Montreal, 4090-4096.
• Deligkas, A., Mertzios, G.B., Spirakis, P.G. & Zamaraev, V. (2020), Exact and approximate algorithms for computing a second Hamiltonian cycle, in Esparza, Javier & Král, Daniel eds, Leibniz International Proceedings in Informatics (LIPIcs) 170: MFCS 2020 (International Symposium on Mathematical Foundations of Computer Science). Prague, Czech Republic, Dagstuhl Publishing, Dagstuhl, Germany, 21:1–21:13.
• Mertzios, G.B., Molter, H., Niedermeier, R., Zamaraev, V. & Zschoche, P. (2020), Computing maximum matchings in temporal graphs, in Paul, Christophe & Blaser, Markus eds, Leibniz International Proceedings in Informatics (LIPIcs) 154: 37th International Symposium on Theoretical Aspects of Computer Science (STACS). Montpellier, France, Dagstuhl Publishing, Dagstuhl, Germany, 27:1--27:14.
• Enright, J., Meeks, K., Mertzios, G.B. & Zamaraev, V. (2019), Deleting edges to restrict the size of an epidemic in temporal networks, in Rossmanith, Peter Heggernes, Pinar & Katoen, Joost-Pieter eds, LIPIcs (Leibniz International Proceedings in Informatics) 138: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS). Aachen, Germany, Schloss Dagstuhl, Saarbrücken/Wadern, 57:1--57:15.
• Mertzios, G.B., Molter, H. & Zamaraev, V. (2019), Sliding Window Temporal Graph Coloring, 33: 33rd AAAI Conference on Artificial Intelligence (AAAI 2019). Honolulu, Hawaii, USA, AAAI Press, Palo Alto, California, 7667-7674.
• Akrida, E.C., Mertzios, G.B. & Spirakis, P.G. (2019), The temporal explorer who returns to the base, in Heggernes P. eds, Lecture notes in computer science 11485: 11th International Conference on Algorithms and Complexity (CIAC 2019). Rome, Italy, Springer, Cham, 13-24.
• Akrida, Eleni C. Mertzios, George B., Nikoletseas, Sotiris, Christoforos, Raptopoulos,, Spirakis, Paul G. & Zamaraev, Viktor (2019), How fast can we reach a target vertex in stochastic temporal graphs?, in Baier, Christel Chatzigiannakis, Ioannis Flocchini, Paola & Leonardi, Stefano eds, Leibniz International Proceedings inInformatics (LIPIcs) 132: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Patras, Greece, Dagstuhl Publishing, Dagstuhl, Germany, 131:1--131:14.
• Akrida, E.C., Mertzios, G.B., Spirakis, P.G. & Zamaraev, V. (2018), Temporal vertex cover with a sliding time window, in Chatzigiannakis, Ioannis, Kaklamanis, Christos, Marx, Dániel & Sannella, Don eds, Leibniz International Proceedings in Informatics (LIPICS) 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Prague, Czech Republic, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl.
• Mertzios, G.B., Nichterlein, A. & Niedermeier, R. (2017), The Power of Linear-Time Data Reduction for Maximum Matching, in Larsen, Kim G., Bodlaender, Hans L. & Raskin, Jean-Francois eds, LIPIcs–Leibniz International Proceedings in Informatics 83: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS). Aalborg, Denmark, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 46:1-46:14.
• Fluschnik, T., Komusiewicz, C., Mertzios, G.B., Nichterlein, A., Niedermeier, R. & Talmon, N. (2017), When can graph hyperbolicity be computed in linear time?, in Ellen, Faith, Kolokolova, Antonina & Sack, Jörg-Rüdiger eds, Lecture Notes in Computer Science, volume 10389 Algorithms and Data Structures Symposium (WADS). St. John’s, NL, Springer, Cham, 397-408.
• Deligkas, A., Mertzios, G.B. & Spirakis, P.G. (2017), The computational complexity of weighted greedy matching, 31st AAAI Conference on Artificial Intelligence (AAAI-17). San Francisco, California, USA, AAAI Press, Menlo Park, 466-472.
• Bevern, R.V., Fluschnik, T., Mertzios, G.B., Molter, H., Sorge, M. & Suchý, O. (2017), Finding secluded places of special interest in graphs, in Guo, Jiong & Hermelin, Danny eds, Leibniz International Proceedings in Informatics (LIPIcs) 63: 11th International Symposium on Parameterized and Exact Computation (IPEC). Aarhus, Denmark, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 5:1-5:16.
• Deligkas, A., Mertzios, G.B. & Spirakis, P.G. (2017), Binary search in graphs revisited, in Larsen, Kim G., Bodlaender, Hans L. & Raskin, Jean-Francois eds, LIPIcs–Leibniz International Proceedings in Informatics 83: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS). Aalborg, Denmark, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 20.
• Foucaud, F., Mertzios, G.B., Naserasr, R., Parreau, A. & Valicov, P. (2016), Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs, in Mayr, Ernst W. eds, Lecture notes in computer science, 9224 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG). Munich, Germany, Springer, Berlin, 456-471.
• Mertzios, G.B., Nikoletseas, S.E., Raptopoulos, C.L. & Spirakis, P.G. (2016), Stably computing order statistics with arithmetic population protocols, in Faliszewski, P., Muscholl, A. & Niedermeier, R. eds, Leibniz International Proceedings in Informatics 58: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Krakow, Poland, Schloss Dagstuhl - Leibniz Center for Informatics, Dagstuhl, 68:1-68:14.
• Golovach, P.A. & Mertzios, G.B. (2016), Graph editing to a given degree sequence, in Kulikov, A.S. & Woeginger, G. eds, Lecture Notes in Computer Science, 9691 11th International Computer Science Symposium in Russia. St. Petersburg, Russia, Springer, Cham, Switzerland, 177-191.
• Akrida, E.C., Gasieniec, L., Mertzios, G.B. & Spirakis, P.G. (2016), On temporally connected graphs of small cost, 13th Workshop on Approximation and Online Algorithms (WAOA). Patras, Greece, Springer, Cham, 84-96.
• Giannopoulou, A.C. & Mertzios, G.B. (2015), New geometric representations and domination problems on tolerance and multitolerance graphs, in Mayr, Ernst W. & Ollinger, Nicolas eds, Leibniz International Proceedings in Informatics (LIPIcs) 32nd Symposium on Theoretical Aspects of Computer Science (STACS). Munich, Germany, Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 354-366.
• Giannopoulou, A.C., Mertzios, G.B. & Niedermeier, R. (2015), Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs, in Husfeldt, Thore & Kanj, Iyad eds, 10th International Symposium on Parameterized and Exact Computation (IPEC). Patras, Greece, Leibniz International Proceedings in Informatics, Patras, 102-113.
• Akrida, E.C., Gasieniec, L., Mertzios, G.B. & Spirakis, P.G. (2014), Ephemeral networks with random availability of links: diameter and connectivity, Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures (SPAA). Prague, Czech Republic, Association for Computing Machinery, Prague, 267-276
• Díaz, J., Goldberg, L.A., Mertzios, G.B., Richerby, D., Serna, M. & Spirakis, P.G. (2012), Approximating Fixation Probabilities in the Generalized Moran Process, in Rabani, Yuval eds, 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Kyoto, Japan, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, US, 954-960.
• Mertzios, G.B., Shalom, M., Voloshin, A., Wong, P.W.H. & Zaks, S. (2012), Optimizing busy time on parallel machines, 2012 IEEE 26th International Parallel and Distributed Processing Symposium. Shanghai, IEEE, Shanghai, 238-248.
• Bousquet, N., Gonçalves, D., Mertzios, G.B., Paul, C., Sau, I. & Thomassé, S. (2012), Parameterized Domination in Circle Graphs, in Golumbic, Martin Charles, Stern, Michal, Levy, Avivit & Morgenstern, Gila eds, Lecture Notes in Computer Science 7551: 38th International Workshop, WG 2012. Jerusalem, Israel, Springer, 308-319.
• Mertzios, G.B. (2011), The Recognition of Triangle Graphs, in Schwentick, Thomas & Dürr, Christoph eds, Leibniz International Proceedings in Informatics (LIPIcs) 9: 28th International Symposium on Theoretical Aspects of Computer Science (STACS). Dortmund, Germany, Schloss Dagstuhl, Dortmund, 591-602.
• Mertzios, G.B. & Bezáková, I. (2011), Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time, in Flavia Bonomo, Thomas Liebling, Javier Marenco, Jayme Szwarcfiter, & Mario Valencia-Pabon eds, Electronic Notes in Discrete Mathematics 37: VI Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS). Bariloche, Argentina, Elsevier, Bariloche, 219-224.
• Mertzios, G.B. (2011), An intersection model for multitolerance graphs: Efficient algorithms and hierarchy, ACM-SIAM Symposium on Discrete Algorithms (SODA). San Francisco, California USA, SIAM (Society for Industrial and Applied Mathematics), San Francisco CA, 1306-1317.
• Mertzios, G.B., Shalom, M., Wong, P.W.H. & Zaks, S. (2011), Online Regenerator Placement, in Fernàndez Anta, Antonio, Lipari, Giuseppe & Roy, Matthieu eds, Lecture Notes in Computer Science (LNCS) 7109: 15th International Conference on Principles of Distributed Systems (OPODIS). Toulouse, France, Springer, Toulouse, 4-17.
• Mertzios, G.B., Nikoletseas, S., Raptopoulos, C. & Spirakis, P.G. (2011), Natural Models for Evolution on Networks, in Chen, Ning, Elkind, Edith & Koutsoupias, Elias eds, LNCS (Lecture Notes in Computer Science) 7090: 7th Workshop on Internet & Network Economics (WINE). Singapore, Springer, 290-301.
• Mertzios, G.B., Sau, I. & Zaks, S. (2010), A new intersection model and improved algorithms for tolerance graphs, in Paul, Christophe & Habib, Michel eds, Lecture Notes in Computer Science (LNCS) 5911: 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). Montpellier, France, Springer, Montpellier, 285-295.
• Mertzios, G.B., Sau, I., Shalom, M. & Zaks, S. (2010), Placing regenerators in optical networks to satisfy multiple sets of requests, in Abramsky, Samson Gavoille, Cyril Kirchner, Claude Meyer auf der Heide, Friedhelm & Spirakis, Paul G. eds, Lecture Notes in Computer Science (LNCS) 6199: 37th International Colloquium on Automata, Languages and Programming (ICALP). Bordeaux, France, Springer, Bordeaux, 333-344.
• Mertzios, G.B., Sau, I. & Zaks, S. (2010), The Recognition of Tolerance and Bounded Tolerance Graphs, in Marion, Jean-Yves & Schwentick, Thomas eds, Leibniz International Proceedings in Informatics (LIPIcs) 5: 27th International Symposium on Theoretical Aspects of Computer Science (STACS). Nancy, France, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Nancy, 585-596.
• Mertzios, G.B. & Zaks, S. (2010), On the intersection of tolerance and cocomparability graphs, in Cheong, Otfried Chwa, Kyung-Yong & Park, Kunsoo eds, Lecture Notes in Computer Science (LNCS) 6506: 21st International Symposium on Algorithms and Computation (ISAAC). Jeju Island, Korea, Springer, Jeju Island, 230-240.
• Mertzios, G.B. (2009), Fast convergence of routing games with splittable flows, International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS- 09). Orlando, Florida, ISRST, Orlando FL, 28-33.
• Mertzios, G.B. & Unger, W. (2009), A parameterized algorithm for the preemptive scheduling of equal-length jobs, International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS-09). Orlando, Florida, ISRST, Orlando FL, 20-27.
• Ioannidou, K., Mertzios, G.B. & Nikolopoulos, S.D. (2009), The longest path problem is polynomial on interval graphs, in Rastislav Královic & Damian Niwinski eds, Lecture Notes in Computer Science (LNCS) 5734: 34st International Symposium on Mathematical Foundations of Computer Science (MFCS). Novy Smokovec, Slovakia, Springer, Novy Smokovec, 403-414.
• Mertzios, G.B. & Unger, W. (2008), An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs, 19th International Workshop on Combinatorial Algorithms (IWOCA). Nagoya, Japan, Nagoya, 197-211.
• Mertzios, G.B. & Unger, W. (2008), The friendship problem on graphs, 1st International Conference on Relations, Orders and Graphs: Interaction with Computer Science (ROGICS). Mahdia, Tunisia, Mahdia, 152-158.
• Karras, D.A. & Mertzios, G.B. (2004), Discretization schemes and numerical approximations of PDE impainting models and a comparative evaluation on novel real world MRI reconstruction applications, International Workshop on Imaging Systems and Techniques (IEEE IST 2004). Stresa, Italy, IEEE, Stresa, 153-158.
• Giakos, G.C., Patnekar, N., Sumrain, S., Fraiwan, L., Kumar, V. & Mertzios, G.B. (2003), A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up, 2: IEEE Instrumentation and Measurement Technology Conference (IMTC 2003). Vail, Co. IEEE, Vail CO, 1622-1626.

Journal Article

• Mertzios, G.B., Molter, H., Niedermeier, R., Zamaraev, V. & Zschoche, P. (2023). Computing maximum matchings in temporal graphs. Journal of Computer and System Sciences
• Klobas, N., Mertzios, G.B., Molter, H., Niedermeier, R. & Zschoche, P. (2023). Interference-free walks in time: Temporally disjoint paths. Autonomous Agents and Multi-Agent Systems 37: 1.
• Heeger, K., Hermelin, D., Mertzios, G.B., Molter, H., Niedermeier, R. & Shabtay, D. (2023). Equitable scheduling on a single machine. Journal of Scheduling 26(2): 209–225.
• Akrida, E.C., Mertzios, G.B., Spirakis, P.G. & Raptopoulos, C. (2021). The temporal explorer who returns to the base. Journal of Computer and System Sciences 120: 179-193.
• Mertzios, G.B., Molter, H. & Zamaraev, V. (2021). Sliding window temporal graph coloring. Journal of Computer and System Sciences 120: 97-115.
• Enright, J., Meeks, K., Mertzios, G.B. & Zamaraev, V. (2021). Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences 119: 60-77.
• Mertzios, G.B., Nichterlein, A. & Niedermeier, R. (2020). The Power of Linear-Time Data Reduction for Maximum Matching. Algorithmica 82(12): 3521-3565.
• Akrida, Eleni C., Mertzios, George B., Nikoletseas, Sotiris, Raptopoulos, Christoforos, Spirakis, Paul G. & Zmaraev, Viktor (2020). How fast can we reach a target vertex in stochastic temporal graphs? Journal of Computer and System Sciences 114: 65-83.
• Akrida, E.C., Mertzios, G.B., Spirakis, P.G. & Zamaraev, V. (2020). Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences 107: 108-123.
• Mertzios, G.B., Michail, O. & Spirakis, P.G. (2019). Temporal network optimization subject to connectivity constraints. Algorithmica 81(4): 1416-1449.
• Deligkas, A., Mertzios, G.B. & Spirakis, P.G. (2019). Binary search in graphs revisited. Algorithmica 81(5): 1757.
• Fluschnik, T., Komusiewicz, C., Mertzios, G.B., Nichterlein, A., Niedermeier, R. & Talmon, N. (2019). When can graph hyperbolicity be computed in linear time? Algorithmica 81(5): 2016–2045.
• Mertzios, G.B., Nichterlein, A. & Niedermeier, R. (2018). A linear-time algorithm for maximum-cardinality matching on cocomparability graphs. SIAM Journal on Discrete Mathematics 32(4): 2820-2835.
• Bevern, R.V., Fluschnik, T., Mertzios, G.B., Molter, H., Sorge, M. & Suchý, O. (2018). The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs. Discrete Optimization 30: 20-50.
• Mertzios, G.B. & Spirakis, P.G. (2018). Strong bounds for evolution in networks. Journal of Computer and System Sciences 97: 60-82.
• Giannopoulou, Archontia C., Mertzios, George B. & Niedermeier, Rolf (2017). Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theoretical Computer Science 689: 67-95.
• Diaz, J. & Mertzios, G.B. (2017). Minimum bisection is NP-hard on unit disk graphs. Information and Computation 256: 83-92.
• Akrida, E.C., Gasieniec, L., Mertzios, G.B. & Spirakis, P.G. (2017). The complexity of optimal design of temporally connected graphs. Theory of Computing Systems 61(3): 907–944.
• Foucaud, F., Mertzios, G.B., Naserasr, R., Parreau, A. & Valicov, P. (2017). Identification, location–domination and metric dimension on interval and permutation graphs. I. Bounds. Theoretical Computer Science 668: 43-58.
• Mertzios, G.B., Shalom, M., Wong, P.W.H. & Zaks, S. (2017). Online regenerator placement. Theory of Computing Systems 61(3): 739-754.
• Foucaud, F., Mertzios, G.B., Naserasr, R., Parreau, A. & Valicov, P. (2017). Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica 78(3): 914-944.
• Golovach, P.A. & Mertzios, G.B. (2017). Graph editing to a given degree sequence. Theoretical Computer Science 665: 1-12.
• Mertzios, G.B., Nikoletseas, S.E., Raptopoulos, C.L. & Spirakis, P.G. (2017). Determining majority in networks with local interactions and very small local memory. Distributed Computing 30(1): 1-16.
• Giannopoulou, A.C. & Mertzios, G.B. (2016). New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs. SIAM Journal on Discrete Mathematics 30(3): 1685-1725.
• Mertzios, G.B. & Unger, W. (2016). The friendship problem on graphs. Journal of Multiple-Valued Logic and Soft Computing 27(2-3): 275-285.
• Felsner, S., Knauer, K., Mertzios, G.B. & Ueckerdt, T. (2016). Intersection Graphs of L-Shapes and Segments in the Plane. Discrete Applied Mathematics 206: 48-55.
• Akrida, E.C., Gąsieniec, L., Mertzios, G.B. & Spirakis, P.G. (2016). Ephemeral networks with random availability of links: The case of fast networks. Journal of Parallel and Distributed Computing 87: 109-120.
• Mertzios, G.B. & Zaks, S. (2016). On the intersection of tolerance and cocomparability graphs. Discrete Applied Mathematics 199: 46-88.
• Mertzios, G.B. & Spirakis, P.G. (2016). Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs. Algorithmica 74(1): 385-414.
• Mertzios, G.B. (2015). The recognition of simple-triangle graphs and of linear-interval orders is polynomial. SIAM Journal on Discrete Mathematics 29(3): 1150-1185.
• Mertzios, G.B., Shalom, M., Voloshin, A., Wong, P.W.H. & Zaks, S. (2015). Optimizing busy time on parallel machines. Theoretical Computer Science 562: 524-541.
• Mertzios, G.B. & Bezáková, I. (2014). Computing and counting longest paths on circular-arc graphs in polynomial time. Discrete Applied Mathematics 164(Part 2): 383-399.
• Mertzios, G.B. (2014). An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy. Algorithmica 69(3): 540-581.
• Bousquet, N., Gonçalves, D., Mertzios, G.B., Paul, C., Sau, I. & Thomassé, S. (2014). Parameterized Domination in Circle Graphs. Theory of Computing Systems 54(1): 45-72.
• Díaz, J., Goldberg, L.A., Mertzios, G.B., Richerby, D., Serna, M. & Spirakis, P.G. (2014). Approximating Fixation Probabilities in the Generalized Moran Process. Algorithmica 69(1): 78-91.
• Mertzios, G.B., Nikoletseas, S., Raptopoulos, C. & Spirakis, P.G. (2013). Natural models for evolution on networks. Theoretical Computer Science 477: 76-95.
• Díaz, J., Goldberg, L.A., Mertzios, G.B., Richerby, D., Serna, M. & Spirakis, P.G. (2013). On the fixation probability of superstars. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 469(2156): 20130193.
• Mertzios, G.B., Sau, I., Shalom, M. & Zaks, S. (2012). Placing regenerators in optical networks to satisfy multiple sets of requests. IEEE/ACM Transactions on Networking 20(6): 1870-1879
• Mertzios G.B. & Corneil D.G. (2012). A simple polynomial algorithm for the longest path problem on cocomparability graphs. SIAM Journal on Discrete Mathematics 26(3): 940-963.
• Mertzios, G.B. (2012). The recognition of triangle graphs. Theoretical Computer Science 438: 34-47.
• Ioannidou, K., Mertzios, G.B. & Nikolopoulos, S.D. (2011). The longest path problem has a polynomial solution on interval graphs. Algorithmica 61(2): 320-341.
• Mertzios, G.B. & Corneil, D.G. (2011). Vertex Splitting and the Recognition of Trapezoid Graphs. Discrete Applied Mathematics 159(11): 1131-1147.
• Mertzios, G.B., Sau, I. & Zaks, S. (2011). The recognition of tolerance and bounded tolerance graphs. SIAM Journal on Computing 40(5): 1234-1257.
• Mertzios, G.B. & Unger, W. (2010). An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs. Mathematics in computer science 3(1): 85-96.
• Efraimidis, P.S., Tsavlidis, L. & Mertzios, G.B. (2010). Window-games between TCP flows. Theoretical Computer Science 411(31-33): 2798-2817.
• Mertzios, G.B. & Unger, W. (2010). Preemptive scheduling of equal-length jobs in polynomial time. Mathematics in Computer Science 3(1): 73-84.
• Mertzios, G.B., Sau, I. & Zaks, S. (2009). A New Intersection Model and Improved Algorithms for Tolerance Graphs. SIAM Journal on Discrete Mathematics 23(4): 1800-1813.
• Karras, D.A. & Mertzios, G.B. (2009). New PDE-based methods for image enhancement using SOM and Bayesian inference in various discretization schemes. Measurement Science and Technology 20(10): 104012
• Mertzios, G.B. (2008). A matrix characterization of interval and proper interval graphs. Applied Mathematics Letters 21(4): 332-337.
• Mertzios, G.B. (2006). Solution of parameter-varying linear matrix inequalities in Toeplitz form. Journal of Applied Functional Analysis 1(2): 131-152.
• Giakos, G.C., Fraiwan, L., Patnekar, N., Sumrain, S., Mertzios, G.B. & Periyathamby, S. (2004). A sensitive optical polarimetric imaging technique for surface defects detection of aircraft turbine engines. IEEE Transactions on Instrumentation and Measurement 53(1): 216-222.