Intersection Graphs of L-Shapes and Segments in the Plane (2014)
Book Chapter
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

An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: ⌊,⌈,⌋ and ⌉. A k-bend path is a simple path in the plane, whose direction changes k times from horizontal to vertical. If a graph adm... Read More about Intersection Graphs of L-Shapes and Segments in the Plane.

Determining Majority in Networks with Local Interactions and Very Small Local Memory (2014)
Book Chapter
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

We study here the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types (states). The vertices may have a few additional possible states and can interact in pairs only if the... Read More about Determining Majority in Networks with Local Interactions and Very Small Local Memory.

Minimum Bisection Is NP-hard on Unit Disk Graphs (2014)
Book Chapter
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

In this paper we prove that the Min-Bisection problem is NP-hard on unit disk graphs, thus solving a longstanding open question.

Approximating Fixation Probabilities in the Generalized Moran Process (2014)
Book Chapter
Mertzios, G. (2014). Approximating Fixation Probabilities in the Generalized Moran Process. In M. Kao (Ed.), Encyclopedia of algorithms (1-6). Springer Verlag. https://doi.org/10.1007/978-3-642-27848-8_596-1

Problem Definition Population and evolutionary dynamics have been extensively studied, usually with the assumption that the evolving population has no spatial structure. One of the main models in this area is the Moran process [17]. The initial popul... Read More about Approximating Fixation Probabilities in the Generalized Moran Process.

On the intersection of tolerance and cocomparability graphs (2014)
Journal Article
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

Tolerance graphs have been extensively studied since their introduction, due to their interesting structure and their numerous applications, as they generalize both interval and permutation graphs in a natural way. It has been conjectured by Golumbic... Read More about On the intersection of tolerance and cocomparability graphs.

Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs (2014)
Journal Article
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

The 3-coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter 4. Moreover, assuming the Exponential Time Hypothesis (ETH), 3-coloring cannot be solved in... Read More about Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs.

Multitolerance Graphs (2014)
Book Chapter
Mertzios, G. (2014). Multitolerance Graphs. In M. Kao (Ed.), Encyclopedia of algorithms (1-6). Springer Verlag. https://doi.org/10.1007/978-3-642-27848-8_684-1

Problem Definition Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. A graph G = (V, E) on n vertices is a tolerance graph if there exists a collection I = { Iv... Read More about Multitolerance Graphs.

Ephemeral networks with random availability of links: diameter and connectivity (2014)
Conference Proceeding
Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2014). Ephemeral networks with random availability of links: diameter and connectivity. In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures (267-276). https://doi.org/10.1145/2612669.2612693

In this work we consider temporal networks, the links of which are available only at random times (randomly available temporal networks). Our networks are {\em ephemeral}: their links appear sporadically, only at certain times, within a given maximum... Read More about Ephemeral networks with random availability of links: diameter and connectivity.

Approximating Fixation Probabilities in the Generalized Moran Process (2014)
Journal Article
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

We consider the Moran process, as generalized by Lieberman et al. (Nature 433:312–316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability pro... Read More about Approximating Fixation Probabilities in the Generalized Moran Process.

Computing and counting longest paths on circular-arc graphs in polynomial time (2014)
Journal Article
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

The longest path problem asks for a path with the largest number of vertices in a given graph. In contrast to the Hamiltonian path problem, until recently polynomial algorithms for the longest path problem were known only for small graph classes, suc... Read More about Computing and counting longest paths on circular-arc graphs in polynomial time.

Parameterized Domination in Circle Graphs (2014)
Journal Article
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

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51–63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of ou... Read More about Parameterized Domination in Circle Graphs.