María Serna

Generating author description...

All published works

Action	Title	Year	Authors
+ PDF Chat	Rainbow connectivity of multilayered random geometric graphs	2024	Josep Dı́az Öznur Yaşar Diner Marı́a Serna Oriol Serra
+	On Minimum Vertex Bisection of Random d-Regular Graphs	2024	Josep Dı́az Öznur Yaşar Diner Marı́a Serna Oriol Serra
+	The multicolored graph realization problem	2022	Josep Dı́az Öznur Yaşar Diner Marı́a Serna Oriol Serra
+	Playing with Thresholds on the Forward Linear Threshold Rank	2022	María J. Blesa Marı́a Serna
+	On Vertex Bisection Width of Random $d$-Regular Graphs	2022	Josep Dı́az Öznur Yaşar Diner María Serna Oriol Serra
+	The Multicolored Graph Realization Problem	2021	Josep Dı́az Öznur Yaşar Diner Marı́a Serna Oriol Serra
+ PDF Chat	On List k-Coloring Convex Bipartite Graphs	2020	Josep Dı́az Öznur Yaşar Diner Marı́a Serna Oriol Serra
+	On List k-Coloring Convex Bipartite Graphs	2020	Josep Dı́az Öznur Yaşar Diner Marı́a Serna Oriol Serra
+	On List k-Coloring Convex Bipartite Graphs	2020	Josep Dı́az Öznur Yaşar Diner Marı́a Serna Oriol Serra
+	Data-Compression for Parametrized Counting Problems on Sparse Graphs	2018	Eun Jung Kim María Serna Dimitrios M. Thilikos
+	Data-compression for Parametrized Counting Problems on Sparse graphs	2018	Eun Jung Kim Marı́a Serna Dimitrios M. Thilikos
+ PDF Chat	Dimension and codimension of simple games	2016	Sascha Kurz Xavier Molinero Martin Olsen Marı́a Serna
+	Complexity of metric dimension on planar graphs	2016	Josep Dı́az Olli Pottonen Marı́a Serna Erik Jan van Leeuwen
+	Measuring satisfaction in societies with opinion leaders and mediators	2016	Xavier Molinero Fabián Riquelme Marı́a Serna
+	Dimension and codimension of simple games	2016	Sascha Kurz Xavier Molinero Martin Olsen Marı́a Serna
+ PDF Chat	Absorption time of the Moran process	2016	Josep Dı́az Leslie Ann Goldberg David Richerby Marı́a Serna
+	Uncertainty Analysis of Simple Macroeconomic Models Using Angel-Daemon Games	2016	Joaquim Gabarró Marı́a Serna
+ PDF Chat	Dimension and Codimension of Simple Games	2016	Sascha Kurz Xavier Molinero Martin Olsen Marı́a Serna
+ PDF Chat	Randomized Parallel Approximations to Max Flow	2016	Marı́a Serna
+	Measuring satisfaction in societies with opinion leaders and mediators	2016	Xavier Molinero Fabián Riquelme Marı́a Serna
+	Dimension and codimension of simple games	2016	Sascha Kurz Xavier Molinero Martin Olsen Marı́a Serna
+ PDF Chat	On the Stability of Generalized Second Price Auctions with Budgets	2015	Josep Dı́az Ioannis Giotis Lefteris M. Kirousis Evangelos Markakis Marı́a Serna
+	On the Complexity of Trading	2015	Xavier Molinero Martin Olsen Marı́a Serna
+	On the Complexity of Exchanging	2015	Xavier Molinero Martin Olsen Marı́a Serna
+	Stars and Celebrities: A Network Creation Game	2015	Carme Àlvarez María J. Blesa Amalia Duch Arnau Messegué Marı́a Serna
+	Optimizing the Social Cost of Congestion Games by Imposing Variable Delays	2014	Josep Dı́az Ioannis Giotis Lefteris M. Kirousis Yiannis Mourtos Marı́a Serna
+	Absorption Time of the Moran Process	2014	Josep Dı́az Leslie Ann Goldberg David Richerby Marı́a Serna
+ PDF Chat	On the Stability of Generalized Second Price Auctions with Budgets	2014	Josep Dı́az Ioannis Giotis Lefteris M. Kirousis Evangelos Markakis Marı́a Serna
+	Absorption Time of the Moran Process	2013	Josep Dı́az Leslie Ann Goldberg David Richerby Marı́a Serna
+	On the Stability of Generalized Second Price Auctions with Budgets	2013	Josep Dı́az Ioannis Giotis Lefteris M. Kirousis Evangelos Markakis Marı́a Serna
+ PDF Chat	On the fixation probability of superstars	2013	Josep Dı́az Leslie Ann Goldberg George B. Mertzios David Richerby Marı́a Serna Paul G. Spirakis
+	Power indices of influence games and new centrality measures for social networks	2013	Xavier Molinero Fabián Riquelme Marı́a Serna
+	On the Stability of Generalized Second Price Auctions with Budgets	2013	Josep Dı́az Ioannis Giotis Lefteris M. Kirousis Evangelos Markakis Marı́a Serna
+	Absorption Time of the Moran Process	2013	Josep Dı́az Leslie Ann Goldberg David Richerby María Serna
+ PDF Chat	Approximating Fixation Probabilities in the Generalized Moran Process	2012	Josep Dı́az Leslie Ann Goldberg George B. Mertzios David Richerby Marı́a Serna Paul G. Spirakis
+	Can Fixation be Guaranteed in the Generalized Moran Process	2012	Josep Dı́az Leslie Ann Goldberg George B. Mertzios David Richerby Marı́a Serna Paul G. Spirakis
+	Approximating fixation probabilities in the generalized Moran process	2012	Josep Dı́az Leslie Ann Goldberg George B. Mertzios David Richerby Marı́a Serna Paul G. Spirakis
+	Approximating Fixation Probabilities in the Generalized Moran Process	2012	Josep Dı́az Leslie Ann Goldberg George B. Mertzios David Richerby Marı́a Serna Paul G. Spirakis
+	Social Influence as a Voting System: a Complexity Analysis of Parameters and Properties	2012	Xavier Molinero Fabián Riquelme Marı́a Serna
+	Complexity of Metric Dimension on Planar Graphs	2011	Josep Dı́az Olli Pottonen Marı́a Serna Erik Jan van Leeuwen
+	On the Complexity of Metric Dimension	2011	Josep Dı́az Olli Pottonen Marı́a Serna Erik Jan van Leeuwen
+	Complexity of Metric Dimension on Planar Graphs	2011	Josep Dı́az Olli Pottonen Marı́a Serna Erik Jan van Leeuwen
+	Vertex fusion under distance constraints	2009	Marc Comas‐Cufí Marı́a Serna
+	Efficient algorithms for counting parameterized list H-colorings	2008	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+	Randomized Parallel Approximations to Max Flow	2008	María Serna
+	The Complexity of Testing Properties of Simple Games	2008	Josep Freixas Xavier Molinero Martin Olsen Marı́a Serna
+ PDF Chat	Parallel approximation to high multiplicity scheduling problems<i>VIA</i>smooth multi-valued quadratic programming	2007	Marı́a Serna Fatos Xhafa
+	Vertex fusion under diameter constraints	2007	Marc Comas‐Cufí Marı́a Serna
+ PDF Chat	Bounds on the bisection width for random d -regular graphs	2007	Josep Dı́az Marı́a Serna N. C. Wormald
+	Complexity issues on bounded restrictive H-coloring	2007	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+	Computation of the Bisection Width for Random d-Regular Graphs	2004	Josep Dı́az Marı́a Serna Nicholas Wormald
+	Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings	2004	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+	Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings (Extended Abstract)	2004	Josep D ́ iaz María Serna Dimitrios M. Thilikos
+	Bounds on the max and min bisection of random cubic and random 4-regular graphs	2003	Josep Dı́az Norman Do Marı́a Serna N. C. Wormald
+	The Complexity of deciding stability under FFS in the adversarial model	2003	Carme Àlvarez María J. Blesa Josep Dı́az Antonio Fernández Anta María Serna
+	Counting H-colorings of partial k-trees	2002	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+ PDF Chat	H-Colorings of Large Degree Graphs	2002	Josep Dı́az Jaroslav Nešetřil Marı́a Serna Dimitrios M. Thilikos
+	The Complexity of Restrictive H-Coloring	2002	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+ PDF Chat	On the parallel approximability of a subclass of quadratic programming	2001	Marı́a Serna Fatos Xhafa
+	Approximating layout problems on random graphs	2001	Josep Dı́az Jordi Petit Marı́a Serna Luca Trevisan
+	Counting list h-colorings and variants	2001	Josep Dı́az María Serna Dimitrios Thilikos Touloupas
+	Counting H-Colorings of Partial k-Trees	2001	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+ PDF Chat	Convergence Theorems for Some Layout Measures on Random Lattice and Random Geometric Graphs	2000	Josep Dı́az Mathew D. Penrose Jordi Petit Marı́a Serna
+	Routing Tree Problems on Random Graphs.	2000	Carme Àlvarez R. Ferrer Cases Josep Dı́az Jordi Petit María Serna
+	Linear orderings of random geometric graphs (extended abstract)	1999	Josep Dı́az Matthew Penrose Jordi Petit María Serna
+	Approximating layout problems on random sparse graphs	1998	Josep Dı́az Jordi Petit María Serna Marco Trevisan
+	On the random generation and counting of matchings in dense graphs	1998	Josep Dı́az Marı́a Serna Paul G. Spirakis
+	Random Geometric Problems on [0, 1]2	1998	Josep Dı́az Jordi Petit Marı́a Serna
+	A Parallel Algorithm for Sampling Matchings from an Almost Uniform Distribution	1998	Josep Dı́az Jordi Petit Panagiotis Psycharis Marı́a Serna
+	Approximating the permanent is in RNC	1995	Josep Dı́az María Serna Paul G. Spirakis
+ PDF Chat	On parallel versus sequential approximation	1995	Marı́a Serna Fatos Xhafa
+	On RNC approximate counting	1994	Josep Dı́az María Serna Paul G. Spirakis
+	Approximating linear programming is log-space complete for P	1991	Marı́a Serna
+	The approximability of problems complete for P (invited)	1989	María Serna Paul G. Spirakis
+ PDF Chat	Asymptotical behaviour of some non-uniform measures	1989	Marı́a Serna

