Maria J. Serna

Xavier Molinero, Fabián Riquelme, Maria J. Serna: Star-shaped mediation in influence games. CTW 2013: 179-182

Carme Àlvarez, Josep Díaz, Dieter Mitsche, Maria J. Serna: Continuous monitoring in the dynamic sensor field model. Theor. Comput. Sci. 463: 114-122 (2012)

Josep Díaz, Olli Pottonen, Maria J. Serna, Erik Jan van Leeuwen: On the Complexity of Metric Dimension. ESA 2012: 419-430

Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis: Approximating fixation probabilities in the generalized Moran process. SODA 2012: 954-960

Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis: Can Fixation be Guaranteed in the Generalized Moran Process? CoRR abs/1202.0436 (2012)

Xavier Molinero, Fabián Riquelme, Maria J. Serna: Social Influence as a Voting System: a Complexity Analysis of Parameters and Properties. CoRR abs/1208.3751 (2012)

Carme Àlvarez, Ioannis Chatzigiannakis, Amalia Duch, Joaquim Gabarró, Othon Michail, Maria J. Serna, Paul G. Spirakis: Computational models for networks of tiny artifacts: A survey. Computer Science Review 5(1): 7-25 (2011)

Maria J. Blesa, Amalia Duch, Joaquim Gabarró, Hugo Hernández, Maria J. Serna: Coaching on New Technologies: Programming Workshop Android Applications for Google Phones. Bulletin of the EATCS 105: 205-208 (2011)

Carme Àlvarez, Joaquim Gabarró, Maria J. Serna: Equilibria problems on games: Complexity versus succinctness. J. Comput. Syst. Sci. 77(6): 1172-1197 (2011)

Josep Freixas, Xavier Molinero, Martin Olsen, Maria J. Serna: On the complexity of problems on simple games. RAIRO - Operations Research 45(4): 295-314 (2011)

Joaquim Gabarró, Alina García, Maria J. Serna: The complexity of game isomorphism. Theor. Comput. Sci. 412(48): 6675-6695 (2011)

Carme Àlvarez, Maria J. Blesa, Maria J. Serna: The robustness of stability under link and node failures. Theor. Comput. Sci. 412(50): 6855-6878 (2011)

Carme Àlvarez, Josep Díaz, Dieter Mitsche, Maria J. Serna: Continuous Monitoring in the Dynamic Sensor Field Model. ALGOSENSORS 2011: 161-172

Joaquim Gabarró, Maria J. Serna, Alan Stewart: Web Services and Incerta Spiriti: A Game Theoretic Approach to Uncertainty. ECSQARU 2011: 651-662

Carme Àlvarez, Amalia Duch, Maria J. Serna, Dimitrios M. Thilikos: On the Existence of Nash Equilibria in Strategic Search Games. TGC 2011: 58-72

Joaquim Gabarró, Maria J. Serna, Alan Stewart: Orchestrating Unreliable Services: Strategic and Probabilistic Approaches to Reliability. TGC 2011: 197-211

Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis: Approximating Fixation Probabilities in the Generalized Moran Process. CoRR abs/1111.3321 (2011)

Joaquim Gabarró, Peter Kilpatrick, Maria J. Serna, Alan Stewart: Stressed Web Environments as Strategic Games: Risk Profiles and Weltanschauung. TGC 2010: 189-204

Maria J. Serna, Ronen Shaltiel, Klaus Jansen, José D. P. Rolim (Eds.): Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings. Lecture Notes in Computer Science 6302, Springer 2010, isbn 978-3-642-15368-6

Josep Díaz, Maria J. Serna, Paul G. Spirakis, Jacobo Torán: Paradigms for fast parallel approximability (Reprint from 1997). Cambridge international series on parallel computation 8, Cambridge University Press 2009, isbn 978-0-521-43170-5, pp. I-VIII, 1-158

Marc Comas, Maria J. Serna: Vertex fusion under distance constraints. Eur. J. Comb. 30(7): 1612-1623 (2009)

