Home page of George B. Mertzios

Dr. George B. Mertzios
Associate Professor

Contact

Address:
- Department of Computer Science,
- Durham University, Upper Mountjoy Campus,
- Stockton Road, Durham DH1 3LE
- United Kingdom
- Room: MCS 2066
- Phone: + 44 (0) 191 33 42 429

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

Brief Curriculum Vitae

Since March 2017: Associate Professor at the Algorithms and Complexity Research Group (ACiD), Department of Computer Science, Durham University, UK
October 2015 - February 2017: Senior Lecturer in Computer Science at the Algorithms and Complexity Research Group (ACiD), School of Engineering and Computing Sciences, Durham University, UK
September 2011 - September 2015: Lecturer in Computer Science at the Algorithms and Complexity Research Group (ACiD), School of Engineering and Computing Sciences, Durham University, UK
June - July 2012: Invited Assistant Professor at the Laboratoire Bordelais de Recherche en Informatique (LaBRI), University of Bordeaux/CNRS, France.
October 2010 - August 2011: Postdoc research fellow at the Caesarea Rothschild Institute for Interdisciplinary Applications of Computer Science, University of Haifa, Haifa, Israel
April - July 2010: Visiting research fellow at the Department of Computer Science, Technion - Israel Institute of Technology, Haifa, Israel
November 2009: PhD degree in Computer Science, Department of Computer Science, RWTH Aachen University
October 2006 - March 2010: Research Assistant at RWTH Aachen University
July 2005: Degree ("Diplom") in Mathematics with minor Computer Science (1.2, "Excellent"), Technische Universität München
2003 - 2005: Studies in Mathematics and Informatics, Technische Universität München
2000 - 2003: Studies at the School of Applied Mathematics and Physical Sciences (average 9.46 / 10), National Technical University of Athens (NTUA)

Invited Talks and Academic Posts

January 2022: Invited Monday Lecture at the DFG Graduiertenkolleg Facets of Complexity (GRK 2434), Algorithmic problems on temporal graphs [recording], Technische Universität Berlin, Germany.
March-June 2020: Research Scholarship (Forschungsstipendium) from the DFG Gratuiertenkolleg Facets of Complexity (GRK 2434), Freie Universität Berlin, Germany.
September 2019: 9th Workshop on Graph Classes, Optimization, and Width Parameters (GROW 2019), Temporal vertex cover with a sliding time window, Vienna, Austria (participation by invitation only).
June 2019: Invited Talk at the Workshop of Network Sciences and Technologies (NeST), Sliding window temporal graph coloring, University of Liverpool, UK.
September 2018: Invited Talk at the 2nd AlgoUK workshop, Temporal vertex cover with a sliding time window, University of Liverpool, UK.
October 2017: 8th Workshop on Graph Classes, Optimization, and Width Parameters (GROW 2017), Algorithms and complexity on temporal graphs (video), Toronto, Canada (participation by invitation only).
July 2016: Invited Monday Lecture at the Graduiertenkolleg: Methods for Discrete Structures, Algorithms and complexity on temporal graphs, Technische Universität Berlin, Germany.
October 2015: 7th Workshop on Graph Classes, Optimization, and Width Parameters (GROW 2015), Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs, Aussois, France (participation by invitation only).
June 2015: Algorithmic Graph Theory on the Adriatic Coast (AGTAC 2015), New geometric representations and domination problems on tolerance and multitolerance graphs (slides), Koper, Slovenia (participation by invitation only).
June 2015: Invited Talk at the 5th biennial Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM), Minisimposium Geometric representations of graphs, New geometric representations and domination problems on tolerance and multitolerance graphs, University of Saskatchewan, Saskatoon, SK, Canada.
June 2014: Invited Talk at the Workshop of Network Sciences and Technologies (NeST), Determining majority in networks with local interactions and very small local memory (slides), University of Liverpool, UK.
June 2014: Invited Talk at the SIAM Conference on Discrete Mathematics, Minisimposium MS23 - Geometric Representations of Graphs, The recognition of simple-triangle graphs and of linear-interval orders is polynomial, Minneapolis, Minnesota, USA.
February 2014: Dagstuhl seminar 14071 (''Graph Modifcation Problems''), On the recognition of four-directional orthogonal ray graphs, Schloss Dagstuhl, Germany (participation by invitation only).
October 2013: 6th Workshop on Graph Classes, Optimization, and Width Parameters (GROW 2013), The recognition of simple-triangle graphs and of linear-interval orders is polynomial, Santorini, Greece (participation by invitation only).
July 2013: Invited Talk at the EULER Summer School 2013, Graph and routing dynamics: models and algorithms, Advances in algorithmic graph theory (slides Part I and slides Part II), Universitat Politecnica de Catalunya, Barcelona, Spain, organised by the FP7 EULER project.
June - July 2012: Invited Assistant Professor at the Laboratoire Bordelais de Recherche en Informatique (LaBRI), University of Bordeaux/CNRS, France.
June 2011: Invited Talk at the 3rd biennial Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM), Minisimposium Geometric Representations of Graphs II, Geometric intersection models on the plane and the 3D-space, University of Victoria, Victoria, BC, Canada.
October 2009: 4th Workshop on Graph Classes, Optimization, and Width Parameters (GROW 2009), The recognition of tolerance and bounded tolerance graphs, Bergen, Norway (participation by invitation only).