Common Coauthors

Coauthor	Papers Together
Josep Dı́az	48
Xavier Molinero	11
Paul G. Spirakis	9
Leslie Ann Goldberg	9
David Richerby	9
Öznur Yaşar Diner	8
Oriol Serra	7
Jordi Petit	7
Martin Olsen	6
Lefteris M. Kirousis	5
George B. Mertzios	5
Ioannis Giotis	5
Dimitrios M. Thilikos	5
Olli Pottonen	4
Erik Jan van Leeuwen	4
Fabián Riquelme	4
Sascha Kurz	4
Evangelos Markakis	4
María J. Blesa	3
Dimitrios M. Thilikos	3
Carme Àlvarez	3
Fatos Xhafa	3
N. C. Wormald	2
Marc Comas‐Cufí	2
Eun Jung Kim	2
Dimitrios M. Thilikos	2
Panagiotis Psycharis	1
Luca Trevisan	1
Martin Olsen	1
Dimitrios Thilikos Touloupas	1
Arnau Messegué	1
Jaroslav Nešetřil	1
R. Ferrer Cases	1
Josep D ́ iaz	1
Josep Freixas	1
Joaquim Gabarró	1
Yiannis Mourtos	1
Nicholas Wormald	1
Marco Trevisan	1
Mathew D. Penrose	1
Antonio Fernández Anta	1
Oriol Serra	1
Amalia Duch	1
Norman Do	1
Matthew Penrose	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+	The complexity of counting graph homomorphisms	2000	Martin Dyer Catherine Greenhill	8
+	On the complexity of H-coloring	1990	Pavol Hell Jaroslav Nešetřil	7
+	List Homomorphisms and Circular Arc Graphs	1999	Tomás Feder Pavol Hell Jing Huang	7
+	The Isoperimetric Number of Random Regular Graphs	1988	Béla Bollobás	6
+	Dynamic Monopolies of Constant Size	2001	Eli Berger	5
+	Natural models for evolution on networks	2012	George B. Mertzios Sotiris Nikoletseas Christoforos Raptopoulos Paul G. Spirakis	4
+ PDF Chat	Fixation of Strategies for an Evolutionary Game in Finite Populations	2006	Tibor Antal István Scheuring	4
+	The complexity of colouring problems on dense graphs	1986	Keith Edwards	3
+ PDF Chat	On the submodularity of influence in social networks	2007	Elchanan Mossel Sébastien Roch	3
+ PDF Chat	The long-run behavior of the stochastic replicator dynamics	2005	Lorens A. Imhof	3
+	Bounds on the max and min bisection of random cubic and random 4-regular graphs	2003	Josep Dı́az Norman Do Marı́a Serna N. C. Wormald	3
+ PDF Chat	Stochastic Evolutionary Game Dynamics	2009	Arne Traulsen Christoph Hauert	3
+	Monte-Carlo algorithms for enumeration and reliability problems	1983	Richard M. Karp Michael Luby	3
+ PDF Chat	A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory	1975	Miroslav Fiedler	3
+ PDF Chat	Polyhedral clinching auctions and the adwords polytope	2012	Gagan Goel Vahab Mirrokni Renato Paes Leme	3
+	Approximating linear programming is log-space complete for P	1991	Marı́a Serna	3
+	Surveys in Combinatorics	1979		3
+	Models of Random Regular Graphs	1999	N. C. Wormald	3
+	Random generation of combinatorial structures from a uniform distribution	1986	Mark Jerrum Leslie G. Valiant Vijay V. Vazirani	3
+	Lecture notes on particle systems and percolation	1988	Richard Durrett	3
+	Counting H-colorings of partial k-trees	2002	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos	3
+	CONTRIBUTIONS TO PARAMETERIZED COMPLEXITY	2003	Catherine McCartin	3
+	On the Edge-Expansion of Graphs	1997	Noga Alon	3
+	The Parameterized Complexity of Counting Problems	2004	Jörg Flum Martin Grohe	3
+	Graph minors – a survey	1985	Neil Robertson Paul Seymour	3
+	Surveys in Combinatorics, 1999	1999	John D. Lamb D. A. Preece	3
+	The complexity of H-colouring of bounded degree graphs	2000	Anna Galluccio Pavol Hell Jaroslav Nešetřil	3
+ PDF Chat	Diffusion in Social Networks with Competing Products	2011	Krzysztof R. Apt Evangelos Markakis	3
+ PDF Chat	Budget optimization in search-based advertising auctions	2007	Jon Feldman S. Muthukrishnan Martin Pál Clifford Stein	3
+	Narrowing the Complexity Gap for Colouring (<i>C<sub>s</sub>, P<sub>t</sub></i>)-Free Graphs	2015	Shenwei Huang Matthew Johnson Daniël Paulusma	2
+	A Course in Probability Theory	1974	Kai Lai Chung	2
+	Three Partition Refinement Algorithms	1987	Robert Paige Robert E. Tarjan	2
+	Interacting Particle Systems	2016	Thomas M. Liggett	2
+	New Spectral Lower Bounds on the Bisection Width of Graphs	2000	Sergei L. Bezrukov Robert Elsässer⋆ Burkhard Monien Robert Preis Jean–Pierre Tillich	2
+	A parallel approximation algorithm for positive linear programming	1993	Michael Luby Noam Nisan	2
+	Hard coloring problems in low degree planar bipartite graphs	2006	Miroslav Chlebík Janka Chlebı́ková	2
+	Compressions and isoperimetric inequalities	1991	Béla Bollobás Imre Leader	2
+	How to decrease the diameter of triangle-free graphs	1998	Paul Erdős András Gyárfás Miklós Ruszinkó	2
+	Chordal bipartite graphs of bounded tree- and clique-width	2004	Vadim Lozin Dieter Rautenbach	2
+	Generating Random Regular Graphs Quickly	1999	Angelika Steger N. C. Wormald	2
+ PDF Chat	Natural Models for Evolution on Networks	2011	George B. Mertzios Sotiris Nikoletseas Christoforos Raptopoulos Paul G. Spirakis	2
+	Probability Theory and Combinatorial Optimization	1997	John Steele	2
+	On Approximately Counting Colorings of Small Degree Graphs	1999	Russ Bubley Martin Dyer Catherine Greenhill Mark Jerrum	2
+	Approximating layout problems on random graphs	2001	Josep Dı́az Jordi Petit Marı́a Serna Luca Trevisan	2
+	Decreasing the diameter of bounded degree graphs	2000	Noga Alon András Gyárfás Miklós Ruszinkó	2
+	Probability and Computing: Randomized Algorithms and Probabilistic Analysis	2005	Michael Mitzenmacher Eli Upfal	2
+	Isoperimetric numbers of graphs	1989	Bojan Mohar	2
+	Polynomial algorithms in linear programming	1980	Leonid Khachiyan	2
+	Biconvex graphs: ordering and algorithms	2000	Nesrine Abbas Lorna Stewart	2
+	The complexity of counting graph homomorphisms (extended abstract)	2000	Martin Dyer Catherine Greenhill	2