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

• Kernelization Lower Bounds for Finding Constant-Size Subgraphs
  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
• Approximating Fixation Probabilities in the Generalized Moran Process
  Mertzios, G. (2014). Approximating Fixation Probabilities in the Generalized Moran Process. In M.-Y. Kao (Ed.), Encyclopedia of algorithms (1-6). Springer Verlag. https://doi.org/10.1007/978-3-642-27848-8_596-1
• Multitolerance Graphs
  Mertzios, G. (2014). Multitolerance Graphs. In M.-Y. Kao (Ed.), Encyclopedia of algorithms (1-6). Springer Verlag. https://doi.org/10.1007/978-3-642-27848-8_684-1
• Minimum Bisection Is NP-hard on Unit Disk Graphs
  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
• Determining Majority in Networks with Local Interactions and Very Small Local Memory
  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
• Intersection Graphs of L-Shapes and Segments in the Plane
  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
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial
  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
• Temporal Network Optimization Subject to Connectivity Constraints
  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
• Strong Bounds for Evolution in Networks
  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
• On the Recognition of Four-Directional Orthogonal Ray Graphs
  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
• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
  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

Conference Paper

• Brief Announcement: Amnesiac Flooding: Easy to Break, Hard to Escape
  Austin, H., Gadouleau, M., Mertzios, G. B., & Trehan, A. (2025, June). Brief Announcement: Amnesiac Flooding: Easy to Break, Hard to Escape. Presented at ACM Principles of Distributed Computing (PODC) 2025, Huatulco, Mexico
• Realizing temporal transportation trees
  Mertzios, G., Molter, H., Morawietz, N., & Spirakis, P. (2025, June). Realizing temporal transportation trees. Presented at 51st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2025), Otzenhausen, Germany
• NP-completeness of the combinatorial distance matrix realisation problem
  Fairbairn, D., Mertzios, G., & Peyerimhoff, N. (2025, December). NP-completeness of the combinatorial distance matrix realisation problem. Presented at 14th International Symposium on Algorithms and Complexity (CIAC 2025), Rome, Italy
• Brief Announcement: Amnesiac Flooding: Easy to Break, Difficult to Escape
  Austin, H., Gadouleau, M., Mertzios, G., & Trehan, A. (2025, June). Brief Announcement: Amnesiac Flooding: Easy to Break, Difficult to Escape. Presented at 2025 Symposium on Principles of Distributed Computing, Huatulco, Mexico
• Temporal graph realization with bounded stretch
  Mertzios, G., Molter, H., Morawietz, N., & Spirakis, P. (2025, August). Temporal graph realization with bounded stretch. Presented at Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), Warsaw, Poland
• The threshold of existence of δ-temporal cliques in random simple temporal graphs
  Mertzios, G. B., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2024, September). The threshold of existence of δ-temporal cliques in random simple temporal graphs. Presented at The 20th International Symposium on Algorithmics of Wireless Networks (ALGOWIN), Egham, London, United Kingdom
• Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs
  Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2024, June). Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs. Presented at 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), Patras, Greece
• Temporal Graph Realization from Fastest Paths
  Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2024, June). Temporal Graph Realization from Fastest Paths. Presented at 3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, Patras, Greece
• Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
  Klobas, N., Mertzios, G. B., & Spirakis, P. G. (2023, August). Sliding into the Future: Investigating Sliding Windows in Temporal Graphs. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France
• Payment scheduling in the Interval Debt Model
  Friedetzky, T., Kutner, D., Mertzios, G., Stewart, I., & Trehan, A. (2023, January). Payment scheduling in the Interval Debt Model. Presented at 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023), Novy Smokovec, Slovakia
• The complexity of growing a graph
  Mertzios, G., Michail, O., Skretas, G., Spirakis, P., & Theofilatos, M. (2022, September). The complexity of growing a graph. Presented at 18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS 2022), Potsdam, Germany
