Skip to main content

Staff profile

Overview

Dr George Mertzios

Associate Professor

Affiliations
AffiliationTelephone
Associate Professor in the Department of Computer Science+44 (0) 191 33 42429

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:
https://mertzios.net/

Research interests

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

Publications

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. (pp. 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. (pp. 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. (pp. 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. (pp. 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. (pp. 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. (pp. 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. (pp. 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. (pp. 657-668). Springer Verlag. https://doi.org/10.1007/978-3-642-39212-2_57
  • 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. van 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. (pp. 332-343). Springer Verlag. https://doi.org/10.1007/978-3-642-35843-2_29
  • 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. (pp. 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. (pp. 373-384). Springer Verlag. https://doi.org/10.1007/978-3-642-40313-2_34

Conference Paper

  • Brief Announcement: Amnesiac Flooding: Easy to Break, Hard to Escape
    Austin, H., Gadouleau, M., Mertzios, G. B., & Trehan, A. (in press). Brief Announcement: Amnesiac Flooding: Easy to Break, Hard to Escape. Presented at ACM Principles of Distributed Computing (PODC) 2025, Huatulco, Mexico.
  • NP-completeness of the combinatorial distance matrix realisation problem
    Fairbairn, D., Mertzios, G., & Peyerimhoff, N. (in press). 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. (in press). Brief Announcement: Amnesiac Flooding: Easy to Break, Difficult to Escape. Presented at 2025 Symposium on Principles of Distributed Computing, Huatulco, Mexico.
  • The threshold of existence of δ-temporal cliques in random simple temporal graphs
    Mertzios, G. B., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2025). The threshold of existence of δ-temporal cliques in random simple temporal graphs. In Q. Bramas, A. Casteigts, & K. Meeks (Eds.), Algorithmics of Wireless Networks (pp. 131-143). Springer. https://doi.org/10.1007/978-3-031-74580-5_10
  • Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs
    Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2024). Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) (pp. 27:1-27:5). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2024.27
  • Temporal Graph Realization from Fastest Paths
    Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2024). Temporal Graph Realization from Fastest Paths. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) (pp. 16:1-16:18). Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2024. https://doi.org/10.4230/LIPIcs.SAND.2024.16
  • Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
    Klobas, N., Mertzios, G. B., & Spirakis, P. G. (2023, August 21). 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. https://doi.org/10.4230/LIPIcs.MFCS.2023.5
  • Payment scheduling in the Interval Debt Model
    Friedetzky, T., Kutner, D., Mertzios, G., Stewart, I., & Trehan, A. (2023). Payment scheduling in the Interval Debt Model. In Lecture Notes in Computer Science (pp. 267-282). Springer Verlag. https://doi.org/10.1007/978-3-031-23101-8_18
  • The complexity of growing a graph
    Mertzios, G., Michail, O., Skretas, G., Spirakis, P., & Theofilatos, M. (2022). The complexity of growing a graph. In ALGOSENSORS 2022: Algorithmics of Wireless Networks (pp. 123-137). Springer Verlag. https://doi.org/10.1007/978-3-031-22050-0_9
  • The complexity of temporal vertex cover in small-degree graphs
    Hamm, T., Klobas, N., Mertzios, G., & Spirakis, P. (2022, June 28). The complexity of temporal vertex cover in small-degree graphs. Presented at 36th AAAI Conference on Artificial Intelligence (AAAI 2022), Vancouver, BC. https://doi.org/10.1609/aaai.v36i9.21259
  • The complexity of computing optimum labelings for temporal connectivity
    Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2022). The complexity of computing optimum labelings for temporal connectivity. In Leibniz International Proceedings in Informatics (LIPIcs) (pp. 62:1-62:15). LIPIcs (Leibniz International Proceedings in Informatics). https://doi.org/10.4230/lipics.mfcs.2022.62
  • The complexity of transitively orienting temporal graphs
    Mertzios, G., Molter, H., Renken, M., Spirakis, P., & Zschoche, P. (2021). The complexity of transitively orienting temporal graphs (F. Bonchi & S. J. Puglisi, Eds.). https://doi.org/10.4230/lipics.mfcs.2021.75
  • Equitable scheduling on a single machine
    Heeger, K., Hermelin, D., Mertzios, G., Molter, H., Niedermeier, R., & Shabtay, D. (2021). Equitable scheduling on a single machine. Presented at 35th AAAI Conference on Artificial Intelligence (AAAI), Vancouver, Canada. https://doi.org/10.1609/aaai.v35i13.17404
  • Interference-free walks in time: temporally disjoint paths
    Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2021). Interference-free walks in time: temporally disjoint paths. Presented at 30th International Joint Conference on Artificial Intelligence (IJCAI-21), Montreal, Quebec. https://doi.org/10.24963/ijcai.2021/563
  • Computing maximum matchings in temporal graphs
    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) (pp. 27:1-27:14). Dagstuhl Publishing. https://doi.org/10.4230/lipics.stacs.2020.27
  • Exact and approximate algorithms for computing a second Hamiltonian cycle
    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). (pp. 21:1-21:13). Dagstuhl Publishing. https://doi.org/10.4230/lipics.mfcs.2020.27
  • Deleting edges to restrict the size of an epidemic in temporal networks
    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.-P. Katoen (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science (pp. 57:1-57:15). Schloss Dagstuhl. https://doi.org/10.4230/lipics.mfcs.2019.57
  • 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). 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) (pp. 131:1-131:14). Dagstuhl Publishing. https://doi.org/10.4230/lipics.icalp.2019.131
  • Sliding Window Temporal Graph Coloring
    Mertzios, G., Molter, H., & Zamaraev, V. (2019). Sliding Window Temporal Graph Coloring. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. (pp. 7667-7674). AAAI Press. https://doi.org/10.1609/aaai.v33i01.33017667
  • The temporal explorer who returns to the base
    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. (pp. 13-24). Springer Verlag. https://doi.org/10.1007/978-3-030-17402-6_2
  • Temporal vertex cover with a sliding time window
    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. (pp. 148:1-148:14). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.icalp.2018.148
  • Binary search in graphs revisited
    Deligkas, A., Mertzios, G., & Spirakis, P. (2017). Binary search in graphs revisited. In K. G. Larsen, H. L. Bodlaender, & J.-F. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.mfcs.2017.20
  • The Power of Linear-Time Data Reduction for Maximum Matching
    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.-F. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings.. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.mfcs.2017.46
  • When can graph hyperbolicity be computed in linear time?
    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.-R. Sack (Eds.), Algorithms and data structures : 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 – August 2, 2017 ; proceedings. (pp. 397-408). Springer Verlag. https://doi.org/10.1007/978-3-319-62127-2_34
  • The computational complexity of weighted greedy matching
    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. (pp. 466-472). AAAI Press.
  • Finding secluded places of special interest in graphs
    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. (pp. 5:1-5:16). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.ipec.2016.5
  • Stably computing order statistics with arithmetic population protocols
    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). (pp. 68:1-68:14). Schloss Dagstuhl - Leibniz Center for Informatics. https://doi.org/10.4230/lipics.mfcs.2016.68
  • 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). 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. (pp. 456-471). Springer Verlag. https://doi.org/10.1007/978-3-662-53174-7_32
  • Graph editing to a given degree sequence
    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. (pp. 177-191). Springer Verlag. https://doi.org/10.1007/978-3-319-34171-2_13
  • On temporally connected graphs of small cost
    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. (pp. 84-96). Springer Verlag. https://doi.org/10.1007/978-3-319-28684-6_8
  • Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs
    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). (pp. 102-113). Leibniz International Proceedings in Informatics. https://doi.org/10.4230/lipics.ipec.2015.102
  • New geometric representations and domination problems on tolerance and multitolerance graphs
    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). (pp. 354-366). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.stacs.2015.354
  • Ephemeral networks with random availability of links: diameter and connectivity
    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. (pp. 267-276). Association for Computing Machinery (ACM). https://doi.org/10.1145/2612669.2612693
  • Approximating Fixation Probabilities in the Generalized Moran Process
    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. (pp. 954-960). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973099.76
  • Parameterized Domination in Circle Graphs
    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 (pp. 308-319). Springer Verlag. https://doi.org/10.1007/978-3-642-34611-8_31
  • Optimizing busy time on parallel machines
    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). (pp. 238-248). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ipdps.2012.31
  • Natural Models for Evolution on Networks
    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. (pp. 290-301). Springer Verlag. https://doi.org/10.1007/978-3-642-25510-6_25
  • Online Regenerator Placement
    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. (pp. 4-17). Springer Verlag. https://doi.org/10.1007/978-3-642-25873-2_2
  • Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time
    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.), Electronic notes in discrete mathematics (pp. 219-224). Elsevier. https://doi.org/10.1016/j.endm.2011.05.038
  • The Recognition of Triangle Graphs
    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. (pp. 591-602). Schloss Dagstuhl. https://doi.org/10.4230/lipics.stacs.2011.591
  • An intersection model for multitolerance graphs: Efficient algorithms and hierarchy
    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. (pp. 1306-1317). Society for Industrial and Applied Mathematics.
  • On the intersection of tolerance and cocomparability graphs
    Mertzios, G., & Zaks, S. (2010). On the intersection of tolerance and cocomparability graphs. In O. Cheong, K.-Y. Chwa, & K. Park (Eds.), Algorithms and Computation, 21st International Symposium, ISAAC 2010, 15-17 December 2010, Jeju Island, Korea ; proceedings Part I. (pp. 230-240). Springer Verlag. https://doi.org/10.1007/978-3-642-17517-6_22
  • Placing regenerators in optical networks to satisfy multiple sets of requests
    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. (pp. 333-344). Springer Verlag. https://doi.org/10.1007/978-3-642-14162-1_28
  • 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. 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. (pp. 285-295). Springer Verlag. https://doi.org/10.1007/978-3-642-11409-0_25
  • The Recognition of Tolerance and Bounded Tolerance Graphs
    Mertzios, G., Sau, I., Zaks, S., Marion, J.-Y., & Schwentick, T. (2010). The Recognition of Tolerance and Bounded Tolerance Graphs. In J.-Y. Marion & T. Schwentick (Eds.), 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, 4-6 March 2010 ; proceedings. (pp. 585-596). Schloss Dagstuhl. https://doi.org/10.4230/lipics.stacs.2010.2487
  • The longest path problem is polynomial on interval graphs
    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. (pp. 403-414). Springer Verlag. https://doi.org/10.1007/978-3-642-03816-7_35
  • A parameterized algorithm for the preemptive scheduling of equal-length jobs
    Mertzios, G., & Unger, W. (2009, July 1). 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.
  • Fast convergence of routing games with splittable flows
    Mertzios, G. (2009, July 1). Fast convergence of routing games with splittable flows. 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, January 1). 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, January 1). 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). 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. (pp. 153-158). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ist.2004.1397304
  • 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). 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. (pp. 1622-1626). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/imtc.2003.1208024

Journal Article

Supervision students

David Kutner

Postgraduate Student

David Fairbairn

3P

Henry Austin

Postgraduate Student

Yilin Li

Postgraduate Student