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

Chapter in book

• Fluschnik, T., Mertzios, G., & Nichterlein, A. (2018). Kernelization Lower Bounds for Finding Constant-Size Subgraphs. In F. Manea, R. Miller, & D. Nowotka (Eds.), Sailing routes in the world of computation : 14th Conference on Computability in Europe, CiE 2018, Kiel, Germany, July 30-August 3, 2018. Proceedings (183-193). Springer Verlag. https://doi.org/10.1007/978-3-319-94418-0_19
• Mertzios, G. (2014). Approximating Fixation Probabilities in the Generalized Moran Process. In M. Kao (Ed.), Encyclopedia of algorithms (1-6). Springer Verlag. https://doi.org/10.1007/978-3-642-27848-8_596-1
• Mertzios, G. (2014). Multitolerance Graphs. In M. Kao (Ed.), Encyclopedia of algorithms (1-6). Springer Verlag. https://doi.org/10.1007/978-3-642-27848-8_684-1
• Díaz, J., & Mertzios, G. (2014). Minimum Bisection Is NP-hard on Unit Disk Graphs. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), Mathematical foundations of computer science 2014 : 39th international symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, part II (251-262). Springer Verlag. https://doi.org/10.1007/978-3-662-44465-8_22
• Felsner, S., Knauer, K., Mertzios, G., & Ueckerdt, T. (2014). Intersection Graphs of L-Shapes and Segments in the Plane. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), Mathematical foundations of computer science 2014 : 39th international symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, part II (299-310). Springer Verlag. https://doi.org/10.1007/978-3-662-44465-8_26
• Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2014). Determining Majority in Networks with Local Interactions and Very Small Local Memory. In J. Esparza, P. Fraigniaud, T. Husfeldt, & E. Koutsoupias (Eds.), Automata, languages, and programming : 41st international colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, proceedings, part I (871-882). Springer Verlag. https://doi.org/10.1007/978-3-662-43948-7_72
• Mertzios, G. (2013). The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial. In H. L. Bodlaender, & G. F. Italiano (Eds.), Algorithms - ESA 2013 : 21st annual European symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings (719-730). Springer Verlag. https://doi.org/10.1007/978-3-642-40450-4_61
• Mertzios, G., & Spirakis, P. (2013). Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs. In P. V. E. Boas, F. C. Groen, G. F. Italiano, J. Nawrocki, & H. Sack (Eds.), 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 (332-343). Springer Verlag. https://doi.org/10.1007/978-3-642-35843-2_29
• Mertzios, G., & Spirakis, P. (2013). Strong Bounds for Evolution in Networks. In F. V. Fomin, R. Freivalds, M. Kwiatkowska, & D. Peleg (Eds.), Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, proceedings, part II (669-680). Springer Verlag. https://doi.org/10.1007/978-3-642-39212-2_58
• Felsner, S., Mertzios, G., & Mustata, I. (2013). On the Recognition of Four-Directional Orthogonal Ray Graphs. In K. Chatterjee, & J. Sgall (Eds.), Mathematical foundations of computer science 2013 : 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings (373-384). Springer Verlag. https://doi.org/10.1007/978-3-642-40313-2_34
• Mertzios, G., Michail, O., Chatzigiannakis, I., & Spirakis, P. (2013). Temporal Network Optimization Subject to Connectivity Constraints. In F. V. Fomin, R. Freivalds, M. Kwiatkowska, & D. Peleg (Eds.), Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, proceedings, part II (657-668). Springer Verlag. https://doi.org/10.1007/978-3-642-39212-2_57

Conference Paper

