Since March 2017: Associate Professor in Computer Science at the
Algorithms and Complexity Research Group,
School of Engineering and Computing Sciences, Durham University, UK
October 2015 - February 2017: Senior Lecturer in Computer Science at the
Algorithms and Complexity Research Group,
School of Engineering and Computing Sciences, Durham University, UK
September 2011 - September 2015: Lecturer in Computer Science at the
Algorithms and Complexity Research Group,
School of Engineering and Computing Sciences, Durham University, UK
Dr. Viktor Zamaraev, postdoctoral researcher, September 2017 - July 2020, funded by the EPSRC grant EP/P020372/1.
Dr. André Nichterlein, postdoctoral researcher, February 2016 - January 2017, funded by the DAAD Postdoc Scholarship, Germany.
Dr. Archontia Giannopoulou, postdoctoral researcher, January 2015 - January 2016, 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.
Ph.D. Supervision of Sepehr Meshkinfamfard, Durham University, graduated in 2016.
Ph.D. Supervision of Ioannis Lignos, Durham University, graduated in 2016.
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
E.C. Akrida, G.B. Mertzios, P.G. Spirakis, and V. Zamaraev.
Temporal vertex covers and sliding time windows.
In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP),
Prague, Czech Republic, July 2018. To appear.
[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, 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 and P.G. Spirakis.
Strong bounds for evolution in networks.
Journal of Computer and System Sciences. To appear. [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. To appear. [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.