• The complexity of temporal vertex cover in small-degree graphs
  Hamm, T., Klobas, N., Mertzios, G., & Spirakis, P. (2023, February). The complexity of temporal vertex cover in small-degree graphs. Presented at 36th AAAI Conference on Artificial Intelligence (AAAI 2022), Vancouver, BC
• The complexity of computing optimum labelings for temporal connectivity
  Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2022, August). The complexity of computing optimum labelings for temporal connectivity. Presented at 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Vienna, Austria
• Equitable scheduling on a single machine
  Heeger, K., Hermelin, D., Mertzios, G., Molter, H., Niedermeier, R., & Shabtay, D. (2021, February). Equitable scheduling on a single machine. Presented at 35th AAAI Conference on Artificial Intelligence (AAAI), Vancouver, Canada
• The complexity of transitively orienting temporal graphs
  Mertzios, G., Molter, H., Renken, M., Spirakis, P., & Zschoche, P. (2021, August). The complexity of transitively orienting temporal graphs. Presented at 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), Tallinn, Estonia
• Interference-free walks in time: temporally disjoint paths
  Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2021, August). Interference-free walks in time: temporally disjoint paths. Presented at 30th International Joint Conference on Artificial Intelligence (IJCAI-21), Montreal, Quebec
• Computing maximum matchings in temporal graphs
  Mertzios, G., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2020, December). Computing maximum matchings in temporal graphs. Presented at 37th International Symposium on Theoretical Aspects of Computer Science (STACS), Montpellier, France
• Exact and approximate algorithms for computing a second Hamiltonian cycle
  Deligkas, A., Mertzios, G., Spirakis, P., & Zamaraev, V. (2020, December). Exact and approximate algorithms for computing a second Hamiltonian cycle. Presented at MFCS 2020 (International Symposium on Mathematical Foundations of Computer Science), Prague, Czech Republic
• Deleting edges to restrict the size of an epidemic in temporal networks
  Enright, J., Meeks, K., Mertzios, G., & Zamaraev, V. (2019, August). Deleting edges to restrict the size of an epidemic in temporal networks. Presented at 44th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aachen, Germany
• How fast can we reach a target vertex in stochastic temporal graphs?
  Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Christoforos, R., Spirakis, P. G., & Zamaraev, V. (2019, July). How fast can we reach a target vertex in stochastic temporal graphs?. Presented at 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Patras, Greece
• Sliding Window Temporal Graph Coloring
  Mertzios, G., Molter, H., & Zamaraev, V. (2023, January). Sliding Window Temporal Graph Coloring. Presented at 33rd AAAI Conference on Artificial Intelligence (AAAI 2019)., Honolulu, Hawaii, USA
• The temporal explorer who returns to the base
  Akrida, E., Mertzios, G., & Spirakis, P. (2019, December). The temporal explorer who returns to the base. Presented at 11th International Conference on Algorithms and Complexity (CIAC 2019), Rome, Italy
• Temporal vertex cover with a sliding time window
  Akrida, E., Mertzios, G., Spirakis, P., & Zamaraev, V. (2018, July). Temporal vertex cover with a sliding time window. Presented at 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)., Prague, Czech Republic
• Binary search in graphs revisited
  Deligkas, A., Mertzios, G., & Spirakis, P. (2017, August). Binary search in graphs revisited. Presented at 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS), Aalborg, Denmark
• The Power of Linear-Time Data Reduction for Maximum Matching
  Mertzios, G., Nichterlein, A., & Niedermeier, R. (2017, August). The Power of Linear-Time Data Reduction for Maximum Matching. Presented at 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS)., Aalborg, Denmark
• When can graph hyperbolicity be computed in linear time?
  Fluschnik, T., Komusiewicz, C., Mertzios, G., Nichterlein, A., Niedermeier, R., & Talmon, N. (2023, July). When can graph hyperbolicity be computed in linear time?. Presented at Algorithms and Data Structures Symposium (WADS) 2017, St. John’s, NL, Canada
• The computational complexity of weighted greedy matching
  Deligkas, A., Mertzios, G., & Spirakis, P. (2017, February). The computational complexity of weighted greedy matching. Presented at 31st AAAI Conference on Artificial Intelligence (AAAI-17), San Francisco, California, USA
