Maria J. Serna

  • Polytechnic University of Catalonia, Barcelona, Spain

According to our database1, Maria J. Serna authored at least 151 papers between 1989 and 2023.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.



In proceedings 
PhD thesis 


Online presence:



Multidimension: a dimensionality extension of simple games.
Comput. Appl. Math., December, 2023

On the generalized dimension and codimension of simple games.
Eur. J. Oper. Res., 2023

On Vertex Bisection Width of Random d-Regular Graphs.
CoRR, 2022

Playing with Thresholds on the Forward Linear Threshold Rank.
CoRR, 2022

Relating Real and Synthetic Social Networks Through Centrality Measures.
Proceedings of the 20th International Symposium on Experimental Algorithms, 2022

On Weights and Quotas for Weighted Majority Voting Games.
Games, 2021

The Multicolored Graph Realization Problem.
CoRR, 2021

Forward and backward linear threshold ranks.
Proceedings of the ASONAM '21: International Conference on Advances in Social Networks Analysis and Mining, Virtual Event, The Netherlands, November 8, 2021

Refining Indeterministic Choice: Imprecise Probabilities and Strategic Thinking.
Vietnam. J. Comput. Sci., 2020

On List k-Coloring Convex Bipartite Graphs.
CoRR, 2020

Measuring satisfaction and power in influence based decision systems.
Knowl. Based Syst., 2019

Refining the Imprecise Meaning of Non-determinism in the Web by Strategic Games.
Proceedings of the Computational Collective Intelligence - 11th International Conference, 2019

Measuring Investment Opportunities Under Uncertainty.
Proceedings of the Symbolic and Quantitative Approaches to Reasoning with Uncertainty, 2019

Centrality measure in social networks based on linear threshold model.
Knowl. Based Syst., 2018

Satisfaction and Power in Unanimous Majority Influence Decision Models.
Electron. Notes Discret. Math., 2018

Data-Compression for Parametrized Counting Problems on Sparse Graphs.
Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

Web Apps and Imprecise Probabilitites.
Proceedings of the Information Processing and Management of Uncertainty in Knowledge-Based Systems. Theory and Foundations, 2018

Complexity of metric dimension on planar graphs.
J. Comput. Syst. Sci., 2017

The computational complexity of QoS measures for orchestrations - The computational complexity of QoS measures.
J. Comb. Optim., 2017

Uncertainty in basic short-term macroeconomic models with angel-daemon games.
Int. J. Data Anal. Tech. Strateg., 2017

The social cost of congestion games by imposing variable delays.
ICT Express, 2017

An Angel-Daemon Approach to Assess the Uncertainty in the Power of a Collectivity to Act.
Proceedings of the Symbolic and Quantitative Approaches to Reasoning with Uncertainty, 2017

Randomized Parallel Approximations to Max Flow.
Encyclopedia of Algorithms, 2016

Parallel Algorithms for Two Processors Precedence Constraint Scheduling.
Encyclopedia of Algorithms, 2016

Celebrity games.
Theor. Comput. Sci., 2016

Absorption time of the Moran process.
Random Struct. Algorithms, 2016

On the Stability of Generalized Second Price Auctions with Budgets.
Theory Comput. Syst., 2016

Network Formation for Asymmetric Players and Bilateral Contracting.
Theory Comput. Syst., 2016

On the complexity of exchanging.
Inf. Process. Lett., 2016

The Complexity of Measuring Power in Generalized Opinion Leader Decision Models.
Electron. Notes Discret. Math., 2016

Dimension and codimension of simple games.
Electron. Notes Discret. Math., 2016

Measuring satisfaction in societies with opinion leaders and mediators.
CoRR, 2016

Uncertainty Analysis of Simple Macroeconomic Models Using Angel-Daemon Games.
CoRR, 2016

Theory Comput. Syst., 2015

Forms of representation for simple games: Sizes, conversions and equivalences.
Math. Soc. Sci., 2015

