Josep Díaz
Person information
- affiliation: Polytechnic University of Catalonia, Departament of Computer Science
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2010 – today
- 2019
- [i17]Josep Díaz, Lefteris M. Kirousis, Sofia Kokonezi, John Livieratos:
Algorithmically Efficient Syntactic Characterization of Possibility Domains. CoRR abs/1901.00138 (2019) - 2018
- [j62]
- [i16]Josep Díaz, Mordecai J. Golin:
Smoothed Analysis of the Expected Number of Maximal Points in Two Dimensions. CoRR abs/1807.06845 (2018) - 2017
- [j61]Josep Díaz, George B. Mertzios:
Minimum bisection is NP-hard on unit disk graphs. Inf. Comput. 256: 83-92 (2017) - [j60]Josep Díaz, Olli Pottonen, Maria J. Serna, Erik Jan van Leeuwen:
Complexity of metric dimension on planar graphs. J. Comput. Syst. Sci. 83(1): 132-158 (2017) - 2016
- [j59]Josep Díaz, Ioannis Giotis, Lefteris M. Kirousis, Evangelos Markakis, Maria J. Serna:
On the Stability of Generalized Second Price Auctions with Budgets. Theory Comput. Syst. 59(1): 1-23 (2016) - [j58]Josep Díaz, Leslie Ann Goldberg, David Richerby, Maria J. Serna:
Absorption time of the Moran process. Random Struct. Algorithms 49(1): 137-159 (2016) - 2014
- [j57]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. Algorithmica 69(1): 78-91 (2014) - [c45]Josep Díaz, Leslie Ann Goldberg, David Richerby, Maria J. Serna:
Absorption Time of the Moran Process. APPROX-RANDOM 2014: 630-642 - [c44]Josep Díaz, Ioannis Giotis, Lefteris M. Kirousis, Evangelos Markakis, Maria J. Serna:
On the Stability of Generalized Second Price Auctions with Budgets. LATIN 2014: 695-706 - [c43]Josep Díaz, George B. Mertzios:
Minimum Bisection Is NP-hard on Unit Disk Graphs. MFCS (2) 2014: 251-262 - [e9]Josep Díaz, Ivan Lanese, Davide Sangiorgi:
Theoretical Computer Science - 8th IFIP TC 1/WG 2.2 International Conference, TCS 2014, Rome, Italy, September 1-3, 2014. Proceedings. Lecture Notes in Computer Science 8705, Springer 2014, ISBN 978-3-662-44601-0 [contents] - [i15]Josep Díaz, George B. Mertzios:
Minimum Bisection is NP-hard on Unit Disk Graphs. CoRR abs/1404.0117 (2014) - [i14]Josep Díaz, Dieter Mitsche, Guillem Perarnau, Xavier Pérez-Giménez:
On the relation between graph distance and Euclidean distance in random geometric graphs. CoRR abs/1404.4757 (2014) - [i13]Josep Díaz, Ioannis Giotis, Lefteris M. Kirousis, Yiannis Mourtos, Maria J. Serna:
Optimizing the Social Cost of Congestion Games by Imposing Variable Delays. CoRR abs/1406.5153 (2014) - 2013
- [c42]Varsha Dani, Josep Díaz, Thomas P. Hayes, Cristopher Moore:
The Power of Choice for Random Satisfiability. APPROX-RANDOM 2013: 484-496 - [i12]Josep Díaz, Ioannis Giotis, Lefteris M. Kirousis, Evangelos Markakis, Maria J. Serna:
On the Stability of Generalized Second Price Auctions with Budgets. CoRR abs/1309.6474 (2013) - [i11]Josep Díaz, Leslie Ann Goldberg, David Richerby, Maria J. Serna:
Absorption Time of the Moran Process. CoRR abs/1311.7631 (2013) - 2012
- [j56]Josep Díaz:
Book Review: George Dyson "Turing's Cathedral: The Origins of the Digital Universe" (2012) Pantheon Books. Computer Science Review 6(4): 185-186 (2012) - [j55]Josep Díaz, Carme Torras:
A personal account of Turing's imprint on the development of computer science. Computer Science Review 6(5-6): 225-234 (2012) - [j54]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) - [c41]Josep Díaz, Olli Pottonen, Maria J. Serna, Erik Jan van Leeuwen:
On the Complexity of Metric Dimension. ESA 2012: 419-430 - [c40]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 - [i10]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) - [i9]Varsha Dani, Josep Díaz, Thomas P. Hayes, Cristopher Moore:
The Power of Choice for Random Satisfiability. CoRR abs/1211.6997 (2012) - 2011
- [j53]
- [j52]Josep Díaz:
Cris Moore, Stephen Mertens, , The Nature of Computation (2011) Oxford UP. Computer Science Review 5(4): 341-345 (2011) - [j51]
- [c39]Carme Àlvarez, Josep Díaz, Dieter Mitsche, Maria J. Serna:
Continuous Monitoring in the Dynamic Sensor Field Model. ALGOSENSORS 2011: 161-172 - [c38]Josep Díaz, Alberto Marchetti-Spaccamela, Dieter Mitsche, Paolo Santi, Julinda Stefa:
Social-Aware Forwarding Improves Routing Performance in Pocket Switched Networks. ESA 2011: 723-735 - [p1]Josep Díaz, Dieter Mitsche, Paolo Santi:
Theoretical Aspects of Graph Models for MANETs. Theoretical Aspects of Distributed Computing in Sensor Networks 2011: 161-190 - [i8]Josep Díaz, Olli Pottonen, Erik Jan van Leeuwen:
Planar Metric Dimension is NP-complete. CoRR abs/1107.2256 (2011) - [i7]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) - 2010
- [j50]
- [j49]Josep Díaz, Dieter Mitsche:
The cook-book approach to the differential equation method. Computer Science Review 4(3): 129-151 (2010) - [j48]Josep Díaz, Marcin Kaminski, Dimitrios M. Thilikos:
A note on the subgraphs of the (2×∞)-grid. Discrete Mathematics 310(3): 531-536 (2010) - [e8]Tiziana Calamoneri, Josep Díaz:
Algorithms and Complexity, 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010. Proceedings. Lecture Notes in Computer Science 6078, Springer 2010, ISBN 978-3-642-13072-4 [contents] - [i6]Josep Díaz, Alberto Marchetti-Spaccamela, Dieter Mitsche, Paolo Santi, Julinda Stefa:
Social-Aware Forwarding Improves Routing Performance in Pocket Switched Networks. CoRR abs/1007.5240 (2010)
2000 – 2009
- 2009
- [b5]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 - [j47]
- [j46]Josep Díaz, Alexis C. Kaporis, G. D. Kemkes, Lefteris M. Kirousis, Xavier Pérez, Nicholas C. Wormald:
On the chromatic number of a random 5-regular graph. Journal of Graph Theory 61(3): 157-191 (2009) - [j45]Josep Díaz, Fabrizio Grandoni, Alberto Marchetti-Spaccamela:
Balanced cut approximation in random geometric graphs. Theor. Comput. Sci. 410(27-29): 2725-2731 (2009) - [j44]Josep Díaz, Lefteris M. Kirousis, Dieter Mitsche, Xavier Pérez-Giménez:
On the satisfiability threshold of formulas with three literals per clause. Theor. Comput. Sci. 410(30-32): 2920-2934 (2009) - [j43]Josep Díaz, Dieter Mitsche, Xavier Pérez-Giménez:
Large Connectivity for Dynamic Random Geometric Graphs. IEEE Trans. Mob. Comput. 8(6): 821-835 (2009) - [c37]Josep Díaz, Dieter Mitsche, Navin Rustagi, Jared Saia:
On the Power of Mediators. WINE 2009: 455-462 - 2008
- [j42]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) - [j41]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) - [j40]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) - [j39]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) - [c36]Josep Díaz, Lefteris M. Kirousis, Dieter Mitsche, Xavier Pérez-Giménez:
A new upper bound for 3-SAT. FSTTCS 2008: 163-174 - [c35]Josep Díaz, Dieter Mitsche, Xavier Pérez-Giménez:
On the connectivity of dynamic random geometric graphs. SODA 2008: 601-610 - [i5]Josep Díaz, Dieter Mitsche, Xavier Pérez:
On the Probability of the Existence of Fixed-Size Components in Random Geometric Graphs. CoRR abs/0806.0311 (2008) - [i4]Josep Díaz, Lefteris M. Kirousis, Dieter Mitsche, Xavier Pérez-Giménez:
A new upper bound for 3-SAT. CoRR abs/0807.3600 (2008) - 2007
- [j38]
- [j37]Jan Kratochvíl, Josep Díaz, Jirí Fiala:
Editorial. Discrete Applied Mathematics 155(2): 79-80 (2007) - [j36]Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos:
Complexity issues on bounded restrictive H-coloring. Discrete Mathematics 307(16): 2082-2093 (2007) - [j35]Josep Díaz, Dieter Mitsche, Xavier Pérez:
Sharp Threshold for Hamiltonicity of Random Geometric Graphs. SIAM J. Discrete Math. 21(1): 57-65 (2007) - [j34]Josep Díaz, Marcin Kaminski:
MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs. Theor. Comput. Sci. 377(1-3): 271-276 (2007) - [j33]Carme Àlvarez, Rafel Cases, Josep Díaz, Jordi Petit, Maria J. Serna:
Communication tree problems. Theor. Comput. Sci. 381(1-3): 197-217 (2007) - [j32]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) - [i3]Josep Díaz, Dieter Mitsche, Xavier Pérez:
Dynamic Random Geometric Graphs. CoRR abs/cs/0702074 (2007) - 2006
- [c34]Josep Díaz, Fabrizio Grandoni, Alberto Marchetti-Spaccamela:
Balanced Cut Approximation in Random Geometric Graphs. ISAAC 2006: 527-536 - [c33]
- [c32]Josep Díaz, Jordi Petit, Dimitrios M. Thilikos:
Kernels for the Vertex Cover Problem on the Preferred Attachment Model. WEA 2006: 231-240 - [e7]Josep Díaz, Klaus Jansen, José D. P. Rolim, Uri Zwick:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings. Lecture Notes in Computer Science 4110, Springer 2006, ISBN 3-540-38044-2 [contents] - [i2]Josep Díaz, Dieter Mitsche, Xavier Pérez:
Sharp threshold for hamiltonicity of random geometric graphs. CoRR abs/cs/0607023 (2006) - [i1]Josep Díaz, Marcin Kaminski:
Max-Cut and Max-Bisection are NP-hard on unit disk graphs. CoRR abs/cs/0609128 (2006) - 2005
- [j31]Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos:
The restrictive H-coloring problem. Discrete Applied Mathematics 145(2): 297-305 (2005) - [j30]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) - [j29]
- [j28]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) - [c31]Josep Díaz, G. Grammatikopoulos, Alexis C. Kaporis, Lefteris M. Kirousis, Xavier Pérez, Dionisios G. Sotiropoulos:
5-Regular Graphs are 3-Colorable with Positive Probability. ESA 2005: 215-225 - [c30]Josep Díaz, Xavier Pérez, Maria J. Serna, Nicholas C. Wormald:
Connectivity for Wireless Agents Moving on a Cycle or Grid. STACS 2005: 353-364 - 2004
- [j27]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) - [c29]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 - [c28]Josep Díaz, Maria J. Serna, Nicholas C. Wormald:
Computation of the Bisection Width for Random d-Regular Graphs. LATIN 2004: 49-58 - [c27]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 - [e6]Josep Díaz, Juhani Karhumäki, Arto Lepistö, Donald Sannella:
Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings. Lecture Notes in Computer Science 3142, Springer 2004, ISBN 3-540-22849-7 [contents] - 2003
- [j26]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) - [j25]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) - [c26]Carme Àlvarez, Maria J. Blesa, Josep Díaz, Antonio Fernández, Maria J. Serna:
Adversarial Models for Priority-Based Networks. MFCS 2003: 142-151 - [c25]Josep Díaz, Jordi Petit, Maria J. Serna:
Evaluation of Basic Protocols for Optical Smart Dust Networks. WEA 2003: 97-106 - 2002
- [j24]Josep Díaz, Jordi Petit, Maria J. Serna:
A survey of graph layout problems. ACM Comput. Surv. 34(3): 313-356 (2002) - [j23]Josep Díaz:
Analysis of Algorithms (AofA): Part I: 1993 -- 1998. Bulletin of the EATCS 77: 42-62 (2002) - [j22]
- [j21]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) - [c24]Josep Díaz, Jaroslav Nesetril, Maria J. Serna, Dimitrios M. Thilikos:
H-Colorings of Large Degree Graphs. EurAsia-ICT 2002: 850-857 - [c23]Josep Díaz, Norman Do, Maria J. Serna, Nicholas C. Wormald:
Bisection of Random Cubic Graphs. RANDOM 2002: 114-125 - [c22]Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos:
The Complexity of Restrictive H-Coloring. WG 2002: 126-137 - 2001
- [j20]Carme Àlvarez, Josep Díaz, Maria J. Serna:
The hardness of intervalizing four colored caterpillars. Discrete Mathematics 235(1-3): 19-27 (2001) - [j19]Josep Díaz, Jordi Petit, Maria J. Serna, Luca Trevisan:
Approximating layout problems on random graphs. Discrete Mathematics 235(1-3): 245-253 (2001) - [j18]
- [j17]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) - [c21]Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos:
Counting H-Colorings of Partial k-Trees. COCOON 2001: 298-307 - [c20]Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos:
Recent Results on Parameterized H-Colorings. Graphs, Morphisms and Statistical Physics 2001: 65-86 - [c19]Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos:
(H, C, K)-Coloring: Fast, Easy, and Hard Cases. MFCS 2001: 304-315 - [c18]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 - 2000
- [j16]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) - [j15]Josep Díaz, Jordi Petit, Maria J. Serna:
Faulty Random Geometric Networks. Parallel Processing Letters 10(4): 343-358 (2000) - [c17]Carme Àlvarez, Rafel Cases, Josep Díaz, Jordi Petit, Maria J. Serna:
Routing Tree Problems on Random Graphs. ICALP Satellite Workshops 2000: 99-110
1990 – 1999
- 1999
- [c16]Josep Díaz, Mathew D. Penrose, Jordi Petit, Maria J. Serna:
Layout Problems on Lattice Graphs. COCOON 1999: 103-112 - [c15]Josep Díaz, Mathew D. Penrose, Jordi Petit, Maria J. Serna:
Linear Orderings of Random Geometric Graphs. WG 1999: 291-302 - 1998
- [j14]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) - [c14]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 - [c13]
- 1997
- [j13]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) - [c12]José L. Balcázar, Josep Díaz, Ricard Gavaldà:
Algorithms for Learning Finite Automata from Queries: A Unified View. Advances in Algorithms, Languages, and Complexity 1997: 53-72 - [c11]Josep Díaz, Maria J. Serna, Paul G. Spirakis:
Linear and nonlinear systems: A survey. Contemporary Trends in Discrete Mathematics 1997: 29-48 - 1996
- [j12]Josep Díaz, Maria J. Serna, Jacobo Torán:
Parallel Approximation Schemes for Problems on Planar Graphs. Acta Inf. 33(4): 387-408 (1996) - [j11]José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe:
An Optimal Parallel Algorithm for Learning DFA. J. UCS 2(3): 97-112 (1996) - [e5]Josep Díaz, Maria J. Serna:
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 [contents] - 1995
- [b4]José L. Balcázar, Josep Díaz, Joaquim Gabarró:
Structural Complexity I, Second Edition. Texts in Theoretical Computer Science. An EATCS Series, Springer 1995, ISBN 978-3-642-79237-3, pp. 1-210 - [c10]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 - 1994
- [j10]José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe:
The Query Complexity of Learning DFA. New Generation Comput. 12(4): 337-358 (1994) - [c9]José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe:
An Optimal Parallel Algorithm for Learning DFA. COLT 1994: 208-217 - 1993
- [j9]Rafael Casas, Josep Díaz, Conrado Martinez:
Average-Case Analysis on Simple Families of Trees Using a Balanced Probability Model. Theor. Comput. Sci. 117(1&2): 99-112 (1993) - [c8]Josep Díaz, Maria J. Serna, Jacobo Torán:
Parallel Approximation Schemes for problems on planar graphs (Extended Abstract). ESA 1993: 145-156 - 1992
- [j8]Ricardo A. Baeza-Yates, Rafael Casas, Josep Díaz, Conrado Martinez:
On the Average Size of the Intersection of Binary Trees. SIAM J. Comput. 21(1): 24-32 (1992) - [c7]José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe:
A Note on the Query Complexity of Learning DFA (Extended Abstract). ALT 1992: 53-62 - [c6]
- 1991
- [c5]
- [c4]
- 1990
- [b3]José L. Balcázar, Josep Díaz, Joaquim Gabarró:
Structural Complexity I. EATCS Monographs on Theoretical Computer Science 11, Springer 1990, ISBN 978-3-642-97064-1, pp. i-ix, 1-191 - [b2]José L. Balcázar, Josep Díaz, Joaquim Gabarró:
Structural Complexity II. EATCS Monographs on Theoretical Computer Science 22, Springer 1990, ISBN 978-3-642-75359-6, pp. I-IX, 1-285 - [j7]Josep Díaz, Jacobo Torán:
Classes of Bounded Nondeterminism. Mathematical Systems Theory 23(1): 21-32 (1990)
1980 – 1989
- 1989
- [j6]Rafael Casas, Josep Díaz, Jean-Marc Steyaert:
Average-Case Analysis of Robinson's Unification Algorithm with Two Different Variables. Inf. Process. Lett. 31(5): 227-232 (1989) - [c3]Carme Àlvarez, Josep Díaz, Jacobo Torán:
Complexity Classes with Complete Problems Between P and NP-C. FCT 1989: 13-24 - [e4]