Carme Àlvarez, Maria J. Serna: On the proper intervalization of colored caterpillar trees. ITA 43(4): 667-686 (2009)

Maria J. Serna, Carme Àlvarez: Preface to special section of selected papers from WEA 2006. ACM Journal of Experimental Algorithmics 14 (2009)

Maria J. Blesa, Daniel Calzada, Antonio Fernández, Luis López, Andrés L. Martínez, Agustín Santos, Maria J. Serna, Christopher Thraves: Adversarial Queueing Model for Continuous Network Dynamics. Theory Comput. Syst. 44(3): 304-331 (2009)

Carme Àlvarez, Amalia Duch, Joaquim Gabarró, Maria J. Serna: Sensor Field: A Computational Model. ALGOSENSORS 2009: 3-14

Josep Díaz, Zvi Lotker, Maria J. Serna: The distant-2 chromatic number of random proximity and random geometric graphs. Inf. Process. Lett. 106(4): 144-148 (2008)

Maria J. Serna, Fatos Xhafa: Parallel approximation to high multiplicity scheduling problems VIA smooth multi-valued quadratic programming. ITA 42(2): 237-252 (2008)

Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos: Efficient algorithms for counting parameterized list H-colorings. J. Comput. Syst. Sci. 74(5): 919-937 (2008)

Josep Díaz, Xavier Pérez, Maria J. Serna, Nicholas C. Wormald: Walkers on the Cycle and the Grid. SIAM J. Discrete Math. 22(2): 747-775 (2008)

Carme Àlvarez, Josep Díaz, Jordi Petit, José D. P. Rolim, Maria J. Serna: High level communication functionalities for wireless sensor networks. Theor. Comput. Sci. 406(3): 240-247 (2008)

Joaquim Gabarró, Alina García, Maria J. Serna: On the Complexity of Equilibria Problems in Angel-Daemon Games. COCOON 2008: 31-40

Maria J. Serna: Parallel Algorithms for Two Processors Precedence Constraint Scheduling. Encyclopedia of Algorithms 2008

Maria J. Serna: Randomized Parallel Approximations to Max Flow. Encyclopedia of Algorithms 2008

Josep Freixas, Xavier Molinero, Martin Olsen, Maria J. Serna: The Complexity of Testing Properties of Simple Games. CoRR abs/0803.0404 (2008)

Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos: Complexity issues on bounded restrictive H-coloring. Discrete Mathematics 307(16): 2082-2093 (2007)

Marc Comas, Maria J. Serna: Vertex fusion under diameter constraints. Electronic Notes in Discrete Mathematics 29: 261-265 (2007)

Carme Àlvarez, Rafel Cases, Josep Díaz, Jordi Petit, Maria J. Serna: Communication tree problems. Theor. Comput. Sci. 381(1-3): 197-217 (2007)

Josep Díaz, Maria J. Serna, Nicholas C. Wormald: Bounds on the bisection width for random d -regular graphs. Theor. Comput. Sci. 382(2): 120-130 (2007)

Juan Antonio Gonzalez, Maria J. Serna, Fatos Xhafa: A Hyper-Heuristic for Scheduling Independent Jobs in Computational Grids. ICSOFT (PL/DPS/KE/MUSE) 2007: 128-135

Joaquim Gabarró, Alina García, Maria J. Serna: On the Complexity of Game Isomorphism. MFCS 2007: 559-571

Maria J. Serna: Random Models for Geometric Graphs (Abstract). WEA 2007: 37

Carme Àlvarez, Maria J. Serna (Eds.): Experimental Algorithms, 5th International Workshop, WEA 2006, Cala Galdana, Menorca, Spain, May 24-27, 2006, Proceedings. Lecture Notes in Computer Science 4007, Springer 2006, isbn 3-540-34597-3

Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos: The restrictive H-coloring problem. Discrete Applied Mathematics 145(2): 297-305 (2005)