Recent / Upcoming Scientific Activities

Co-Author of the article ``Fast parameterized preprocessing for polynomial-time solvable graph problems'' about the research topic ``FPT inside P'' at the Communications of the ACM, 2024.
Co-Organizer of the ICALP 2024 satellite workshop Algorithmic Aspects of Temporal Graphs VII, Tallinn, Estonia, 7 July 2024.
PC member of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND) 2024.
PC member of the 19th Scandinavian Symposium on Algorithm Theory (SWAT) 2024.
Co-Organizer of the ICALP 2023 satellite workshop Algorithmic Aspects of Temporal Graphs VI, Paderborn, Germany, 10 July 2023.
PC member of the 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND) 2023.
Co-Organizer of the ICALP 2022 satellite workshop Algorithmic Aspects of Temporal Graphs V, Paris, France, July 2022.
PC member of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS) 2022.
Coordinator of the seminar series of the research group Network Engineering Science and Theory in Durham (NESTiD).
Co-Organizer of the ICALP 2021 satellite workshop Algorithmic Aspects of Temporal Graphs IV, Glasgow, Scotland, UK, July 2021.
PC member of the 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND) 2022.
Member of the Advisory Board of the 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND) 2022.
PC member of the 32nd International Workshop on Combinatorial Algorithms (IWOCA) 2021.
Co-Organizer of the 28th British Combinatorial Conference (BCC 2021) in Durham, 5-9 July 2021.
PC member of the 18th Workshop on Approximation and Online Algorithms (WAOA) 2020.
Co-Organizer of the Dagstuhl Seminar 21171 "Temporal Graphs: Structure, Algorithms, Applications", Dagstuhl, Germany, 25-30 April 2021.
Co-Organizer of the ICALP 2020 satellite workshop Algorithmic Aspects of Temporal Graphs III, Saarbrücken, Germany, Tuesday 7 July 2020.
Co-Organizer of the ICALP 2019 satellite workshop Algorithmic Aspects of Temporal Graphs II, Patras, Greece, Monday 8 July 2019.
Co-Organizer of the joint BCTCS & AlgoUK 2019 meeting in Durham, 15-17 March 2019. [poster]
Co-Organizer of the ICALP 2018 satellite workshop Algorithmic Aspects of Temporal Graphs, Prague, Czech Republic, Monday 9 July 2018.
PC member of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS) 2018.
PC member of the 14th International Symposium on Pervasive Systems, Algorithms, and Networks (I-SPAN) 2017.
Author of the article ``Polynomial Fixed-Parameter Algorithms'', about the research topic ``FPT inside P'', in the Newsletter of the Parameterized Complexity Community, December 2015, Vol. 11, no. 2.
PC member of the 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS) 2015.
PC member of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG) 2014.
PC member of the 8th International Conference on Algorithms and Complexity (CIAC) 2013.

Research Projects and Grants

2017-2020: Principal Investigator (PI) of the EPSRC grant EP/P020372/1, Algorithmic Aspects of Temporal Graphs.
2013-2015: Principal Investigator (PI) of the EPSRC grant EP/K022660/1 (personal grant), Algorithmic Aspects of Intersection Graph Models.
2011-2013: Co-Investigator (CI) of the EPSRC grant EP/G043434/1, Algorithmic Aspects of Graph Coloring.
2012-2016: Member of the Research Team of the Computer Technology Institute (CTI), Greece, in the EU Integrated Project (IP) Foundational Research on MULTIlevel ComPLEX Networks and Systems (MULTIPLEX - 317532).

Research Supervision

