Dr George Mertzios' Outputs (8)

Online Regenerator Placement (2011)
Presentation / Conference Contribution
Mertzios, G., Shalom, M., Wong, P., & Zaks, S. (2011, December). Online Regenerator Placement. Presented at 15th International Conference on Principles of Distributed Systems (OPODIS), Toulouse, France

Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most d hops, for some given positive integer d. A regenerator can serve only one ligh... Read More about Online Regenerator Placement.

Natural Models for Evolution on Networks (2011)
Presentation / Conference Contribution
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2011, December). Natural Models for Evolution on Networks. Presented at 7th Workshop on Internet & Network Economics (WINE), Singapore

Evolutionary dynamics have been traditionally studied in the context of homogeneous populations, mainly described by the Moran process [15]. Recently, this approach has been generalized in [13] by arranging individuals on the nodes of a network (in g... Read More about Natural Models for Evolution on Networks.

The longest path problem has a polynomial solution on interval graphs (2011)
Journal Article
Ioannidou, K., Mertzios, G., & Nikolopoulos, S. (2011). The longest path problem has a polynomial solution on interval graphs. Algorithmica, 61(2), 320-341. https://doi.org/10.1007/s00453-010-9411-3

The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamilton... Read More about The longest path problem has a polynomial solution on interval graphs.

The recognition of tolerance and bounded tolerance graphs (2011)
Journal Article
Mertzios, G., Sau, I., & Zaks, S. (2011). The recognition of tolerance and bounded tolerance graphs. SIAM Journal on Computing, 40(5), 1234-1257. https://doi.org/10.1137/090780328

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its num... Read More about The recognition of tolerance and bounded tolerance graphs.

Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time (2011)
Presentation / Conference Contribution
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.), . https://doi.org/10.1016/j.endm.2011.05.038

The longest path problem asks for a path with the largest number of vertices in a given graph. The first polynomial time algorithm (with running time O(n4)) has been recently developed for interval graphs. Even though interval and circular-arc graphs... Read More about Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time.

Vertex Splitting and the Recognition of Trapezoid Graphs (2011)
Journal Article
Mertzios, G., & Corneil, D. (2011). Vertex Splitting and the Recognition of Trapezoid Graphs. Discrete Applied Mathematics, 159(11), 1131-1147. https://doi.org/10.1016/j.dam.2011.03.023

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapez... Read More about Vertex Splitting and the Recognition of Trapezoid Graphs.

An intersection model for multitolerance graphs: Efficient algorithms and hierarchy (2011)
Presentation / Conference Contribution
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 (1306-1317)

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in con ict. This class of graphs has attracted many research eorts, mainly due to its interesting structure and its numerous... Read More about An intersection model for multitolerance graphs: Efficient algorithms and hierarchy.

The Recognition of Triangle Graphs (2011)
Presentation / Conference Contribution
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 (591-602). https://doi.org/10.4230/lipics.stacs.2011.591

Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L_{1} and L_{2} of the plane. Strictly between permutation and trapezoid graphs lie the simple-triangle graphs... Read More about The Recognition of Triangle Graphs.