Maria J. Serna, Dimitrios M. Thilikos: Parameterized Complexity for Graph Layout Problems. Bulletin of the EATCS 86: 41-65 (2005)

Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender: Cutwidth I: A linear time fixed parameter algorithm. J. Algorithms 56(1): 1-24 (2005)

Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender: Cutwidth II: Algorithms for partial w-trees of bounded degree. J. Algorithms 56(1): 25-49 (2005)

Carme Àlvarez, Maria J. Blesa, Josep Díaz, Maria J. Serna, Antonio Fernández: Adversarial models for priority-based networks. Networks 45(1): 23-35 (2005)

Maria J. Serna, Luca Trevisan, Fatos Xhafa: The approximability of non-Boolean satisfiability problems and restricted integer programming. Theor. Comput. Sci. 332(1-3): 123-139 (2005)

Josep Díaz, Vishal Sanwalani, Maria J. Serna, Paul G. Spirakis: The chromatic and clique numbers of random scaled sector graphs. Theor. Comput. Sci. 349(1): 40-51 (2005)

Carme Àlvarez, Joaquim Gabarró, Maria J. Serna: Polynomial Space Suffices for Deciding Nash Equilibria Properties for Extensive Games with Large Trees, . ISAAC 2005: 634-643

Carme Àlvarez, Joaquim Gabarró, Maria J. Serna: Pure Nash Equilibria in Games with a Large Number of Actions. MFCS 2005: 95-106

Maria J. Blesa, Daniel Calzada, Antonio Fernández, Luis López, Andrés L. Martínez, Agustín Santos, Maria J. Serna: Adversarial Queueing Model for Continuous Network Dynamics. MFCS 2005: 144-155

Josep Díaz-Giménez, Xavier Pérez, Maria J. Serna, Nicholas C. Wormald: Connectivity for Wireless Agents Moving on a Cycle or Grid. STACS 2005: 353-364

Carme Àlvarez, Joaquim Gabarró, Maria J. Serna: Pure Nash equilibria in games with a large number of actions. Electronic Colloquium on Computational Complexity (ECCC)(031) (2005)

Carme Àlvarez, Maria J. Serna: The Proper Interval Colored Graph problem for caterpillar trees: (Extended Abstract). Electronic Notes in Discrete Mathematics 17: 23-28 (2004)

Carme Àlvarez, Maria J. Blesa, Josep Díaz, Antonio Fernández, Maria J. Serna: The complexity of deciding stability under FFS in the Adversarial Queueing model. Inf. Process. Lett. 90(5): 261-266 (2004)

Carme Àlvarez, Maria J. Blesa, Maria J. Serna: A Characterization of Universal Stability in the Adversarial Queuing Model. SIAM J. Comput. 34(1): 41-66 (2004)

Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos: Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings. ESA 2004: 275-286

Carme Àlvarez, Maria J. Blesa, Maria J. Serna: The Impact of Failure Management on the Stability of Communication Networks. ICPADS 2004: 153-160

Josep Díaz, Maria J. Serna, Nicholas C. Wormald: Computation of the Bisection Width for Random d-Regular Graphs. LATIN 2004: 49-58

Carme Àlvarez, Josep Díaz, Jordi Petit, José D. P. Rolim, Maria J. Serna: Efficient and reliable high level communication in randomly deployed wireless sensor networks. Mobility Management & Wireless Access Protocols 2004: 106-110

Hermann Jung, Maria J. Serna, Paul G. Spirakis: An efficient deterministic parallel algorithm for two processors precedence constraint scheduling. Theor. Comput. Sci. 292(3): 639-652 (2003)

Josep Díaz, Norman Do, Maria J. Serna, Nicholas C. Wormald: Bounds on the max and min bisection of random cubic and random 4-regular graphs. Theor. Comput. Sci. 307(3): 531-547 (2003)

Josep Díaz, Jordi Petit, Maria J. Serna: A Random Graph Model for Optical Networks of Sensors. IEEE Trans. Mob. Comput. 2(3): 186-196 (2003)

Carme Àlvarez, Maria J. Blesa, Josep Díaz, Antonio Fernández, Maria J. Serna: Adversarial Models for Priority-Based Networks. MFCS 2003: 142-151

