All Outputs (8)

On the Recognition of Four-Directional Orthogonal Ray Graphs (2013)
Book Chapter
Felsner, S., Mertzios, G., & Mustata, I. (2013). On the Recognition of Four-Directional Orthogonal Ray Graphs. In K. Chatterjee, & J. Sgall (Eds.), Mathematical foundations of computer science 2013 : 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings (373-384). Springer Verlag. https://doi.org/10.1007/978-3-642-40313-2_34

Orthogonal ray graphs are the intersection graphs of horizontal and vertical rays (i.e. half-lines) in the plane. If the rays can have any possible orientation (left/right/up/down) then the graph is a 4-directional orthogonal ray graph (4-DORG). Othe... Read More about On the Recognition of Four-Directional Orthogonal Ray Graphs.

Temporal Network Optimization Subject to Connectivity Constraints (2013)
Book Chapter
Mertzios, G., Michail, O., Chatzigiannakis, I., & Spirakis, P. (2013). Temporal Network Optimization Subject to Connectivity Constraints. In F. V. Fomin, R. Freivalds, M. Kwiatkowska, & D. Peleg (Eds.), Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, proceedings, part II (657-668). Springer Verlag. https://doi.org/10.1007/978-3-642-39212-2_57

In this work we consider temporal networks, i.e. networks defined by a labeling λ assigning to each edge of an underlying graph G a set of discrete time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at w... Read More about Temporal Network Optimization Subject to Connectivity Constraints.

Strong Bounds for Evolution in Networks (2013)
Book Chapter
Mertzios, G., & Spirakis, P. (2013). Strong Bounds for Evolution in Networks. In F. V. Fomin, R. Freivalds, M. Kwiatkowska, & D. Peleg (Eds.), Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, proceedings, part II (669-680). Springer Verlag. https://doi.org/10.1007/978-3-642-39212-2_58

This work extends what is known so far for a basic model of evolutionary antagonism in undirected networks (graphs). More specifically, this work studies the generalized Moran process, as introduced by Lieberman, Hauert, and Nowak [Nature, 433:312-31... Read More about Strong Bounds for Evolution in Networks.

Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs (2013)
Book Chapter
Mertzios, G., & Spirakis, P. (2013). Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs. In P. V. E. Boas, F. C. Groen, G. F. Italiano, J. Nawrocki, & H. Sack (Eds.), SOFSEM 2013 : theory and practice of computer science : 39th international conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 26-31, 2013. Proceedings (332-343). Springer Verlag. https://doi.org/10.1007/978-3-642-35843-2_29

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 can not be solved i... Read More about Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs.

The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial (2013)
Book Chapter
Mertzios, G. (2013). The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial. In H. L. Bodlaender, & G. F. Italiano (Eds.), Algorithms - ESA 2013 : 21st annual European symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings (719-730). Springer Verlag. https://doi.org/10.1007/978-3-642-40450-4_61

Intersection graphs of geometric objects have been extensively studied, both due to their interesting structure and their numerous applications; prominent examples include interval graphs and permutation graphs. In this paper we study a natural graph... Read More about The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial.

On the fixation probability of superstars (2013)
Journal Article
Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2013). On the fixation probability of superstars. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 469(2156), https://doi.org/10.1098/rspa.2013.0193

The Moran process models the spread of genetic mutations through populations. A mutant with relative fitness r is introduced and the system evolves, either reaching fixation (an all-mutant population) or extinction (no mutants). In a widely cited pap... Read More about On the fixation probability of superstars.

Natural models for evolution on networks (2013)
Journal Article
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2013). Natural models for evolution on networks. Theoretical Computer Science, 477, 76-95. https://doi.org/10.1016/j.tcs.2012.11.032

Evolutionary dynamics has been traditionally studied in the context of homogeneous populations, mainly described by the Moran process [P. Moran, Random processes in genetics, Proceedings of the Cambridge Philosophical Society 54 (1) (1958) 60–71]. Re... Read More about Natural models for evolution on networks.

An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy (2013)
Journal Article
Mertzios, G. (2014). An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy. Algorithmica, 69(3), 540-581. https://doi.org/10.1007/s00453-012-9743-2

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs has attracted many research efforts, mainly due to its interesting structure and its numer... Read More about An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy.