Recent papers by topic

Graph models (MANETs, Infection, RGG)

• "Reconstructing random points from geometric graphs or vertex orderings" (with C. McDiarmid and D. Mitsche) In: {\em Random Structures and Algorithms.} 57, (2), 339–370, 2020. (Pdf)
• "A survey of the modified Moran process and evolutionary graph theory." (with D. Mitsche). To appear in: {\em Computer Science Review}, 2021 (Pdf)
• "On the relation between graph distance and Euclidean distance in RGG" (with D. Mitsche, G. Peranrnau and X. Perez) In: {\em Annals of Applied Probability}, 43.8 2016 (Pdf)
• "Absorption time of the Moran process" (with L.Goldberg, D.Richby, M.Serna) Random Structures and Algorithms, 59,1, 137-159, 2016 (Arxive)
• "On the fixation probability of superstars" (with L. Goldberg, G. Mertzios, D. Richerby, M.Serna and P. Spirakis) In {\em Proc. of the Royal Society A}, 469:20130193, 2013. (Arxive)
• "Continuous monitoring in the dynamic sensor field model" (with C.Alvarez, D.Mitsche, M.Serna) In {\em Theoretical Computer Science}, 463, 114-122, 2012. (Pdf)
• "Approximating fixation probabilities in the generalized Moran process" (with L.A.Goldberg, G.Metzios, D.Richerby, M.Serna, P.Spirakis) In {\em SODA-2012}, (Pdf)
• "Social-Aware Forwarding Improves Routing Performance in Pocket Switched Networks" (with A. Marchetti, D. Mitsche, P. Santi and Julinda Stefan") In ESA-2011, (Pdf)
• "Theoretical Graph Models for MANETs" (with D. Mitsche and P. Santi) In Theoretical Aspects of Sensors Networks, 161-190, Springer, 2011. (Pdf)
• "Balanced Cut Approximation in Random Geometric Graphs" (with F. Grandoni and A. Marchetti) In {\em Theoretical Computer Science}, 410, 2725-2731, 2009. (Pdf)
• "On the Probability of existence of fixed-size components in RGG" (with D. Mitche and X. Perez) In: {\em Advances in Applied Probability} 41, 1-14, 2009. (pdf).
• "Connectivity of Dynamic Random Geometric Graphs'' (with D. Mitche and X. Perez) In: {\em IEEE Trans. Mobile computing} 6, 6, 821-835, 2009. (pdf)
• Routing trees for random graphs (with C. Alvarez, R. Cases, J. Petit, M. Serna) Theoretical Computer Science 21 (1), 57--65, 2007. (pdf)
• On the walkers problem (with X. Perez, M.J. Serna, N. Wormald). In SIAM J. Discrete Math. 22, 2, 747-775, 2008 (pdf)
• Sharp threshold for Hamiltonicity of Random Geometric Graphs (with D. Mitsche, X. Perez). SIAM J. Discrete Math. 21 (1), 57--65, 2007. (pdf)
• High level communication functionality for wireless sensor networks. (with C. Alvarez, J. Petit, J. Rolim, M.J. Serna). In: Theoretical Computer Science, 406, 240-247, 2008. (ps)
• Chromatic number of random scaled sector graphs (with V. Sanwalani, M. Serna, P. Spirakis). Theoretical Computer Science, 349, (2005), 40-51. (Poscript)
• Evaluatiopn of Basic protocols for optical smart dust networks (with J.Petit, M.J. Serna). In Experimental and efficient algorithms-2003 (ps)
• Computation of the bisection for random d-regular graphs (with M. Serna, N. Wormald). Theoretical Ccomputer Science, 382(2007) 120-130. (ps)
• Evaluation of basic protocols for optical smart dust networks (with J.Petit, M.J. Serna). IEEE Transactions Mobile Networks, 2 (3), 186-196, 2003 (Poscript)
• Adversarial models for priority-based networks (with C.Alvarez, M. Blesa, A. Fernandez, M.J. Serna). Networks, 2004. (Pdf)
• Bisection of random cubic and 4-regular graphs (with N. Do, M. Serna, N. Wormald). Theoretical Computer Science, 307, 531-548, 2003. (Poscript)
• The complexity of deciding stability under FFS in the adversarial model (with C.Alvarez, M. Blesa, A. Fernandez, M.J. Serna). Information Processing Latters, 90, 261-266, 2004. (Poscript)
• Bisection of random cubic graphs (with N. Do, M. Serna, N. Wormald). Random-02. (Poscript)
• Stability and non-stability of the FIFO protocol (with D. Kokoupoulos, N. Nikoletseas, M. Serna, P. Spirakis, D. Thilikos) SPAA-2001. (Poscript)
• Modelos de grafos para la web (in Spanish) (with C. Alvarez, M. Serna). In: Las Matematicas del siglo XX. A. Martin\'on (ed.). Ed. Nivola, pp. 477-480. 2000. (Poscript)

Layouts and other graph's problems

• "Min. Bisection is NP-hard on UDG" (with G. Mertzios) Information amd Computation, To appear 2017. (Arxive)
• On the complexity of metric dimension" (with O.Potonen, M.Serna, E. van Leeuwen") In Journal of Computer and System Sciences, To appear 2017. (Pdf)
• Efficient algorithms for counting parametrized list H-coloring (with M. Serna, D. Thilikos). Journal of Computer and System Science 74, 919-937,2008. (Pdf)
• Complexity issues on bounded restrictive H-coloring (with M. Serna, D. Thilikos). Discrete Applied Mathematics, 307,16, 2082-2993, 2007. (Poscript)
• Max-Cut and Max-Bisection are NP-hard on unit disc graphs. (with M. Kamiski) Theoretical Computer Science. 21 (1), 57--65, 2007. (Pdf)
• Efficient algorithms for decissional parametrized H-coloring (with M. Serna, D. Thilikos). In: "Topics in Discrete Mathematics", 105-125. Springer, 2006 (Poscript)
• Fixed parameter algorithms for counting and deciding bounded restrictive list H-colorings (with M. Serna, D. Thilikos). In ESA-2004. (Poscript)
• Recent Results on Parametrized H-coloring (with M. Serna, D. Thilikos). DIMACS, Contemporary Trends in Discrete Math. vol. 63, AMS, 2004 (Poscript)
• The restrictive H-coloring (with M. Serna, D. Thilikos). Discrete Applied Mathematics, 2004. (Poscript)
• "H-coloring of graphs" In: "Current trends in Theoretical Computer Science" 5-18, World Scientific, 2004. (Poscript)
• A survey on Graph Layout Problems (with J. Petit, M. Serna) ACM Surveys, 34, 313-356,2002.. (Poscript)
• Counting H-colorings of partial k-trees (with M. Serna, D. Thilikos). Theoretical Computer Science. 281, 291-309, 2002. (Poscript)
• H-coloring of large degree graphs (with J. Nesetril, M. Serna and D. Thilikos). EURASIA-ICT-2002. (Poscript)
• Linear orderings of random geometric graphs. (with M. D. Penrose, J. Petit and M. Serna). Journal of Algorithms, 38, 78-116, 2001. (Poscript)
• Approximating Layout Problems on Random Graphs (with J.Petit, M.Serna, L. Trevisan) Discrete Mathematics, 235, 245-253, 2001 (Poscript).
• H--Colorings of Graphs. Bulletin of the EATCS, 75. 82-92, 2001. (Poscript)
• (H,C,k)-coloring: Fast, easy and hard cases (with M. Serna, D. Thilikos). MFCS-2001. (Poscript)
• The hardness of Intervalizing Four Colored caterpillars (with C. Alvarez, M. Serna), Discrete Mathematics, 235, pg. 19-27, 2001 Elsevier.
• Convergence theorems for some layout measures on random lattice and random geometric graphs (with M.D. Penrose, J. Petit, M. J. Serna) Combinatorics, Probability and Computing, 9, 489-511, 2000. Cambridge U. Press. (Poscript)
• Faulty random geometric graphs: Emulations and linear layouts (with J.Petit, M.Serna). Parallel Processing Letters, 10, 4, 343--357, 2000. World Scientific. (Poscript)
• Intervalizing colored graphs is NP-complete for caterpillars with hair length 2 (with C. Alvarez, M. Serna) (September 1998). (Poscript)