Cooperation through social influence.
Eur. J. Oper. Res., 2015

Stars and Celebrities: A Network Creation Game.
CoRR, 2015

The Robustness of Periodic Orchestrations in Uncertain Evolving Environments.
Proceedings of the Symbolic and Quantitative Approaches to Reasoning with Uncertainty, 2015

A Cost-benefit Analysis of Continuous Assessment.
Proceedings of the CSEDU 2015, 2015

Continuous Assessment in the Evolution of a CS1 Course: The Pass Rate/Workload Ratio.
Proceedings of the Computer Supported Education - 7th International Conference, 2015

Computational Aspects of Uncertainty Profiles and Angel-Daemon Games.
Theory Comput. Syst., 2014

Optimizing the Social Cost of Congestion Games by Imposing Variable Delays.
CoRR, 2014

Analysing Web-Orchestrations Under Stress Using Uncertainty Profiles.
Comput. J., 2014

Approximating Fixation Probabilities in the Generalized Moran Process.
Algorithmica, 2014

Power Indices of Influence Games and New Centrality Measures for Agent Societies and Social Networks.
Proceedings of the Ambient Intelligence - Software and Applications, 2014

The Life Cycle of a Cutting-edge Technology Course - A Coaching Experience on Android.
Proceedings of the CSEDU 2014, 2014

On the hardness of game equivalence under local isomorphism.
RAIRO Theor. Informatics Appl., 2013

Power indices of influence games and new centrality measures for social networks.
CoRR, 2013

Star-shaped mediation in influence games.
Proceedings of the 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2013

Continuous monitoring in the dynamic sensor field model.
Theor. Comput. Sci., 2012

Letter from the Bulletin Editor.
Bull. EATCS, 2012

Social Influence as a Voting System: a Complexity Analysis of Parameters and Properties
CoRR, 2012

Can Fixation be Guaranteed in the Generalized Moran Process?
CoRR, 2012

On the Complexity of Metric Dimension.
Proceedings of the Algorithms - ESA 2012, 2012

The complexity of game isomorphism.
Theor. Comput. Sci., 2011

The robustness of stability under link and node failures.
Theor. Comput. Sci., 2011

On the complexity of problems on simple games.
RAIRO Oper. Res., 2011

Equilibria problems on games: Complexity versus succinctness.
J. Comput. Syst. Sci., 2011

Coaching on New Technologies: Programming Workshop Android Applications for Google Phones.
Bull. EATCS, 2011

Computational models for networks of tiny artifacts: A survey.
Comput. Sci. Rev., 2011

Orchestrating Unreliable Services: Strategic and Probabilistic Approaches to Reliability.
Proceedings of the Trustworthy Global Computing - 6th International Symposium, 2011

On the Existence of Nash Equilibria in Strategic Search Games.
Proceedings of the Trustworthy Global Computing - 6th International Symposium, 2011

Web Services and <i>Incerta Spiriti</i>: A Game Theoretic Approach to Uncertainty.
Proceedings of the Symbolic and Quantitative Approaches to Reasoning with Uncertainty, 2011

Stressed Web Environments as Strategic Games: Risk Profiles and Weltanschauung.
Proceedings of the Trustworthly Global Computing - 5th International Symposium, 2010

Adversarial Queueing Model for Continuous Network Dynamics.
Theory Comput. Syst., 2009

Preface to special section of selected papers from WEA 2006.
ACM J. Exp. Algorithmics, 2009

On the proper intervalization of colored caterpillar trees.
RAIRO Theor. Informatics Appl., 2009

Vertex fusion under distance constraints.
Eur. J. Comb., 2009

Sensor Field: A Computational Model.
Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2009

Paradigms for fast parallel approximability (Reprint from 1997).
Cambridge international series on parallel computation 8, Cambridge University Press, ISBN: 978-0-521-43170-5, 2009