Josep Díaz, Jordi Petit, Maria J. Serna: Evaluation of Basic Protocols for Optical Smart Dust Networks. WEA 2003: 97-106

Maria J. Serna, Fatos Xhafa: Approximating Scheduling Unrelated Parallel Machines in Parallel. Comp. Opt. and Appl. 21(3): 325-338 (2002)

Josep Díaz, Jordi Petit, Maria J. Serna: A survey of graph layout problems. ACM Comput. Surv. 34(3): 313-356 (2002)

Maria J. Serna, Fatos Xhafa: The Parallel Approximability of the False and True Gates Problems for NOR-Circuits. Parallel Processing Letters 12(1): 127-136 (2002)

Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos: Counting H-colorings of partial k-trees. Theor. Comput. Sci. 281(1-2): 291-309 (2002)

Josep Díaz, Jaroslav Nesetril, Maria J. Serna, Dimitrios M. Thilikos: H-Colorings of Large Degree Graphs. EurAsia-ICT 2002: 850-857

Josep Díaz, Norman Do, Maria J. Serna, Nicholas C. Wormald: Bisection of Random Cubic Graphs. RANDOM 2002: 114-125

Carme Àlvarez, Maria J. Blesa, Maria J. Serna: Universal stability of undirected graphs in the adversarial queueing model. SPAA 2002: 183-197

Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos: The Complexity of Restrictive H-Coloring. WG 2002: 126-137

Carme Àlvarez, Josep Díaz, Maria J. Serna: The hardness of intervalizing four colored caterpillars. Discrete Mathematics 235(1-3): 19-27 (2001)

Josep Díaz, Jordi Petit, Maria J. Serna, Luca Trevisan: Approximating layout problems on random graphs. Discrete Mathematics 235(1-3): 245-253 (2001)

Josep Díaz, Mathew D. Penrose, Jordi Petit, Maria J. Serna: Approximating Layout Problems on Random Geometric Graphs. J. Algorithms 39(1): 78-116 (2001)

Maria J. Serna, Fatos Xhafa: On the parallel approximability of a subclass of quadratic programming. Theor. Comput. Sci. 259(1-2): 217-231 (2001)

Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos: Counting H-Colorings of Partial k-Trees. COCOON 2001: 298-307

Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender: A Polynomial Time Algorithm for the Cutwidth of Bounded Degree Graphs with Small Treewidth. ESA 2001: 380-390

Alan Stewart, Maurice Clint, Joaquim Gabarró, Maria J. Serna: Towards Formally Refining BSP Barrier s into Explicit Two-Sided Communications. Euro-Par 2001: 549-559

Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos: (H, C, K)-Coloring: Fast, Easy, and Hard Cases. MFCS 2001: 304-315

Josep Díaz, Dimitrios Koukopoulos, Sotiris E. Nikoletseas, Maria J. Serna, Paul G. Spirakis, Dimitrios M. Thilikos: Stability and non-stability of the FIFO protocol. SPAA 2001: 48-52

Josep Díaz, Mathew D. Penrose, Jordi Petit, Maria J. Serna: Convergence Theorems For Some Layout Measures On Random Lattice And Random Geometric Graphs. Combinatorics, Probability & Computing 9(6): 489-511 (2000)

Josep Díaz, Jordi Petit, Maria J. Serna: Faulty Random Geometric Networks. Parallel Processing Letters 10(4): 343-358 (2000)

Carme Àlvarez, Rafel Cases, Josep Díaz, Jordi Petit, Maria J. Serna: Routing Tree Problems on Random Graphs. ICALP Satellite Workshops 2000: 99-110

Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender: Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width. ISAAC 2000: 192-203

Maria J. Serna, Fatos Xhafa: On the Average Case Complexity of Some P-complete Problems. ITA 33(1): 33-46 (1999)

Josep Díaz, Mathew D. Penrose, Jordi Petit, Maria J. Serna: Layout Problems on Lattice Graphs. COCOON 1999: 103-112