Ph.D. Supervision of David Fairbairn, Durham University, in progress.
Ph.D. Supervision of David Kutner, Durham University, in progress.
Ph.D. Supervision of Nina Klobas, Durham University, graduated in 2024.
Ph.D. Supervision of Charles Murray, Durham University, graduated in 2021.
Dr. Christoforos Raptopoulos, postdoctoral researcher, January - October 2020, funded by the EPSRC grant EP/P020372/1.
Dr. Viktor Zamaraev, postdoctoral researcher, September 2017 - September 2019, funded by the EPSRC grant EP/P020372/1.
Dr. André Nichterlein, postdoctoral researcher, February 2016 - January 2017, funded by the DAAD Postdoc Scholarship, Germany.
Ph.D. Supervision of Sepehr Meshkinfamfard, Durham University, graduated in 2016.
Ph.D. Supervision of Ioannis Lignos, Durham University, graduated in 2016.
Dr. Archontia Giannopoulou, postdoctoral researcher, January 2014 - January 2015, funded by the EPSRC grant EP/K022660/1.
Dr. Konrad Dabrowski, postdoctoral researcher, November 2012 - April 2013, co-supervised with Daniel Paulusma, funded by the EPSRC grant EP/G043434/1.

External PhD Examination

Peter Stumpf, Unversity of Passau, Germany, 2023 (Supervisor Ignaz Rutter).
Matthew Connor, Unversity of Liverpool, UK, 2023 (Supervisor Othon Michail).
Phong Pham Hong, Unversity of Paris-Sud 11, France, 2018 (Supervisor Yannis Manoussakis).
Bin Sheng, Royal Holloway, University of London, UK, 2017 (Supervisor Gregory Gutin).
Hsiang-Hsuan Liu, University of Liverpool, UK, 2017 (Supervisor Prudence Wong).
Sang-Hyuk Lee, King's College London, UK, 2016 (Supervisor Tomasz Radzik).

Research Interests

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

Awards in International Competitions in Mathematics

June 20, 1998: Athens, Balkan Mathematical Olympiad. First Award (Gold Medal).
November 1, 1998: Bulgarian National Mathematical Competition "Chernorizets Hrabar", organized by the Union of Bulgarian Mathematicians in Sofia. Distinguish Diploma.
April 23, 1999: Mediterranean Mathematics Competition, Peter O' Halloran Memorial. Certificate of Merit.

Publications

Articles in Scientific Encyclopedias

G.B. Mertzios. Multitolerance graphs. Encyclopedia of Algorithms 2015, Springer. [link]
G.B. Mertzios. Approximating fixation probabilities in the generalized Moran process. Encyclopedia of Algorithms 2015, Springer. [link]

Conference Publications

