43 citations · 187 across the 40 of their papers we have counts for
6 papers · 1 filter
Strong Bounds for Evolution in Undirected Graphs
George B. Mertzios, Paul G. Spirakis
This work studies the generalized Moran process, as introduced by Lieberman et al. [Nature, 433:312-316, 2005]. We introduce the parameterized notions of selective amplifiers and s…
The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
George B. Mertzios
Intersection graphs of geometric objects have been extensively studied, both due to their interesting structure and their numerous applications; prominent examples include interval…
On the Intersection of Tolerance and Cocomparability Graphs
George B. Mertzios, Shmuel Zaks
It has been conjectured by Golumbic and Monma in 1984 that the intersection of tolerance and cocomparability graphs coincides with bounded tolerance graphs. The conjecture has been…
Parameterized Domination in Circle Graphs
Nicolas Bousquet, Daniel Gonçalves, George B. Mertzios +3
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…
On the Fixation Probability of Superstars
Josep Diaz, Leslie Ann Goldberg, George B. Mertzios +3
The Moran process models the spread of genetic mutations through a population. A mutant with relative fitness is introduced into a population and the system evolves, either rea…
Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
George B. Mertzios, Paul G. Spirakis
In spite of the extensive studies of the 3-coloring problem with respect to several basic parameters, the complexity status of the 3-coloring problem on graphs with small diameter,…