Maria Serna

Prof. Dr. Maria Serna

orcid

Research Focus & Metrics

Academic Career Length

32Years (1995-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 September 2002 in ACM Computing Surveys
Verified
Journal Article
Open access
JDJosep Díaz
Josep Díaz
JPJordi Petit
Jordi Petit
MSMaria Serna
Maria Serna
Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a linear layout of an input graph in such way that a certain objective cost is optimized. This survey considers their motivation, complexity, approximation properties, upper and lower bounds, heuristics and probabilistic analysis on random graphs. The result is a complete view of the current state of the art with respect to layout problems from an algorithmic point of view.

1 July 2005 in Journal of Algorithms
Verified
Journal Article
Closed access
DTDimitrios M. Thilikos
Dimitrios M. Thilikos
MSMaria Serna
Maria Serna
HBHans L. Bodlaender
Hans L. Bodlaender

1 June 2002 in Theoretical Computer Science
Verified
Journal Article
Closed access
JDJosep Díaz
Josep Díaz
MSMaria Serna
Maria Serna
DTDimitrios M. Thilikos
Dimitrios M. Thilikos

28 November 2012 in Algorithmica
Verified
Journal Article
Closed access
PDF file
JDJosep Díaz
Josep Díaz
LGLeslie Ann Goldberg
Leslie Ann Goldberg
GMGeorge B. Mertzios
George B. Mertzios
DRDavid Richerby
David Richerby
MSMaria Serna
Maria Serna
PSPaul G. Spirakis
Paul G. Spirakis

1 July 2005 in Journal of Algorithms
Verified
Journal Article
Closed access
DTDimitrios M. Thilikos
Dimitrios M. Thilikos
MSMaria Serna
Maria Serna
HBHans L. Bodlaender
Hans L. Bodlaender

12 January 2016 in Random Structures & Algorithms
Verified
Journal Article
Open access
PDF file
JDJosep Díaz
Josep Díaz
LGLeslie Ann Goldberg
Leslie Ann Goldberg
DRDavid Richerby
David Richerby
MSMaria Serna
Maria Serna
The Moran process models the spread of mutations in populations on graphs. We investigate the absorption time of the process, which is the time taken for a mutation introduced at a randomly chosen vertex to either spread to the whole population, or to become extinct. It is known that the expected absorption time for an advantageous mutation is on an n-vertex undirected graph, which allows the behaviour of the process on undirected graphs to be analysed using the Markov chain Monte Carlo method. We show that this does not extend to directed graphs by exhibiting an infinite family of directed graphs for which the expected absorption time is exponential in the number of vertices. However, for regular directed graphs, we show that the expected absorption time is and . We exhibit families of graphs matching these bounds and give improved bounds for other families of graphs, based on isoperimetric number. Our results are obtained via stochastic dominations which we demonstrate by establishing a coupling in a related continuous-time model. The coupling also implies several natural domination results regarding the fixation probability of the original (discrete-time) process, resolving a conjecture of Shakarian, Roos and Johnson. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 137–159, 2016