Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Profile

Dr George Mertzios, Diplom TU München, PhD RWTH Aachen University

Associate Professor in the Department of Computer Science
Telephone: +44 (0) 191 33 42429
Room number: E320

Biography

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:
http://community.dur.ac.uk/george.mertzios/

Research Groups

  • Algorithms and Complexity

Research Interests

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

Publications

Journal Article

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). Approximating Fixation Probabilities in the Generalized Moran Process. In Encyclopedia of Algorithms. Kao, Ming-Yang Springer. 1-6.
  • Mertzios, G.B. (2015). Multitolerance Graphs. In Encyclopedia of Algorithms. Kao, Ming-Yang Springer.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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. & 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.
  • 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.
  • 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.

Conference Paper

  • 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.
  • 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.
  • 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.
  • 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.
  • 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, E.C., Mertzios, G.B., Spirakis, P.G. & Zamaraev, V. (2018), Temporal vertex covers and sliding time windows, 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.
  • 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.
  • 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), 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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), 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. & 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., 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., 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. (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., 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. & 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., Sau, I., Shalom, M. & Zaks, S. (2010), Placing regenerators in optical networks to satisfy multiple sets of requests, in Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide & Paul G. Spirakis 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. & 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.
  • 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.
  • Ioannidou, K., Mertzios, G.B. & Nikolopoulos, S.D. (2009), The longest path problem is polynomial on interval graphs, in Rastislav Královic and 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.

Selected Grants

  • 2017: Principal Investigator (PI) on the EPSRC-funded grant "Algorithmic Aspects of Temporal Graphs". Total Grant Value: £398,836 (EPSRC contribution: £319,069). More details can be found at: http://gow.epsrc.ac.uk/NGBOViewGrant.aspx?GrantRef=EP/P020372/1
  • 2013: Principal Investigator (PI) on the EPSRC-funded grant "Algorithmic Aspects of Intersection Graph Models" (personal grant). Total Grant Value: £121,002 (EPSRC contribution: £96,802). More details can be found at: http://gow.epsrc.ac.uk/NGBOViewGrant.aspx?GrantRef=EP/K022660/1
  • 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
  • 2011: Co-Investigator (CI) on the EPSRC-funded grant "Algorithmic Aspects of Graph Coloring". Total Grant Value: £546,892 (EPSRC contribution: £437,514). More details can be found at: http://gow.epsrc.ac.uk/NGBOViewGrant.aspx?GrantRef=EP/G043434/1

Supervises