• Klobas, N., Mertzios, G. B., & Spirakis, P. G. (2023). Sliding into the Future: Investigating Sliding Windows in Temporal Graphs. . https://doi.org/10.4230/LIPIcs.MFCS.2023.5
• Friedetzky, T., Kutner, D., Mertzios, G., Stewart, I., & Trehan, A. (2023). Payment scheduling in the Interval Debt Model. . https://doi.org/10.1007/978-3-031-23101-8_18
• Mertzios, G., Michail, O., Skretas, G., Spirakis, P., & Theofilatos, M. (2022). The complexity of growing a graph. In ALGOSENSORS 2022: Algorithmics of Wireless Networks (123-137). https://doi.org/10.1007/978-3-031-22050-0_9
• Hamm, T., Klobas, N., Mertzios, G., & Spirakis, P. (2022). The complexity of temporal vertex cover in small-degree graphs. . https://doi.org/10.1609/aaai.v36i9.21259
• Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2022). The complexity of computing optimum labelings for temporal connectivity. . https://doi.org/10.4230/lipics.mfcs.2022.62
• Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2021). Interference-free walks in time: temporally disjoint paths. . https://doi.org/10.24963/ijcai.2021/563
• Mertzios, G., Molter, H., Renken, M., Spirakis, P., & Zschoche, P. (2021). The complexity of transitively orienting temporal graphs. In F. Bonchi, & S. J. Puglisi (Eds.), . https://doi.org/10.4230/lipics.mfcs.2021.75
• Heeger, K., Hermelin, D., Mertzios, G., Molter, H., Niedermeier, R., & Shabtay, D. (2021). Equitable scheduling on a single machine. . https://doi.org/10.1609/aaai.v35i13.17404
• Mertzios, G., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2020). Computing maximum matchings in temporal graphs. In C. Paul, & M. Blaser (Eds.), 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (27:1-27:14). https://doi.org/10.4230/lipics.stacs.2020.27
• Deligkas, A., Mertzios, G., Spirakis, P., & Zamaraev, V. (2020). Exact and approximate algorithms for computing a second Hamiltonian cycle. In J. Esparza, & D. Král (Eds.), 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) (21:1-21:13). https://doi.org/10.4230/lipics.mfcs.2020.27
• Enright, J., Meeks, K., Mertzios, G., & Zamaraev, V. (2019). Deleting edges to restrict the size of an epidemic in temporal networks. In P. Rossmanith, P. Heggernes, & J. Katoen (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science (57:1-57:15). https://doi.org/10.4230/lipics.mfcs.2019.57
• Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Christoforos, R., Spirakis, P. G., & Zamaraev, V. (2019). How fast can we reach a target vertex in stochastic temporal graphs?. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (131:1-131:14). https://doi.org/10.4230/lipics.icalp.2019.131
• Mertzios, G., Molter, H., & Zamaraev, V. (2019). Sliding Window Temporal Graph Coloring. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (7667-7674). https://doi.org/10.1609/aaai.v33i01.33017667
• Akrida, E., Mertzios, G., & Spirakis, P. (2019). The temporal explorer who returns to the base. In P. Heggernes (Ed.), Algorithms and Complexity (CIAC 2019); 11th International Conference, CIAC 2019, Rome, Italy, May 27–29, 2019 ; proceedings (13-24). https://doi.org/10.1007/978-3-030-17402-6_2
• Akrida, E., Mertzios, G., Spirakis, P., & Zamaraev, V. (2018). Temporal vertex cover with a sliding time window. In I. Chatzigiannakis, C. Kaklamanis, D. Marx, & D. Sannella (Eds.), 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) : Prague, Czech Republic, July 9-13, 2018 ; proceedings (148:1-148:14). https://doi.org/10.4230/lipics.icalp.2018.148
• Mertzios, G., Nichterlein, A., & Niedermeier, R. (2017). The Power of Linear-Time Data Reduction for Maximum Matching. In K. G. Larsen, H. L. Bodlaender, & J. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. https://doi.org/10.4230/lipics.mfcs.2017.46
• Deligkas, A., Mertzios, G., & Spirakis, P. (2017). Binary search in graphs revisited. In K. G. Larsen, H. L. Bodlaender, & J. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. https://doi.org/10.4230/lipics.mfcs.2017.20
• Fluschnik, T., Komusiewicz, C., Mertzios, G., Nichterlein, A., Niedermeier, R., & Talmon, N. (2017). When can graph hyperbolicity be computed in linear time?. In F. Ellen, A. Kolokolova, & J. Sack (Eds.), Algorithms and data structures : 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 – August 2, 2017 ; proceedings (397-408). https://doi.org/10.1007/978-3-319-62127-2_34
• Deligkas, A., Mertzios, G., & Spirakis, P. (2017). The computational complexity of weighted greedy matching. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17) : Hilton, San Francisco, Union Square, February 4, 2017 – February 10 (466-472)
• Bevern, R., Fluschnik, T., Mertzios, G., Molter, H., Sorge, M., & Suchý, O. (2017). Finding secluded places of special interest in graphs. In J. Guo, & D. Hermelin (Eds.), 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) : August 24-26, 2016, Aarhus, Denmark (5:1-5:16). https://doi.org/10.4230/lipics.ipec.2016.5
• Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2016). Stably computing order statistics with arithmetic population protocols. In P. Faliszewski, A. Muscholl, & R. Niedermeier (Eds.), 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) (68:1-68:14). https://doi.org/10.4230/lipics.mfcs.2016.68
• Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2016). Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers (456-471). https://doi.org/10.1007/978-3-662-53174-7_32
• Golovach, P., & Mertzios, G. (2016). Graph editing to a given degree sequence. In A. Kulikov, & G. Woeginger (Eds.), Computer science – Theory and applications : 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016. Proceedings (177-191). https://doi.org/10.1007/978-3-319-34171-2_13
• Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2016). On temporally connected graphs of small cost. In Approximation and online algorithms : 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised selected papers (84-96). https://doi.org/10.1007/978-3-319-28684-6_8
• Giannopoulou, A., Mertzios, G., & Niedermeier, R. (2015). Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. In T. Husfeldt, & I. Kanj (Eds.), 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) (102-113). https://doi.org/10.4230/lipics.ipec.2015.102
• Giannopoulou, A., & Mertzios, G. (2015). New geometric representations and domination problems on tolerance and multitolerance graphs. In E. W. Mayr, & N. Ollinger (Eds.), 32nd international symposium on theoretical aspects of computer science (STACS 2015) (354-366). https://doi.org/10.4230/lipics.stacs.2015.354
• Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2014). Ephemeral networks with random availability of links: diameter and connectivity. In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures (267-276). https://doi.org/10.1145/2612669.2612693
• Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2012). Approximating Fixation Probabilities in the Generalized Moran Process. In Y. Rabani (Ed.), Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan, January 17-19, 2012 (954-960). https://doi.org/10.1137/1.9781611973099.76
• Bousquet, N., Gonçalves, D., Mertzios, G., Paul, C., Sau, I., & Thomassé, S. (2012). Parameterized Domination in Circle Graphs. In M. C. .. Golumbic, M. Stern, A. Levy, & G. Morgenstern (Eds.), Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012 ; revised selected papers (308-319). https://doi.org/10.1007/978-3-642-34611-8_31
• Mertzios, G., Shalom, M., Voloshin, A., Wong, P., & Zaks, S. (2012). Optimizing busy time on parallel machines. In Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium (IPDPS 2012) (238-248). https://doi.org/10.1109/ipdps.2012.31
• Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2011). Natural Models for Evolution on Networks. In N. Chen, E. Elkind, & E. Koutsoupias (Eds.), Internet and network economics : 7th international workshop, WINE 2011, 11-14 December 2011 ; proceedings (290-301). https://doi.org/10.1007/978-3-642-25510-6_25
• Mertzios, G., Shalom, M., Wong, P., & Zaks, S. (2011). Online Regenerator Placement. In A. Fernàndez Anta, G. Lipari, & M. Roy (Eds.), Principles of distributed systems, OPODIS 2011, 15th International Conference, 13-16 December 2011, Toulouse, France ; proceedings (4-17). https://doi.org/10.1007/978-3-642-25873-2_2
• Mertzios, G., & Bezáková, I. (2011). Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time. In F. Bonomo, T. Liebling, J. Marenco, J. Szwarcfiter, & M. Valencia-Pabon (Eds.), . https://doi.org/10.1016/j.endm.2011.05.038
• Mertzios, G. (2011). The Recognition of Triangle Graphs. In T. Schwentick, & C. Dürr (Eds.), 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, 10-12 March 2011, Dortmund, Germany ; proceedings (591-602). https://doi.org/10.4230/lipics.stacs.2011.591
• Mertzios, G. (2011). An intersection model for multitolerance graphs: Efficient algorithms and hierarchy. In Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 23-25 January 2011, San Francisco ; proceedings (1306-1317)
• Mertzios, G., & Zaks, S. (2010). On the intersection of tolerance and cocomparability graphs. In O. Cheong, K. Chwa, & K. Park (Eds.), Algorithms and Computation, 21st International Symposium, ISAAC 2010, 15-17 December 2010, Jeju Island, Korea ; proceedings Part I (230-240). https://doi.org/10.1007/978-3-642-17517-6_22
• Mertzios, G., Sau, I., Shalom, M., & Zaks, S. (2010). Placing regenerators in optical networks to satisfy multiple sets of requests. In S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, & P. G. Spirakis (Eds.), Automata, Languages and Programming : 37th International Colloquium, ICALP 2010, 6-10 July 2010, Bordeaux, France ; proceedings, Part II (333-344). https://doi.org/10.1007/978-3-642-14162-1_28
• Mertzios, G., Sau, I., & Zaks, S. (2010). A new intersection model and improved algorithms for tolerance graphs. In C. Paul, & M. Habib (Eds.), Graph-theoretic concepts in computer science : 35th international workshop, WG 2009, 24-26 June 2009, Montpellier, France ; revised papers (285-295). https://doi.org/10.1007/978-3-642-11409-0_25
• Mertzios, G., Sau, I., & Zaks, S. (2010). The Recognition of Tolerance and Bounded Tolerance Graphs. In J. Marion, & T. Schwentick (Eds.), . https://doi.org/10.4230/lipics.stacs.2010.2487
• Ioannidou, K., Mertzios, G., & Nikolopoulos, S. (2009). The longest path problem is polynomial on interval graphs. In K. Rastislav, & N. Damian (Eds.), Mathematical foundations of computer science 2009 34th international symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009 : proceedings (403-414). https://doi.org/10.1007/978-3-642-03816-7_35
• Mertzios, G., & Unger, W. (2009). A parameterized algorithm for the preemptive scheduling of equal-length jobs.
• Mertzios, G. (2009). Fast convergence of routing games with splittable flows.
• Mertzios, G., & Unger, W. (2008). An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs.
• Mertzios, G., & Unger, W. (2008). The friendship problem on graphs.
• Karras, D., & Mertzios, G. (2004). Discretization schemes and numerical approximations of PDE impainting models and a comparative evaluation on novel real world MRI reconstruction applications. In 2004 IEEE International Workshop on Imaging Systems and Techniques (IST) : 14 May 2004, Stresa, Italy ; proceedings (153-158). https://doi.org/10.1109/ist.2004.1397304
• Giakos, G., Patnekar, N., Sumrain, S., Fraiwan, L., Kumar, V., & Mertzios, G. (2003). A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up. In Instrumentation and Measurement Technology, 20th Annual Conference, IMTC '03, 20-22 May 2003, Colorado, USA ; proceedings (1622-1626). https://doi.org/10.1109/imtc.2003.1208024