Randomized Parallel Approximations to Max Flow.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Parallel Algorithms for Two Processors Precedence Constraint Scheduling.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

High level communication functionalities for wireless sensor networks.
Theor. Comput. Sci., 2008

Walkers on the Cycle and the Grid.
SIAM J. Discret. Math., 2008

Efficient algorithms for counting parameterized list H-colorings.
J. Comput. Syst. Sci., 2008

Parallel approximation to high multiplicity scheduling problems VIA smooth multi-valued quadratic programming.
RAIRO Theor. Informatics Appl., 2008

The distant-2 chromatic number of random proximity and random geometric graphs.
Inf. Process. Lett., 2008

The Complexity of Testing Properties of Simple Games
CoRR, 2008

Analysing Orchestrations Using Risk Profiles And Angel-Daemon Games.
Proceedings of the Grid Computing, 2008

On the Complexity of Equilibria Problems in Angel-Daemon Games.
Proceedings of the Computing and Combinatorics, 14th Annual International Conference, 2008

Bounds on the bisection width for random d -regular graphs.
Theor. Comput. Sci., 2007

Communication tree problems.
Theor. Comput. Sci., 2007

Vertex fusion under diameter constraints.
Electron. Notes Discret. Math., 2007

Complexity issues on bounded restrictive H-coloring.
Discret. Math., 2007

Random Models for Geometric Graphs (Abstract).
Proceedings of the Experimental Algorithms, 6th International Workshop, 2007

A Hyper-Heuristic for Scheduling Independent Jobs in Computational Grids.
Proceedings of the ICSOFT 2007, 2007

The approximability of non-Boolean satisfiability problems and restricted integer programming.
Theor. Comput. Sci., 2005

The chromatic and clique numbers of random scaled sector graphs.
Theor. Comput. Sci., 2005

Adversarial models for priority-based networks.
Networks, 2005

Cutwidth II: Algorithms for partial w-trees of bounded degree.
J. Algorithms, 2005

Cutwidth I: A linear time fixed parameter algorithm.
J. Algorithms, 2005

Pure Nash equilibria in games with a large number of actions
Electron. Colloquium Comput. Complex., 2005

Parameterized Complexity for Graph Layout Problems.
Bull. EATCS, 2005

The restrictive <i>H</i>-coloring problem.
Discret. Appl. Math., 2005

Connectivity for Wireless Agents Moving on a Cycle or Grid.
Proceedings of the STACS 2005, 2005

Adversarial Queueing Model for Continuous Network Dynamics.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

Polynomial Space Suffices for Deciding Nash Equilibria Properties for Extensive Games with Large Trees, .
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

A Characterization of Universal Stability in the Adversarial Queuing Model.
SIAM J. Comput., 2004

The complexity of deciding stability under FFS in the Adversarial Queueing model.
Inf. Process. Lett., 2004

The Proper Interval Colored Graph problem for caterpillar trees: (Extended Abstract).
Electron. Notes Discret. Math., 2004

Efficient and reliable high level communication in randomly deployed wireless sensor networks.
Proceedings of the Second International Workshop on Mobility Management & Wireless Access Protocols, 2004

Computation of the Bisection Width for Random d-Regular Graphs.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

The Impact of Failure Management on the Stability of Communication Networks.
Proceedings of the 10th International Conference on Parallel and Distributed Systems, 2004

Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings.
Proceedings of the Algorithms, 2004

A Random Graph Model for Optical Networks of Sensors.
IEEE Trans. Mob. Comput., 2003

An efficient deterministic parallel algorithm for two processors precedence constraint scheduling.
Theor. Comput. Sci., 2003

Bounds on the max and min bisection of random cubic and random 4-regular graphs.
Theor. Comput. Sci., 2003

Evaluation of Basic Protocols for Optical Smart Dust Networks.
Proceedings of the Experimental and Efficient Algorithms, Second International Workshop, 2003

Counting H-colorings of partial k-trees.
Theor. Comput. Sci., 2002

