Placing regenerators in optical networks to satisfy multiple sets of requests (2012)
Journal Article
Mertzios, G., Sau, I., Shalom, M., & Zaks, S. (2012). Placing regenerators in optical networks to satisfy multiple sets of requests. IEEE/ACM Transactions on Networking, 20(6), 1870-1879. https://doi.org/10.1109/tnet.2012.2186462

The placement of regenerators in optical networks has become an active area of research during the last few years. Given a set of lightpaths in a network $G$ and a positive integer $d$ , regenerators must be placed in such a way that in any lightpath... Read More about Placing regenerators in optical networks to satisfy multiple sets of requests.

Approximating Fixation Probabilities in the Generalized Moran Process (2012)
Conference Proceeding
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 (954-960). https://doi.org/10.1137/1.9781611973099.76

We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (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 pr... Read More about Approximating Fixation Probabilities in the Generalized Moran Process.

A simple polynomial algorithm for the longest path problem on cocomparability graphs (2012)
Journal Article
Mertzios, G., & Corneil, D. (2012). A simple polynomial algorithm for the longest path problem on cocomparability graphs. SIAM Journal on Discrete Mathematics, 26(3), 940-963. https://doi.org/10.1137/100793529

Given a graph $G$, the longest path problem asks to compute a simple path of $G$ with the largest number of vertices. This problem is the most natural optimization version of the well-known and well-studied Hamiltonian path problem, and thus it is NP... Read More about A simple polynomial algorithm for the longest path problem on cocomparability graphs.

Parameterized Domination in Circle Graphs (2012)
Conference Proceeding
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 (308-319). https://doi.org/10.1007/978-3-642-34611-8_31

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

The recognition of triangle graphs (2012)
Journal Article
Mertzios, G. (2012). The recognition of triangle graphs. Theoretical Computer Science, 438, 34-47. https://doi.org/10.1016/j.tcs.2012.02.042

Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L1 and L2 of the plane. This subclass of perfect graphs has received considerable attention as it generalizes i... Read More about The recognition of triangle graphs.

Optimizing busy time on parallel machines (2012)
Conference Proceeding
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) (238-248). https://doi.org/10.1109/ipdps.2012.31

We consider the following fundamental scheduling problem in which the input consists of n jobs to be scheduled on a set of identical machines of bounded capacity g (which is the maximal number of jobs that can be processed simultaneously by a single... Read More about Optimizing busy time on parallel machines.