G.B. Mertzios, S. Nikoletseas, C. Raptopoulos, and P.G. Spirakis. The threshold of existence of δ-temporal cliques in random simple temporal graphs. In Proceedings of the 20th International Symposium on Algorithmics of Wireless Networks (ALGOWIN), Egham, London, United Kingdom, September 2024. To appear. [pdf]
N. Klobas, G.B. Mertzios, Hendrik Molter, and P.G. Spirakis. Temporal graph realization from fastest paths. In Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND), Patras, Greece, June 2024, pp. 16:1-16:18. Best student paper. [pdf]
G.B. Mertzios, S. Nikoletseas, C. Raptopoulos, and P.G. Spirakis. Brief Announcement: On the existence of δ-temporal cliques in random simple temporal graphs. In Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND), Patras, Greece, June 2024, pp. 27:1-27:5. [pdf]
N. Klobas, G.B. Mertzios, and P.G. Spirakis. Sliding into the Future: Investigating Sliding Windows in Temporal Graphs. In Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS), Bordeaux, France, August-September 2023, pp. 5:1-5:12. [pdf]
T. Friedetzky, D. Kutner, G.B. Mertzios, I.A. Stewart, and A. Trehan. Payment scheduling in the Interval Debt Model. In Proceedings of the 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Novy Smokovec, Slovakia, January 2023, pp. 267-282. [pdf]
G.B. Mertzios, O. Michail, G. Skretas, P.G. Spirakis, and M. Theofilatos. The complexity of growing a graph. In Proceedings of the 18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS), Potsdam, Germany, September 2022, pp. 123-137. [pdf]
N. Klobas, G.B. Mertzios, H. Molter, and P.G. Spirakis. The complexity of computing optimum labelings for temporal connectivity. In Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS), Vienna, Austria, August 2022, pp. 62:1-62:15. [pdf]
T. Hamm, N. Klobas, G.B. Mertzios, and P.G. Spirakis. The complexity of temporal vertex cover in small-degree graphs. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), Vancouver, BC, Canada, February 2022, pp. 10193-10201. [pdf]
G.B. Mertzios, H. Molter, M. Renken, P.G. Spirakis, and P. Zschoche. The complexity of transitively orienting temporal graphs. In Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS), Tallinn, Estonia, August 2021, pp. 75:1-75:18. [pdf]
N. Klobas, G.B. Mertzios, H. Molter, R. Niedermeier, and P. Zschoche. Interference-free walks in time: temporally disjoint paths. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), Montreal, Canada, August 2021, pp. 4090-4096. [pdf]
K. Heeger, D. Hermelin, G.B. Mertzios, H. Molter, R. Niedermeier, and D. Shabtay. Equitable scheduling on a single machine. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), Vancouver, Canada, February 2021, pp. 11818-11825. [pdf]
A. Deligkas, G.B. Mertzios, P.G. Spirakis, and V. Zamaraev. Exact and approximate algorithms for computing a second Hamiltonian cycle. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), Prague, Czech Republic, August 2020, pp. 27:1-27:13. [pdf]
G.B. Mertzios, H. Molter, R. Niedermeier, V. Zamaraev, P. Zschoche. Computing maximum matchings in temporal graphs. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS), Montpellier, France, March 2020, pp. 27:1-27:14. [pdf]
J. Enright, K. Meeks, G.B. Mertzios, and V. Zamaraev. Deleting edges to restrict the size of an epidemic in temporal networks. In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aachen, Germany, August 2019, pp. 57:1-57:15. [pdf]
E.C. Akrida, G.B. Mertzios, S. Nikoletseas, C. Raptopoulos, P.G. Spirakis and V. Zamaraev. How fast can we reach a target vertex in stochastic temporal graphs? In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), Patras, Greece, July 2019, pp. 131:1-131:14. [pdf]
E.C. Akrida, G.B. Mertzios, and P.G. Spirakis. The temporal explorer who returns to the base. In Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC), Rome, Italy, May 2019, pp. 13-24. [pdf]
G.B. Mertzios, H. Molter, and V. Zamaraev. Sliding window temporal graph coloring. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), Honolulu, Hawaii, USA, January-February 2019, pp. 7667-7674. [pdf]
E.C. Akrida, G.B. Mertzios, P.G. Spirakis, and V. Zamaraev. Temporal vertex cover with a sliding time window. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), Prague, Czech Republic, July 2018, pp. 148:1-148:14. [pdf]
T. Fluschnik, G.B. Mertzios, and A. Nichterlein. Kernelization lower bounds for finding constant-size subgraphs. In Proceedings of the 14th Conference on Computability in Europe (CiE), Kiel, Germany, August 2018, pp. 183-193. [pdf]
A. Deligkas, G.B. Mertzios, and P.G. Spirakis. Binary search in graphs revisited. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS), Aalborg, Denmark, August 2017, pp. 20:1-20:14. [pdf]
G.B. Mertzios, A. Nichterlein, and R. Niedermeier. The power of linear-time data reduction for maximum matching. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS), Aalborg, Denmark, August 2017, pp. 46:1-46:14. [pdf]
T. Fluschnik, C. Komusiewicz, G.B. Mertzios, A. Nichterlein, R. Niedermeier, and N. Talmon. When can graph hyperbolicity be computed in linear time? In Proceedings of the Algorithms and Data Structures Symposium (WADS), St. John's, NL, Canada, July 2017, pp. 397-408. [pdf]
A. Deligkas, G.B. Mertzios, and P.G. Spirakis. The computational complexity of weighted greedy matching. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), San Francisco, California, USA, February 2017, pp. 466-474. [pdf]
R.v. Bevern, T. Fluschnik, G.B. Mertzios, H. Molter, M. Sorge, and O. Suchy. Finding secluded places of special interest in graphs. In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC), Aarhus, Denmark, August 2016, pp. 5:1-5:16. [pdf]
G.B. Mertzios, S.E. Nikoletseas, C.L. Raptopoulos, and P.G. Spirakis. Stably computing order statistics with arithmetic population protocols. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), Krakow, Poland, August 2016, pp. 68:1-68:14. [pdf]
P.A. Golovach and G.B. Mertzios. Graph editing to a given degree sequence. In Proceedings of the 11th International Computer Science Symposium in Russia (CSR), St. Petersburg, Russia, June 2016, pp. 177-191. [pdf]
A.C. Giannopoulou, G.B. Mertzios, and R. Niedermeier. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC), Patras, Greece, September 2015, pp. 102-113. [pdf]
E.C. Akrida, L. Gasieniec, G.B. Mertzios and P.G. Spirakis. On temporally connected graphs of small cost. In Proceedings of the 13th Workshop on Approximation and Online Algorithms (WAOA), Patras, Greece, September 2015. pp. 84-96. [pdf]
A.C. Giannopoulou and G.B. Mertzios. New geometric representations and domination problems on tolerance and multitolerance graphs. In Proceedings of the 32nd Symposium on Theoretical Aspects of Computer Science (STACS), Munich, Germany, March 2015, pp. 354-366. [pdf]
F. Foucaud, G.B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov. Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. In Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Munich, Germany, June 2015, pp. 456-471. [pdf]
J. Diaz and G.B. Mertzios. Minimum bisection is NP-hard on unit disk graphs. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS), Part II, Budapest, Hungary, August 2014, pp. 251-262. [pdf]
S. Felsner, K. Knauer, G.B. Mertzios, and T. Ueckerdt. Intersection graphs of L-shapes and segments in the plane. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS), Part II, Budapest, Hungary, August 2014, pp. 299-310. [pdf]
G.B. Mertzios, S.E. Nikoletseas, C.L. Raptopoulos, and P.G. Spirakis. Determining majority in networks with local interactions and very small local memory. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Copenhagen, Denmark, July 2014. pp. 871-882. [pdf]
E.C. Akrida, L. Gasieniec, G.B. Mertzios, and P.G. Spirakis. Ephemeral networks with random availability of links: Diameter and connectivity. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Prague, Czech Republic, June 2014, pp. 267-276. [pdf]
G.B. Mertzios. The recognition of simple-triangle graphs and of linear-interval orders is polynomial. In Proceedings of the 21st European Symposium on Algorithms (ESA), Sophia Antipolis, France, September 2013, pp. 719-730. [pdf]
S. Felsner, G.B. Mertzios, and I. Mustata. On the recognition of four-directional orthogonal ray graphs. In Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS), Klosterneuburg, Austria, August 2013, pp. 373-384. [pdf]
G.B. Mertzios and P.G. Spirakis. Strong bounds for evolution in networks. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Riga, Latvia, July 2013, pp. 669-680. [pdf]
G.B. Mertzios, O. Michail, I. Chatzigiannakis, and P.G. Spirakis. Temporal network optimization subject to connectivity constraints. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Riga, Latvia, July 2013, pp. 657-668. [pdf]
G.B. Mertzios and P.G. Spirakis. Algorithms and almost tight results for 3-colorability of small diameter graphs. In Proceedings of the 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Spindleruv Mlyn, Czech Republic, January 2013, pp. 332-343. [pdf]
N. Bousquet, D. Goncalves, G.B. Mertzios, C. Paul, I. Sau, and S. Thomasse. Parameterized domination in circle graphs. In Proceedings of the 38th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Ramat Rachel, Jerusalem, Israel, June 2012, pp. 308-319. [pdf]
G.B. Mertzios, M. Shalom, A. Voloshin, P.W.H. Wong, and S. Zaks. Optimizing busy time on parallel machines. In Proceedings of the 26th IEEE International Parallel & Distributed Processing Symposium (IEEE IPDPS), Shanghai, China, May 2012. pp. 238-248. [pdf]
J. Diaz, L.A. Goldberg, G.B. Mertzios, D. Richerby, M. Serna, and P.G. Spirakis. Approximating fixation probabilities in the generalized Moran process. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), Kyoto, Japan, January 2012, pp. 954-960. [pdf]
G.B. Mertzios, S.E. Nikoletseas, C.L. Raptopoulos, and P.G. Spirakis. Natural models for evolution on networks. In Proceedings of the 7th Workshop on Internet & Network Economics (WINE), Singapore, December 2011, pp. 290-301. [pdf]
G.B. Mertzios, M. Shalom, P.W.H. Wong, and S. Zaks. Online regenerator placement. In Proceedings of the 15th International Conference on Principles of Distributed Systems (OPODIS), Toulouse, France, December 2011, pp. 4-17. [pdf]
G.B. Mertzios and I. Bezakova. Computing and counting longest paths on circular-arc graphs in polynomial time. In Proceedings of the VI Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), Bariloche, Argentina, March 2011, pp. 148-153. [pdf]
G.B. Mertzios. The recognition of triangle graphs. In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), Dortmund, Germany, March 2011, pp. 591-602. [pdf]
G.B. Mertzios. An intersection model for multitolerance graphs: Efficient algorithms and hierarchy. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, California USA, January 2011, pp. 1306-1317. [pdf]
G.B. Mertzios and S. Zaks. On the intersection of tolerance and cocomparability graphs. In Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC), Jeju Island, Korea, December 2010, Volume 1, pp. 230-240. [pdf]
G.B. Mertzios, I. Sau, M. Shalom, and S. Zaks. Placing regenerators in optical networks to satisfy multiple sets of requests. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), Bordeaux, France, July 2010, Volume 2, pp. 333-344. Best paper award of Track C. [pdf]
G.B. Mertzios, I. Sau, and S. Zaks. The recognition of tolerance and bounded tolerance graphs. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), Nancy, France, March 2010, pp. 585-596. [pdf]
K. Ioannidou, G.B. Mertzios, and S.D. Nikolopoulos. The longest path problem is polynomial on interval graphs. In Proceedings of the 34st International Symposium on Mathematical Foundations of Computer Science (MFCS), Novy Smokovec, High Tatras, Slovakia, August 2009, pp. 403-414. [pdf]
G.B. Mertzios, I. Sau, and S. Zaks. A new intersection model and improved algorithms for tolerance graphs. In Proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Montpellier, France, June 2009, pp. 285-295. [pdf]
G.B. Mertzios and W. Unger. A parameterized algorithm for the preemptive scheduling of equal-length jobs. In Proceedings of the 2nd International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS), Orlando, FL, USA, July 2009, pp. 20-27. [pdf]
G.B. Mertzios. Fast convergence of routing games with splittable flows. In Proceedings of the 2nd International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS), Orlando, FL, USA, July 2009, pp. 28-33. [pdf]
G.B. Mertzios and W. Unger. An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs. In Proceedings of the 19th International Workshop on Combinatorial Algorithms (IWOCA), Nagoya, Japan, September 2008, pp. 197-211. [pdf]
G.B. Mertzios and W. Unger. The friendship problem on graphs. In Proceedings of the 1st International Conference on Relations, Orders and Graphs: Interaction with Computer Science (ROGICS), Mahdia, Tunisia, May 2008, pp. 152-158. [pdf]
D.A. Karras and G. Mertzios. Discretization schemes and numerical approximations of PDE impainting models and a comparative evaluation on novel real world MRI reconstruction applications. In Proceedings of the International Workshop on Imaging Systems and Techniques (IEEE IST 2004), Stresa, Italy, 14 May 2004, pp. 153-158. [pdf]
G.C. Giakos, N. Patnekar, S. Sumrain, L. Fraiwan, V. Kumar and G.B. Mertzios. A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up. In Proceedings of the IEEE Instrumentation and Measurement Technology Conference (IMTC 2003), Vail, CO, USA, 20-22 May 2003, pp. 1622-1626. [pdf]