• Finding secluded places of special interest in graphs
  Bevern, R., Fluschnik, T., Mertzios, G., Molter, H., Sorge, M., & Suchý, O. (2016, August). Finding secluded places of special interest in graphs. Presented at 11th International Symposium on Parameterized and Exact Computation (IPEC), Aarhus, Denmark
• Stably computing order statistics with arithmetic population protocols
  Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2016, August). Stably computing order statistics with arithmetic population protocols. Presented at 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)., Krakow, Poland
• Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
  Foucaud, F., Mertzios, G., Naserasr, R., Parreau, A., & Valicov, P. (2016, August). Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. Presented at 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Munich, Germany
• Graph editing to a given degree sequence
  Golovach, P., & Mertzios, G. (2016, June). Graph editing to a given degree sequence. Presented at 11th International Computer Science Symposium in Russia., St. Petersburg, Russia
• On temporally connected graphs of small cost
  Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2015, September). On temporally connected graphs of small cost. Presented at 13th Workshop on Approximation and Online Algorithms (WAOA), Patras, Greece
• Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs
  Giannopoulou, A., Mertzios, G., & Niedermeier, R. (2015, September). Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Presented at 10th International Symposium on Parameterized and Exact Computation (IPEC), Patras, Greece
• New geometric representations and domination problems on tolerance and multitolerance graphs
  Giannopoulou, A., & Mertzios, G. (2015, December). New geometric representations and domination problems on tolerance and multitolerance graphs. Presented at 32nd Symposium on Theoretical Aspects of Computer Science (STACS), Munich, Germany
• Ephemeral networks with random availability of links: diameter and connectivity
  Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2014, June). Ephemeral networks with random availability of links: diameter and connectivity. Presented at Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures (SPAA), Prague, Czech Republic
• Approximating Fixation Probabilities in the Generalized Moran Process
  Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2012, November). Approximating Fixation Probabilities in the Generalized Moran Process. Presented at Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, Kyoto, Japan
• Parameterized Domination in Circle Graphs
  Bousquet, N., Gonçalves, D., Mertzios, G., Paul, C., Sau, I., & Thomassé, S. (2012, December). Parameterized Domination in Circle Graphs. Presented at 38th International Workshop, WG 2012, Jerusalem, Israel
• Optimizing busy time on parallel machines
  Mertzios, G., Shalom, M., Voloshin, A., Wong, P., & Zaks, S. (2012, May). Optimizing busy time on parallel machines. Presented at 2012 IEEE 26th International Parallel and Distributed Processing Symposium, Shanghai
• Natural Models for Evolution on Networks
  Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2011, December). Natural Models for Evolution on Networks. Presented at 7th Workshop on Internet & Network Economics (WINE), Singapore
• Online Regenerator Placement
  Mertzios, G., Shalom, M., Wong, P., & Zaks, S. (2011, December). Online Regenerator Placement. Presented at 15th International Conference on Principles of Distributed Systems (OPODIS), Toulouse, France
• Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time
  Mertzios, G., & Bezáková, I. (2011, August). Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time. Presented at VI Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), Bariloche, Argentina
• The Recognition of Triangle Graphs
  Mertzios, G. (2011, December). The Recognition of Triangle Graphs. Presented at 28th International Symposium on Theoretical Aspects of Computer Science (STACS), Dortmund, Germany
• An intersection model for multitolerance graphs: Efficient algorithms and hierarchy
  Mertzios, G. (2011, January). An intersection model for multitolerance graphs: Efficient algorithms and hierarchy. Presented at ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, California USA
• On the intersection of tolerance and cocomparability graphs
  Mertzios, G., & Zaks, S. (2010, December). On the intersection of tolerance and cocomparability graphs. Presented at 21st International Symposium on Algorithms and Computation (ISAAC), Jeju Island, Korea
