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)