Journal Publications

G.B. Mertzios, O. Michail, G. Skretas, P.G. Spirakis, and M. Theofilatos. The complexity of growing a graph. Journal of Computer and System Sciences, 147, pp. 103587, 2025. [pdf]
N. Klobas, G.B. Mertzios, H. Molter, and P.G. Spirakis. The complexity of computing optimum labelings for temporal connectivity. Journal of Computer and System Sciences, 146, pp. 103564, 2024. [pdf]
A. Deligkas, G.B. Mertzios, P.G. Spirakis, and V. Zamaraev. Approximate and randomized algorithms for computing a second Hamiltonian cycle. Algorithmica, 86(9), pp. 2766-2785, 2024. [pdf]
A.S. Himmel, G.B. Mertzios, A. Nichterlein, and R. Niedermeier. Fast parameterized preprocessing for polynomial-time solvable graph problems. Communications of the ACM, 67(4), pp. 70-79, 2024. [pdf]
M. Gadouleau, N. Harms, G.B. Mertzios, and V. Zamaraev. Graphs with minimum fractional domatic number. Discrete Applied Mathematics, 343, pp. 140-148, 2024. [pdf]
G.B. Mertzios, H. Molter, R. Niedermeier, V. Zamaraev, and P. Zschoche. Computing maximum matchings in temporal graphs. Journal of Computer and System Sciences, 137, pp. 1-19, 2023. [pdf]
N. Klobas, G.B. Mertzios, H. Molter, R. Niedermeier, P. Zschoche. Interference-free walks in time: Temporally disjoint paths. Autonomous Agents and Multi-Agent Systems, 37(1), 2023. [pdf]
K. Heeger, D. Hermelin, G.B. Mertzios, H. Molter, R. Niedermeier, and D. Shabtay. Equitable scheduling on a single machine. Journal of Scheduling, 26(2), pp. 209-225, 2023. [pdf]
E.C. Akrida, G.B. Mertzios, P.G. Spirakis, and C. Raptopoulos. The temporal explorer who returns to the base. Journal of Computer and System Sciences, 120, pp. 179-193, 2021. [pdf]
G.B. Mertzios, H. Molter, and V. Zamaraev. Sliding window temporal graph coloring. Journal of Computer and System Sciences, 120, pp. 97-115, 2021. [pdf]
J. Enright, K. Meeks, G.B. Mertzios, and V. Zamaraev. Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences, 119, pp. 60-77, 2021. [pdf]
G.B. Mertzios, A. Nichterlein, and R. Niedermeier. The power of linear-time data reduction for maximum matching. Algorithmica, 82(12), pp. 3521-3565, 2020. [pdf]
E.C. Akrida, G.B. Mertzios, S. Nikoletseas, C. Raptopoulos, P.G. Spirakis and V. Zamaraev. How fast can we reach a target vertex in stochastic temporal graphs? Journal of Computer and System Sciences, 114, pp. 65-83, 2020. [pdf]
E.C. Akrida, G.B. Mertzios, P.G. Spirakis, and V. Zamaraev. Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107, pp. 108-123, 2020. [pdf]
G.B. Mertzios, A. Nichterlein, and R. Niedermeier. A linear-time algorithm for maximum-cardinality matching on cocomparability graphs. SIAM Journal on Discrete Mathematics, 32(4), pp. 2820-2835, 2019. [pdf]
T. Fluschnik, C. Komusiewicz, G.B. Mertzios, A. Nichterlein, R. Niedermeier, and N. Talmon. When can graph hyperbolicity be computed in linear time? Algorithmica, 81(5), pp. 2016-2045, 2019. [pdf]
A. Deligkas, G.B. Mertzios, and P.G. Spirakis. Binary search in graphs revisited. Algorithmica, 81(5), pp. 1757-1780, 2019. [pdf]
G.B. Mertzios, O. Michail, and P.G. Spirakis. Temporal network optimization subject to connectivity constraints. Algorithmica, 81(4), pp. 1416-1449, 2019. [pdf]
G.B. Mertzios and P.G. Spirakis. Strong bounds for evolution in networks. Journal of Computer and System Sciences, 97, pp. 60-82, 2018. [pdf]
R.v. Bevern, T. Fluschnik, G.B. Mertzios, H. Molter, M. Sorge, and O. Suchy. The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs. Discrete Optimization, 30, pp. 20-50, 2018. [pdf]
A.C. Giannopoulou, G.B. Mertzios, and R. Niedermeier. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theoretical Computer Science, 689, pp. 67-95, 2017. [pdf]
E.C. Akrida, L. Gasieniec, G.B. Mertzios and P.G. Spirakis. The complexity of optimal design of temporally connected graphs. Theory of Computing Systems, 61(3), pp. 907-944, 2017. [pdf]
J. Diaz and G.B. Mertzios. Minimum bisection is NP-hard on unit disk graphs. Information and Computation, 256, pp. 83-92, 2017. [pdf]
G.B. Mertzios, M. Shalom, P.W.H. Wong, and S. Zaks. Online regenerator placement. Theory of Computing Systems, 61(3), pp. 739-754, 2017. [pdf]
F. Foucaud, G.B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica, 78(3), pp. 914-944, 2017. [pdf]
F. Foucaud, G.B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds. Theoretical Computer Science, 668, pp. 43-58, 2017. [pdf]
P.A. Golovach and G.B. Mertzios. Graph editing to a given degree sequence. Theoretical Computer Science, 665, pp. 1-12, 2017. [pdf]
G.B. Mertzios, S.E. Nikoletseas, C.L. Raptopoulos, and P.G. Spirakis. Determining majority in networks with local interactions and very small local memory. Distributed Computing, 30(1), pp. 1-16, 2017. [pdf]
A.C. Giannopoulou and G.B. Mertzios. New geometric representations and domination problems on tolerance and multitolerance graphs. SIAM Journal on Discrete Mathematics, 30(3), pp. 1685-1725, 2016. [pdf]
E.C. Akrida, L. Gasieniec, G.B. Mertzios, and P.G. Spirakis. Ephemeral networks with random availability of links: The case of fast networks. Journal of Parallel and Distributed Computing, 87, pp. 109-120, 2016. [pdf]
G.B. Mertzios and P.G. Spirakis. Algorithms and almost tight results for 3-colorability of small diameter graphs. Algorithmica, 74(1), pp. 385-414, 2016. [pdf]
G.B. Mertzios and W. Unger. The friendship problem on graphs. Multiple-Valued Logic and Soft Computing, 27(2-3), pp. 275-285, 2016. [pdf]
S. Felsner, K. Knauer, G.B. Mertzios, and T. Ueckerdt. Intersection graphs of L-shapes and segments in the plane. Discrete Applied Mathematics, 206, pp. 48-55, 2016. [pdf]
G.B. Mertzios and S. Zaks. On the intersection of tolerance and cocomparability graphs. Discrete Applied Mathematics, 199, pp. 46-88, 2016. [pdf]
G.B. Mertzios. The recognition of simple-triangle graphs and of linear-interval orders is polynomial. SIAM Journal on Discrete Mathematics, 29(3), pp. 1150-1185, 2015. [pdf]
G.B. Mertzios, M. Shalom, A. Voloshin, P.W.H. Wong, and S. Zaks. Optimizing Busy Time on Parallel Machines. Theoretical Computer Science, 562, pp. 524-541, 2015. [pdf]
G.B. Mertzios. An intersection model for multitolerance graphs: Efficient algorithms and hierarchy. Algorithmica, 69(3), pp. 540-581, 2014. [pdf]
J. Diaz, L.A. Goldberg, G.B. Mertzios, D. Richerby, M. Serna, and P.G. Spirakis. Approximating fixation probabilities in the generalized Moran process. Algorithmica, 69(1), pp. 78-91, 2014. [pdf]
N. Bousquet, D. Goncalves, G.B. Mertzios, C. Paul, I. Sau, and S. Thomasse. Parameterized domination in circle graphs. Theory of Computing Systems, 54(1), pp. 45-72, 2014. [pdf]
G.B. Mertzios and I. Bezakova. Computing and counting longest paths on circular-arc graphs in polynomial time. Discrete Applied Mathematics, 164(2), pp. 383-399, 2014. [pdf]
J. Diaz, L.A. Goldberg, G.B. Mertzios, D. Richerby, M. Serna, and P.G. Spirakis. On the Fixation Probability of Superstars. Proceedings of the Royal Society A, 469(2156), pp. 193-203, 2013. [main pdf: 11 pages], Data Supplement: [supplement pdf: 23 pages] and [C code]
G.B. Mertzios, S.E. Nikoletseas, C.L. Raptopoulos, and P.G. Spirakis. Natural models for evolution on networks. Theoretical Computer Science, 477, pp. 76-95, 2013. [pdf]
G.B. Mertzios and D.G. Corneil. A simple polynomial algorithm for the longest path problem on cocomparability graphs. SIAM Journal on Discrete Mathematics, 26(3), pp. 940-963, 2012. [pdf]
G.B. Mertzios. The recognition of triangle graphs. Theoretical Computer Science, 438, pp. 34-47, 2012. [pdf]
G.B. Mertzios, I. Sau, M. Shalom, and S. Zaks. Placing regenerators in optical networks to satisfy multiple sets of requests. IEEE/ACM Transactions on Networking, 20(6), pp. 1870-1879, 2012. [pdf]
G.B. Mertzios, I. Sau, and S. Zaks. The recognition of tolerance and bounded tolerance graphs. SIAM Journal on Computing, 40(5), pp. 1234-1257, 2011. [pdf]
G.B. Mertzios and D.G. Corneil. Vertex splitting and the recognition of trapezoid graphs. Discrete Applied Mathematics, 159(11), pp. 1131-1147, 2011. [pdf]
K. Ioannidou, G.B. Mertzios, and S.D. Nikolopoulos. The longest path problem has a polynomial solution on interval graphs. Algorithmica, 61(2), pp. 320-341, 2011. [pdf]
P.S. Efraimidis, L. Tsavlidis, and G.B. Mertzios. Window-games between TCP flows. Theoretical Computer Science, 411(31-33), pp. 2798-2817, 2010. [pdf]
G.B. Mertzios and W. Unger. Preemptive scheduling of equal-length jobs in polynomial time. Advances in Combinatorial Algorithms I, Mathematics in Computer Science, Birkhäuser / Springer, 3(1), pp. 73-84, 2010. [pdf]
G.B. Mertzios and W. Unger. An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs. Advances in Combinatorial Algorithms I, Mathematics in Computer Science, Birkhäuser / Springer, 3(1), pp. 85-96, 2010. [pdf]
G.B. Mertzios, I. Sau, and S. Zaks. A new intersection model and improved algorithms for tolerance graphs. SIAM Journal on Discrete Mathematics, 23(4), pp. 1800-1813, 2009. [pdf]
D.A. Karras and G.B. Mertzios. New PDE-based methods for image enhancement using SOM and Bayesian inference in various discretization schemes, Measurement Science and Technology, 20, 2009. [pdf]
G.B. Mertzios. A matrix characterization of interval and proper interval graphs. Applied Mathematics Letters, 21(4), pp. 332-337, 2008. [pdf]
G.B. Mertzios. Solution of parameter-varying linear matrix inequalities in Toeplitz form. Journal of Applied Functional Analysis, 1(2), pp. 131-152, 2006. [pdf]
G.C. Giakos, L. Fraiwan, N. Patnekar, S. Sumrain, G.B. Mertzios, and S. Periyathamby. A sensitive optical polarimetric imaging technique for surface defects detection of aircraft turbine engines. Special Joint Issue - IEEE Transactions on Instrumentation and Measurement and IEEE/OSA Journal of Lightwave Technology, 53(1), pp. 216-222, 2004. [pdf]

Theses

Diploma Thesis: Improved Algorithms for the Constant-Excess Subgraph Problem and Applications, Technische Universität München, December 2004
Ph.D. Thesis: Combinatorial Optimization and Recognition of Graph Classes with Applications to Related Models, RWTH Aachen University, November 2009 [pdf]

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Dr. George B. Mertzios Associate Professor