The Parallel Approximability of the False and True Gates Problems for NOR-Circuits.
Parallel Process. Lett., 2002

A survey of graph layout problems.
ACM Comput. Surv., 2002

Approximating Scheduling Unrelated Parallel Machines in Parallel.
Comput. Optim. Appl., 2002

The Complexity of Restrictive H-Coloring.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

Universal stability of undirected graphs in the adversarial queueing model.
Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2002

Bisection of Random Cubic Graphs.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

H-Colorings of Large Degree Graphs.
Proceedings of the EurAsia-ICT 2002: Information and Communication Technology, 2002

On the parallel approximability of a subclass of quadratic programming.
Theor. Comput. Sci., 2001

Approximating Layout Problems on Random Geometric Graphs.
J. Algorithms, 2001

Approximating layout problems on random graphs.
Discret. Math., 2001

The hardness of intervalizing four colored caterpillars.
Discret. Math., 2001

Stability and non-stability of the FIFO protocol.
Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2001

(H, C, K)-Coloring: Fast, Easy, and Hard Cases.
Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

Towards Formally Refining BSP Barrier s into Explicit Two-Sided Communications.
Proceedings of the Euro-Par 2001: Parallel Processing, 2001

A Polynomial Time Algorithm for the Cutwidth of Bounded Degree Graphs with Small Treewidth.
Proceedings of the Algorithms, 2001

Recent Results on Parameterized H-Colorings.
Proceedings of the Graphs, 2001

Faulty Random Geometric Networks.
Parallel Process. Lett., 2000

Convergence Theorems For Some Layout Measures On Random Lattice And Random Geometric Graphs.
Comb. Probab. Comput., 2000

Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width.
Proceedings of the Algorithms and Computation, 11th International Conference, 2000

Routing Tree Problems on Random Graphs.
Proceedings of the ICALP Workshops 2000, 2000

On the Average Case Complexity of Some P-complete Problems.
RAIRO Theor. Informatics Appl., 1999

Linear Orderings of Random Geometric Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1999

Layout Problems on Lattice Graphs.
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

On the Random Generation and Counting of Matchings in Dense Graphs.
Theor. Comput. Sci., 1998

The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming.
Proceedings of the STACS 98, 1998

Random Geometric Problems on [0, 1]².
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

A Parallel Algorithm for Sampling Matchings from an Almost Uniform Distribution.
Proceedings of the Algorithms and Computation, 9th International Symposium, 1998

Parallel Algorithms for the Minimum Cut and the Minimum Length Tree Layout Problems.
Theor. Comput. Sci., 1997

Approximating Scheduling Problems in Parallel.
Proceedings of the Euro-Par '97 Parallel Processing, 1997

Linear and nonlinear systems: A survey.
Proceedings of the Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, 1997

Parallel Approximation Schemes for Problems on Planar Graphs.
Acta Informatica, 1996

Rational Processes and Linear Systems in CSP.
Fundam. Informaticae, 1995

On Parallel versus Sequential Approximation.
Proceedings of the Algorithms, 1995

Efficient Parallel Algorithms for some Tree Layout Problems.
Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

Parallel Complexity of the Connected Subgraph Problem.
SIAM J. Comput., 1993

Parallel Approximation Schemes for problems on planar graphs (Extended Abstract).
Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993

Approximating Linear Programming is Log-Space Complete for P.
Inf. Process. Lett., 1991

Tight RNC Approximations to Max Flow.
Proceedings of the STACS 91, 1991

A Parallel Algorithm for Two Processors Precedence Constraint Scheduling.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Asymptotical Behaviour of Some Non-Uniform Measures.
RAIRO Theor. Informatics Appl., 1989

The Approximability of Problems Complete for P.
Proceedings of the Optimal Algorithms, International Symposium, Varna, Bulgaria, May 29, 1989

The Parallel Complexity of the Subgraph Connectivity Problem
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989