Josep Díaz

According to our database1, Josep Díaz authored at least 106 papers between 1982 and 2019.

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



In proceedings 
PhD thesis 





Algorithmically Efficient Syntactic Characterization of Possibility Domains.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

EATCS Fellows 2019 - Call for Nominations.
Bulletin of the EATCS, 2018

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

Minimum Bisection Is NP-hard on Unit Disk Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

On the Stability of Generalized Second Price Auctions with Budgets.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Absorption Time of the Moran Process.
Proceedings of the Approximation, 2014

The Power of Choice for Random Satisfiability.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

A personal account of Turing's imprint on the development of computer science.
Computer Science Review, 2012

Book Review: George Dyson "Turing's Cathedral: The Origins of the Digital Universe" (2012) Pantheon Books.
Computer Science Review, 2012

Approximating fixation probabilities in the generalized Moran process.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

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

Theoretical Aspects of Graph Models for MANETs.
Proceedings of the Theoretical Aspects of Distributed Computing in Sensor Networks, 2011

J. Discrete Algorithms, 2011

Computer Science Review, 2011

Cris Moore, Stephen Mertens, , The Nature of Computation (2011) Oxford UP.
Computer Science Review, 2011

Social-Aware Forwarding Improves Routing Performance in Pocket Switched Networks.
Proceedings of the Algorithms - ESA 2011, 2011

Continuous Monitoring in the Dynamic Sensor Field Model.
Proceedings of the Algorithms for Sensor Systems, 2011

A note on the subgraphs of the (2×∞)-grid.
Discrete Mathematics, 2010

The cook-book approach to the differential equation method.
Computer Science Review, 2010

Book review.
Computer Science Review, 2010

Large Connectivity for Dynamic Random Geometric Graphs.
IEEE Trans. Mob. Comput., 2009

On the satisfiability threshold of formulas with three literals per clause.
Theor. Comput. Sci., 2009

On the chromatic number of a random 5-regular graph.
Journal of Graph Theory, 2009

Computer Science Review, 2009

On the Power of Mediators.
Proceedings of the Internet and Network Economics, 5th International Workshop, 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

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

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

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

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

On the connectivity of dynamic random geometric graphs.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

A new upper bound for 3-SAT.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

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

MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs.
Theor. Comput. Sci., 2007

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

Sharp Threshold for Hamiltonicity of Random Geometric Graphs.
SIAM J. Discrete Math., 2007

Complexity issues on bounded restrictive H-coloring.
Discrete Mathematics, 2007

Discrete Applied Mathematics, 2007

Computer Science Review, 2007

Kernels for the Vertex Cover Problem on the Preferred Attachment Model.
Proceedings of the Experimental Algorithms, 5th International Workshop, 2006

Fast FPT-Algorithms for Cleaning Grids.
Proceedings of the STACS 2006, 2006

Balanced Cut Approximation in Random Geometric Graphs.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

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

Theor. Comput. Sci., 2005

Adversarial models for priority-based networks.
Networks, 2005

The restrictive H-coloring problem.
Discrete Applied Mathematics, 2005

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

5-Regular Graphs are 3-Colorable with Positive Probability.
Proceedings of the Algorithms, 2005

The complexity of deciding stability under FFS in the Adversarial Queueing model.
Inf. Process. Lett., 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

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

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

Adversarial Models for Priority-Based Networks.
Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

Analysis of Algorithms (AofA): Part I: 1993 -- 1998.
Bulletin of the EATCS, 2002

Primes in P (Without Assumptions).
Bulletin of the EATCS, 2002

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

The Complexity of Restrictive H-Coloring.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 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

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

H-Colorings of Graphs.
Bulletin of the EATCS, 2001

Approximating layout problems on random graphs.
Discrete Mathematics, 2001

The hardness of intervalizing four colored caterpillars.
Discrete Mathematics, 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

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

Counting H-Colorings of Partial k-Trees.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

Faulty Random Geometric Networks.
Parallel Processing Letters, 2000

Convergence Theorems For Some Layout Measures On Random Lattice And Random Geometric Graphs.
Combinatorics, Probability & Computing, 2000

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

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

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

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

Algorithms for Learning Finite Automata from Queries: A Unified View.
Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

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

Structural Complexity I, Second Edition
Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 354058384X, 1995

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

The Query Complexity of Learning DFA.
New Generation Comput., 1994

An Optimal Parallel Algorithm for Learning DFA.
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

Average-Case Analysis on Simple Families of Trees Using a Balanced Probability Model.
Theor. Comput. Sci., 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

On the Average Size of the Intersection of Binary Trees.
SIAM J. Comput., 1992

Graph Layout Problems.
Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

A Note on the Query Complexity of Learning DFA (Extended Abstract).
Proceedings of the Algorithmic Learning Theory, Third Workshop, 1992

The MINSUMCUT Problem.
Proceedings of the Algorithms and Data Structures, 1991

Static on Random Trees.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Structural Complexity II
EATCS Monographs on Theoretical Computer Science 22, Springer, ISBN: 0387520791, 1990

Structural Complexity I
EATCS Monographs on Theoretical Computer Science 11, Springer, ISBN: 978-3-642-97062-7, 1990

Classes of Bounded Nondeterminism.
Mathematical Systems Theory, 1990

Average-Case Analysis of Robinson's Unification Algorithm with Two Different Variables.
Inf. Process. Lett., 1989

Complexity Classes with Complete Problems Between P and NP-C.
Proceedings of the Fundamentals of Computation Theory, 1989

Structural complexity, 1st Edition.
EATCS monographs on theoretical computer science 11, Springer, ISBN: 0387186220, 1988

On Characterizations of the Class PSPACE/POLY.
Theor. Comput. Sci., 1987

On Non- uniform Polynomial Space.
Proceedings of the Structure in Complexity Theory, 1986

Uniform Characterizations of Non-Uniform Complexity Measures
Information and Control, 1985

Examples of CFI-BI-immune and CF-levelable sets in logspace.
Bulletin of the EATCS, 1985

On some "non-uniform" complexity measures.
Proceedings of the Fundamentals of Computation Theory, 1985

Some results about Logspace complexity measures.
Bulletin of the EATCS, 1984

A Note on a Theorem by Ladner.
Inf. Process. Lett., 1982