Other topics

• "Smoothed Analysis of the Expected Number of Maximal Points in Two Dimensions" (with Mordecai Golin) In Theory of Computer Systems, 59,1, 1-21,2016. (Pdf)
• "On the stability of generalized second prize auctions" (with I.Giotis, L.Kirousis, E.Markakis, M. Serna) In Theory of Computer Systems, 59,1, 1-21,2016. (Pdf)
• "The power of choice for random satisfiability" (with V. Dani, T. Hayes, C. Moore) In {\em ArXive}, RANDOM-2013. (Pdf)
• "A personal account of Turing's imprint on the development of computer science" (with C. Torras) In {\em Computer Science Review}, 6, 225-234, 2012. (Pdf)
• "The cook-book approach to the differential equation method" (with D. Mitsche) In {\em Computer Science Review}, 4, 129-153, 2010. (Pdf)
• A note on the subgraphs of the (2 times infinit)-grid (with M. Karminski and D. Thilikos). In {\em Discrete Mathematics} 310, 531-536, 2010. (Pdf)
• A new upper-bound for 3-SAT (with L. Kirousis, D. Mitsche, X. Perez). In {\em Theoretical Computer Science} 410, 2920-2934, 2009. pdf
• Fear in Mediation: Exploiting the "Windfall of Malice" (with D. Mitsche, N. Rustagi and J. Saia) WINE 2009. (Pdf)
• Fast FPT-algorithms for cleaning grids (with D. Thilikos). STACS-06 (pdf)
• Partition networks into classes of mutually isolated nodes (with A. Kaporis, L. Kirousis, X. Perez). European Conference on Complex Systems-05. (pdf)
• Primes in P (without assumptions). Bulletin EATCS, 78, 67-71, 2002. (Poscript)
• A guide to concentration bounds (with J. Petit, M. Serna). In: Handbook of Randomized Computing - Edited by S. Rajasekaran, P. Pardalos, J. Reif and J. Rolim. 457-507, Kluwer, 2001.. (Poscript)
• On the average complexity of the circuit value problem (with M. Serna, P. Spirakis and T. Tsukiji). (Poscript)

Book Reviews

• A review of the books: "The Making of a New Science" by Giorgio Ausiello and "Valley of Genius" by Adam Fisher To appear: {\em Computer Science Review}, 2019. (Pdf)
• A review of the book: "Turing's cathedral: The origins of the digital universe" by George Dyson {\em Computer Science Review}, 6, 185-187, 2012. (Pdf)
• A review of the book: "The nature of computation" by C. Moore and S. Mertens. {\em Computer Science Review}, 5, 341-345, 2011. (Pdf)
• A review of the book: "Concentration measure for the analysis of randomized algorithms" by P. Dubhashi and A. Panconesi. {\em Computer Science Review}, 4, 125-127, 2009. (Pdf)