Josep Díaz, Mathew D. Penrose, Jordi Petit, Maria J. Serna: Linear Orderings of Random Geometric Graphs. WG 1999: 291-302

Josep Díaz, Maria J. Serna, Paul G. Spirakis: On the Random Generation and Counting of Matchings in Dense Graphs. Theor. Comput. Sci. 201(1-2): 281-290 (1998)

Josep Díaz, Jordi Petit, Panagiotis Psycharis, Maria J. Serna: A Parallel Algorithm for Sampling Matchings from an Almost Uniform Distribution. ISAAC 1998: 457-466

Josep Díaz, Jordi Petit, Maria J. Serna: Random Geometric Problems on [0, 1]². RANDOM 1998: 294-306

Maria J. Serna, Luca Trevisan, Fatos Xhafa: The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming. STACS 1998: 488-498

Michael Luby, José D. P. Rolim, Maria J. Serna (Eds.): Randomization and Approximation Techniques in Computer Science, Second International Workshop, RANDOM'98, Barcelona, Spain, October 8-10, 1998, Proceedings. Lecture Notes in Computer Science 1518, Springer 1998, isbn 3-540-65142-X

Josep Díaz, Alan Gibbons, Grammati E. Pantziou, Maria J. Serna, Paul G. Spirakis, Jacobo Torán: Parallel Algorithms for the Minimum Cut and the Minimum Length Tree Layout Problems. Theor. Comput. Sci. 181(2): 267-287 (1997)

Maria J. Serna, Fatos Xhafa: Approximating Scheduling Problems in Parallel. Euro-Par 1997: 440-449

Maria J. Serna, Fatos Xhafa: The Parallel Approximability of a Subclass of Quadratic Programming. ICPADS 1997: 474-

Josep Díaz, Maria J. Serna, Jacobo Torán: Parallel Approximation Schemes for Problems on Planar Graphs. Acta Inf. 33(4): 387-408 (1996)

Josep Díaz, Maria J. Serna (Eds.): Algorithms - ESA '96, Fourth Annual European Symposium, Barcelona, Spain, September 25-27, 1996, Proceedings. Lecture Notes in Computer Science 1136, Springer 1996, isbn 3-540-61680-2

Joaquim Gabarró, Maria J. Serna: Rational Processes and Linear Systems in CSP. Fundam. Inform. 24(3): 283-302 (1995)

Josep Díaz, Alan Gibbons, Grammati E. Pantziou, Maria J. Serna, Paul G. Spirakis, Jacobo Torán: Efficient Parallel Algorithms for some Tree Layout Problems. COCOON 1995: 313-323

Maria J. Serna, Fatos Xhafa: On Parallel versus Sequential Approximation. ESA 1995: 409-419

Lefteris M. Kirousis, Maria J. Serna, Paul G. Spirakis: Parallel Complexity of the Connected Subgraph Problem. SIAM J. Comput. 22(3): 573-586 (1993)

Josep Díaz, Maria J. Serna, Jacobo Torán: Parallel Approximation Schemes for problems on planar graphs (Extended Abstract). ESA 1993: 145-156

Maria J. Serna: Approximating Linear Programming is Log-Space Complete for P. Inf. Process. Lett. 37(4): 233-236 (1991)

Hermann Jung, Maria J. Serna, Paul G. Spirakis: A Parallel Algorithm for Two Processors Precedence Constraint Scheduling. ICALP 1991: 417-428

Maria J. Serna, Paul G. Spirakis: Tight RNC Approximations to Max Flow. STACS 1991: 118-126

Maria J. Serna: Asymptotical Behaviour of Some Non-Uniform Measures. ITA 23(3): 281-293 (1989)

Lefteris M. Kirousis, Maria J. Serna, Paul G. Spirakis: The Parallel Complexity of the Subgraph Connectivity Problem. FOCS 1989: 294-299

Maria J. Serna, Paul G. Spirakis: The Approximability of Problems Complete for P. Optimal Algorithms 1989: 193-204