Journal Article

• Deligkas, A., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (in press). Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle. Algorithmica,
• Himmel, A., Mertzios, G., Nichterlein, A., & Niedermeier, R. (in press). Fast parameterized preprocessing for polynomial-time solvable graph problems. Communications of the ACM,
• Gadouleau, M., Harms, N., Mertzios, G. B., & Zamaraev, V. (2024). Graphs with minimum fractional domatic number. Discrete Applied Mathematics, 343, 140-148. https://doi.org/10.1016/j.dam.2023.10.020
• Heeger, K., Hermelin, D., Mertzios, G., Molter, H., Niedermeier, R., & Shabtay, D. (2023). Equitable scheduling on a single machine. Journal of Scheduling, 26(2), 209-225. https://doi.org/10.1007/s10951-022-00754-6
• Mertzios, G., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2023). Computing maximum matchings in temporal graphs. Journal of Computer and System Sciences, https://doi.org/10.1016/j.jcss.2023.04.005
• Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2022). Interference-free walks in time: Temporally disjoint paths. Autonomous Agents and Multi-Agent Systems, 37, Article 1. https://doi.org/10.1007/s10458-022-09583-5
• Mertzios, G., Molter, H., & Zamaraev, V. (2021). Sliding window temporal graph coloring. Journal of Computer and System Sciences, 120, 97-115. https://doi.org/10.1016/j.jcss.2021.03.005
• Akrida, E., Mertzios, G., Spirakis, P., & Raptopoulos, C. (2021). The temporal explorer who returns to the base. Journal of Computer and System Sciences, 120, 179-193. https://doi.org/10.1016/j.jcss.2021.04.001
• Enright, J., Meeks, K., Mertzios, G., & Zamaraev, V. (2021). Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences, 119, 60-77. https://doi.org/10.1016/j.jcss.2021.01.007
• Mertzios, G., Nichterlein, A., & Niedermeier, R. (2020). The Power of Linear-Time Data Reduction for Maximum Matching. Algorithmica, 82(12), 3521-3565. https://doi.org/10.1007/s00453-020-00736-0
• Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Raptopoulos, C., Spirakis, P. G., & Zmaraev, V. (2020). How fast can we reach a target vertex in stochastic temporal graphs?. Journal of Computer and System Sciences, 114, 65-83. https://doi.org/10.1016/j.jcss.2020.05.005
• Akrida, E., Mertzios, G., Spirakis, P., & Zamaraev, V. (2020). Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107, 108-123. https://doi.org/10.1016/j.jcss.2019.08.002
• Deligkas, A., Mertzios, G., & Spirakis, P. (2019). Binary search in graphs revisited. Algorithmica, 81(5), Article 1757. https://doi.org/10.1007/s00453-018-0501-y
• Fluschnik, T., Komusiewicz, C., Mertzios, G., Nichterlein, A., Niedermeier, R., & Talmon, N. (2019). When can graph hyperbolicity be computed in linear time?. Algorithmica, 81(5), 2016-2045. https://doi.org/10.1007/s00453-018-0522-6
• Mertzios, G., Michail, O., & Spirakis, P. (2019). Temporal network optimization subject to connectivity constraints. Algorithmica, 81(4), 1416-1449. https://doi.org/10.1007/s00453-018-0478-6
• Mertzios, G., 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. https://doi.org/10.1137/17m1120920
• Mertzios, G., & Spirakis, P. (2018). Strong bounds for evolution in networks. Journal of Computer and System Sciences, 97, 60-82. https://doi.org/10.1016/j.jcss.2018.04.004
• Bevern, R., Fluschnik, T., Mertzios, G., 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. https://doi.org/10.1016/j.disopt.2018.05.002
• Giannopoulou, A. C., Mertzios, G. B., & Niedermeier, R. (2017). Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theoretical Computer Science, 689, 67-95. https://doi.org/10.1016/j.tcs.2017.05.017
• Diaz, J., & Mertzios, G. (2017). Minimum bisection is NP-hard on unit disk graphs. Information and Computation, 256, 83-92. https://doi.org/10.1016/j.ic.2017.04.010
• Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2017). The complexity of optimal design of temporally connected graphs. Theory of Computing Systems, 61(3), 907-944. https://doi.org/10.1007/s00224-017-9757-x
• Foucaud, F., Mertzios, G., 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. https://doi.org/10.1016/j.tcs.2017.01.006
• Golovach, P., & Mertzios, G. (2017). Graph editing to a given degree sequence. Theoretical Computer Science, 665, 1-12. https://doi.org/10.1016/j.tcs.2016.12.007
• Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2017). Determining majority in networks with local interactions and very small local memory. Distributed Computing, 30(1), 1-16. https://doi.org/10.1007/s00446-016-0277-8
• Mertzios, G., Shalom, M., Wong, P., & Zaks, S. (2016). Online regenerator placement. Theory of Computing Systems, 61(3), 739-754. https://doi.org/10.1007/s00224-016-9711-3
• Giannopoulou, A., & Mertzios, G. (2016). New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs. SIAM Journal on Discrete Mathematics, 30(3), 1685-1725. https://doi.org/10.1137/15m1039468
• Mertzios, G., & Unger, W. (2016). The friendship problem on graphs. Journal of Multiple-Valued Logic and Soft Computing, 27(2-3), 275-285
• Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2016). Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica, 78(3), 914-944. https://doi.org/10.1007/s00453-016-0184-1
• Felsner, S., Knauer, K., Mertzios, G., & Ueckerdt, T. (2016). Intersection Graphs of L-Shapes and Segments in the Plane. Discrete Applied Mathematics, 206, 48-55. https://doi.org/10.1016/j.dam.2016.01.028
• Mertzios, G., & Zaks, S. (2016). On the intersection of tolerance and cocomparability graphs. Discrete Applied Mathematics, 199, 46-88. https://doi.org/10.1016/j.dam.2014.10.025
• Akrida, E., Gąsieniec, L., Mertzios, G., & Spirakis, P. (2016). Ephemeral networks with random availability of links: The case of fast networks. Journal of Parallel and Distributed Computing, 87, 109-120. https://doi.org/10.1016/j.jpdc.2015.10.002
• Mertzios, G., & Spirakis, P. (2016). Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs. Algorithmica, 74(1), 385-414. https://doi.org/10.1007/s00453-014-9949-6
• Mertzios, G. (2015). The recognition of simple-triangle graphs and of linear-interval orders is polynomial. SIAM Journal on Discrete Mathematics, 29(3), 1150-1185. https://doi.org/10.1137/140963108
• Mertzios, G., Shalom, M., Voloshin, A., Wong, P., & Zaks, S. (2015). Optimizing busy time on parallel machines. Theoretical Computer Science, 562, 524-541. https://doi.org/10.1016/j.tcs.2014.10.033
• Mertzios, G. (2014). An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy. Algorithmica, 69(3), 540-581. https://doi.org/10.1007/s00453-012-9743-2
• Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2014). Approximating Fixation Probabilities in the Generalized Moran Process. Algorithmica, 69(1), 78-91. https://doi.org/10.1007/s00453-012-9722-7
• Mertzios, G., & Bezáková, I. (2014). Computing and counting longest paths on circular-arc graphs in polynomial time. Discrete Applied Mathematics, 164(Part 2), 383-399. https://doi.org/10.1016/j.dam.2012.08.024
• Bousquet, N., Gonçalves, D., Mertzios, G., Paul, C., Sau, I., & Thomassé, S. (2014). Parameterized Domination in Circle Graphs. Theory of Computing Systems, 54(1), 45-72. https://doi.org/10.1007/s00224-013-9478-8
• Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2013). On the fixation probability of superstars. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 469(2156), https://doi.org/10.1098/rspa.2013.0193
• Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2013). Natural models for evolution on networks. Theoretical Computer Science, 477, 76-95. https://doi.org/10.1016/j.tcs.2012.11.032
• Mertzios, G., 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. https://doi.org/10.1109/tnet.2012.2186462
• Mertzios, G., & Corneil, D. (2012). A simple polynomial algorithm for the longest path problem on cocomparability graphs. SIAM Journal on Discrete Mathematics, 26(3), 940-963. https://doi.org/10.1137/100793529
• Mertzios, G. (2012). The recognition of triangle graphs. Theoretical Computer Science, 438, 34-47. https://doi.org/10.1016/j.tcs.2012.02.042
• Ioannidou, K., Mertzios, G., & Nikolopoulos, S. (2011). The longest path problem has a polynomial solution on interval graphs. Algorithmica, 61(2), 320-341. https://doi.org/10.1007/s00453-010-9411-3
• Mertzios, G., Sau, I., & Zaks, S. (2011). The recognition of tolerance and bounded tolerance graphs. SIAM Journal on Computing, 40(5), 1234-1257. https://doi.org/10.1137/090780328
• Mertzios, G., & Corneil, D. (2011). Vertex Splitting and the Recognition of Trapezoid Graphs. Discrete Applied Mathematics, 159(11), 1131-1147. https://doi.org/10.1016/j.dam.2011.03.023
• Efraimidis, P., Tsavlidis, L., & Mertzios, G. (2010). Window-games between TCP flows. Theoretical Computer Science, 411(31-33), 2798-2817. https://doi.org/10.1016/j.tcs.2010.03.031
• Mertzios, G., & 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. https://doi.org/10.1007/s11786-009-0004-y
• Mertzios, G., & Unger, W. (2010). Preemptive scheduling of equal-length jobs in polynomial time. Mathematics in Computer Science, 3(1), 73-84. https://doi.org/10.1007/s11786-009-0003-z
• Mertzios, G., Sau, I., & Zaks, S. (2010). A New Intersection Model and Improved Algorithms for Tolerance Graphs. SIAM Journal on Discrete Mathematics, 23(4), 1800-1813. https://doi.org/10.1137/09075994x
• Karras, D., & Mertzios, G. (2009). New PDE-based methods for image enhancement using SOM and Bayesian inference in various discretization schemes. Measurement Science and Technology, 20(10), Article 104012. https://doi.org/10.1088/0957-0233/20/10/104012
• Mertzios, G. (2008). A matrix characterization of interval and proper interval graphs. Applied Mathematics Letters, 21(4), 332-337. https://doi.org/10.1016/j.aml.2007.04.001
• Mertzios, G. (2006). Solution of parameter-varying linear matrix inequalities in Toeplitz form. Journal of applied functional analysis, 1(2), 131-152
• Giakos, G., Fraiwan, L., Patnekar, N., Sumrain, S., Mertzios, G., & 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. https://doi.org/10.1109/tim.2003.821497