Recent papers by topic

Game Theory

• Fear in Mediation: Exploiting the "Windfall of Malice" (with D. Mitsche, N. Rustagi and J. Saia) WINE 2009. (Pdf)

Networks and graph models of networks

• "Social-Aware Forwarding Improves Routing Performance in Pocket Switched Networks" (with A. Marchetti, D. Mitsche, P. Santi and Julinda Stefan") In {\em ESA-2011}, (Pdf)
• "Theoretical Graph Models for MANETs" (with D. Mitsche and P. Santi) In {\em 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

• Max-Cut and Max-Bisection are NP-hard on unit disc graphs. (with M. Kamiski) Theoretical Computer Science. 21 (1), 57--65, 2007. (Pdf)
• A survey on Graph Layout Problems (with J. Petit, M. Serna) ACM Surveys. (Poscript)
• Linear orderings of random geometric graphs. (with M. D. Penrose, J. Petit and M. Serna). Journal of Algorithms, 38, 78-116, 2001. Academic Press. (Poscript)
• Approximating Layout Problems on Random Graphs (with J.Petit, M.Serna, L. Trevisan) Discrete Mathematics, 235, 245-253, 2001 Elsevier. (Poscript)
• 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)

Morphisms on graphs

• Efficient algorithms for counting parametrized list H-coloring (with M. Serna, D. Thilikos). To appear JCSS-08. (Pdf)
• Complexity issues on bounded restrictive H-coloring (with M. Serna, D. Thilikos). To appear Discrete Applied Mathematics. (Poscript)
• Efficient algorithms for decissional parametrized H-coloring (with M. Serna, D. Thilikos). (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 large degree graphs (with J. Nesetril, M. Serna and D. Thilikos). EURASIA-ICT-2002. (Poscript)
• Counting H-colorings of partial k-trees (with M. Serna, D. Thilikos). Theoretical Computer Science. 281, 291-309, 2002. (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.

Other topics

• "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
• Fast FPT-algorithms for cleaning grids (with D. Thilikos). STACS-06 (pdf)
• 5-regular multi-graphs are 3-colorable with independent of their size positive probability (with G. Grammatikopoulos, A. Kaporis, L. Kirousis, X. Perez, D. Sotiropoulos). ESA-05 (pdf)
• Partition networks into classes of mutually isolated nodes (with A. Kaporis, L. Kirousis, X. Perez). European Conference on Complex Systems-05. (pdf)
• 5-regular multi-graphs are 3-colorable with independent of their size positive probability (with A. Kaporis, L. Kirousis, X. Perez). ESA-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)