• Placing regenerators in optical networks to satisfy multiple sets of requests
  Mertzios, G., Sau, I., Shalom, M., & Zaks, S. (2010, July). Placing regenerators in optical networks to satisfy multiple sets of requests. Presented at 37th International Colloquium on Automata, Languages and Programming (ICALP), Bordeaux, France
• A new intersection model and improved algorithms for tolerance graphs
  Mertzios, G., Sau, I., & Zaks, S. (2010, June). A new intersection model and improved algorithms for tolerance graphs. Presented at 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Montpellier, France
• The Recognition of Tolerance and Bounded Tolerance Graphs
  Mertzios, G., Sau, I., Zaks, S., Marion, J.-Y., & Schwentick, T. (2010, March). The Recognition of Tolerance and Bounded Tolerance Graphs. Presented at 27th International Symposium on Theoretical Aspects of Computer Science (STACS), Nancy, France
• The longest path problem is polynomial on interval graphs
  Ioannidou, K., Mertzios, G., & Nikolopoulos, S. (2009, August). The longest path problem is polynomial on interval graphs. Presented at 34st International Symposium on Mathematical Foundations of Computer Science (MFCS), Novy Smokovec, Slovakia
• Fast convergence of routing games with splittable flows
  Mertzios, G. (2009, July). Fast convergence of routing games with splittable flows. Presented at International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS- 09), Orlando, Florida
• A parameterized algorithm for the preemptive scheduling of equal-length jobs
  Mertzios, G., & Unger, W. (2009, July). A parameterized algorithm for the preemptive scheduling of equal-length jobs. Presented at International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS-09), Orlando, Florida
• The friendship problem on graphs
  Mertzios, G., & Unger, W. (2008, May). The friendship problem on graphs. Presented at 1st International Conference on Relations, Orders and Graphs : Interaction with Computer Science (ROGICS), Mahdia, Tunisia
• An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs
  Mertzios, G., & Unger, W. (2008, May). An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs. Presented at 19th International Workshop on Combinatorial Algorithms (IWOCA), Nagoya, Japan
• Discretization schemes and numerical approximations of PDE impainting models and a comparative evaluation on novel real world MRI reconstruction applications
  Karras, D., & Mertzios, G. (2004, December). Discretization schemes and numerical approximations of PDE impainting models and a comparative evaluation on novel real world MRI reconstruction applications. Presented at International Workshop on Imaging Systems and Techniques (IEEE IST 2004), Stresa, Italy
• A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up
  Giakos, G., Patnekar, N., Sumrain, S., Fraiwan, L., Kumar, V., & Mertzios, G. (2003, December). A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up. Presented at IEEE Instrumentation and Measurement Technology Conference (IMTC 2003), Vail, Co

Journal Article

• The complexity of transitively orienting temporal graphs
  Mertzios, G., Molter, H., Renken, M., Spirakis, P., & Zschoche, P. (2025). The complexity of transitively orienting temporal graphs. Journal of Computer and System Sciences, 150, Article 103630. https://doi.org/10.1016/j.jcss.2025.103630
• Linear Programming complementation
  Gadouleau, M., Mertzios, G., & Zamaraev, V. (2025). Linear Programming complementation. Theoretical Computer Science, 1032, Article 115087. https://doi.org/10.1016/j.tcs.2025.115087
• Payment Scheduling in the Interval Debt Model
  Stewart, I., Kutner, D., Friedetzky, T., Trehan, A., & Mertzios, G. (2025). Payment Scheduling in the Interval Debt Model. Theoretical Computer Science, 1028, Article 115028. https://doi.org/10.1016/j.tcs.2024.115028
• The complexity of growing a graph
  Mertzios, G., Michail, O., Skretas, G., Spirakis, P. G., & Theofilatos, M. (2025). The complexity of growing a graph. Journal of Computer and System Sciences, 147, Article 103587. https://doi.org/10.1016/j.jcss.2024.103587
• The complexity of computing optimum labelings for temporal connectivity
  Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2024). The complexity of computing optimum labelings for temporal connectivity. Journal of Computer and System Sciences, 146, Article 103564. https://doi.org/10.1016/j.jcss.2024.103564
• Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle
  Deligkas, A., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (2024). Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle. Algorithmica, 86(9), 2766-2785. https://doi.org/10.1007/s00453-024-01238-z
• Fast parameterized preprocessing for polynomial-time solvable graph problems
  Himmel, A., Mertzios, G., Nichterlein, A., & Niedermeier, R. (2024). Fast parameterized preprocessing for polynomial-time solvable graph problems. Communications of the ACM, 67(4), 70–79. https://doi.org/10.1145/3624713
• Graphs with minimum fractional domatic number
  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
• Computing maximum matchings in temporal graphs
  Mertzios, G., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2023). Computing maximum matchings in temporal graphs. Journal of Computer and System Sciences, 137, 1-19. https://doi.org/10.1016/j.jcss.2023.04.005
• Equitable scheduling on a single machine
  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
• Interference-free walks in time: Temporally disjoint paths
  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
• Sliding window temporal graph coloring
  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
• The temporal explorer who returns to the base
  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
• Deleting edges to restrict the size of an epidemic in temporal networks
  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
• The Power of Linear-Time Data Reduction for Maximum Matching
  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
• How fast can we reach a target vertex in stochastic temporal graphs?
  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
• Temporal vertex cover with a sliding time window
  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
• Binary search in graphs revisited
  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
• When can graph hyperbolicity be computed in linear time?
  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
• Temporal network optimization subject to connectivity constraints
  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
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
  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
• The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
  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
• Strong bounds for evolution in networks
  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
• Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs
  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
• Minimum bisection is NP-hard on unit disk graphs
  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
• The complexity of optimal design of temporally connected graphs
  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
• Identification, location–domination and metric dimension on interval and permutation graphs. I. Bounds
  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
• Graph editing to a given degree sequence
  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
• Determining majority in networks with local interactions and very small local memory
  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
• Online regenerator placement
  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
• New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs
  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
• The friendship problem on graphs
  Mertzios, G., & Unger, W. (2016). The friendship problem on graphs. Journal of Multiple-Valued Logic and Soft Computing, 27(2-3), 275-285
• Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity
  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
• Intersection Graphs of L-Shapes and Segments in the Plane
  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
• On the intersection of tolerance and cocomparability graphs
  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
• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
  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
• Ephemeral networks with random availability of links: The case of fast networks
  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
• The recognition of simple-triangle graphs and of linear-interval orders is polynomial
  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
• Optimizing busy time on parallel machines
  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
• An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy
  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
• Approximating Fixation Probabilities in the Generalized Moran Process
  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
• Computing and counting longest paths on circular-arc graphs in polynomial time
  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
• Parameterized Domination in Circle Graphs
  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
• On the fixation probability of superstars
  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
• Natural models for evolution on networks
  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
• Placing regenerators in optical networks to satisfy multiple sets of requests
  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
• A simple polynomial algorithm for the longest path problem on cocomparability graphs
  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
• The recognition of triangle graphs
  Mertzios, G. (2012). The recognition of triangle graphs. Theoretical Computer Science, 438, 34-47. https://doi.org/10.1016/j.tcs.2012.02.042
• The longest path problem has a polynomial solution on interval graphs
  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
• The recognition of tolerance and bounded tolerance graphs
  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
• Vertex Splitting and the Recognition of Trapezoid Graphs
  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
• Window-games between TCP flows
  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
• An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs
  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
• Preemptive scheduling of equal-length jobs in polynomial time
  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
• A New Intersection Model and Improved Algorithms for Tolerance Graphs
  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
• New PDE-based methods for image enhancement using SOM and Bayesian inference in various discretization schemes
  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
• A matrix characterization of interval and proper interval graphs
  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
• Solution of parameter-varying linear matrix inequalities in Toeplitz form
  Mertzios, G. (2006). Solution of parameter-varying linear matrix inequalities in Toeplitz form. Journal of applied functional analysis, 1(2), 131-152
• A sensitive optical polarimetric imaging technique for surface defects detection of aircraft turbine engines
  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