@preamble{{\providecommand{\seealso}[1]{See also~\cite{\#1}} } # {\providecommand{\alsoavailable}[1]{Also available as {\#1}} } # {\providecommand{\nth}{$^{\mathrm{th}}$} } # {\providecommand{\ntha}{$^{\mathrm{th}}$} } # {\providecommand{\st}{$^{\mathrm{st}}$} } # {\providecommand{\sta}{$^{\mathrm{st}}$} } # {\providecommand{\nd}{$^{\mathrm{nd}}$} } # {\providecommand{\nda}{$^{\mathrm{nd}}$} } # {\providecommand{\rd}{$^{\mathrm{rd}}$} } # {\providecommand{\rda}{$^{\mathrm{rd}}$} } # {\providecommand{\andthe}{and the} } # {\providecommand{\andthea}{and the} }}
@article{BYCDM92,
author = {R. Baeza-{Y}ates and R. Casas and J. D{\'i}az and C. Mart{\'i}nez},
title = {On the average size of the intersection of binary trees},
journal = {SIAM J. Comput.},
year = 1992,
volume = 21,
number = 1,
pages = {24--32}
}
@article{CDM93,
author = {R. Casas and J. D{\'i}az and C. Mart{\'i}nez},
title = {Average-case analysis on simple families of trees using a balanced probability model},
journal = {Theoret. Comput. Sci.},
year = 1993,
volume = 117,
pages = {99--112}
}
@article{KMP95,
author = {P. Kirschenhofer and C. Mart{\'i}nez and H. Prodinger},
title = {Analysis of an optimized search algorithm for skip lists},
journal = {Theoret. Comput. Sci.},
url = {http://www.lsi.upc.edu/~conrado/research/papers/tcs-kmp95.pdf},
volume = 144,
year = 1995,
pages = {199--220}
}
@article{GMM96,
author = {J. Gabarr{\'o} and C. Mart{\'i}nez and X. Messeguer},
title = {A design of a parallel dictionary using skip lists},
journal = {Theoret. Comput. Sci.},
url = {http://www.lsi.upc.edu/~conrado/research/papers/tcs-gmm96.pdf},
year = 1996,
volume = 158,
pages = {1--33}
}
@article{FGM97,
author = {Ph. Flajolet and X. Gourdon and C. Mart{\'i}nez},
title = {Patterns in random binary search trees},
url = {http://www.lsi.upc.edu/~conrado/research/papers/rsa-fgm97.pdf},
journal = {Random Structures \& Algorithms},
year = {1997},
volume = 11,
number = 3,
pages = {223--245}
}
@article{KPM97,
author = {P. Kirschenhofer and H. Prodinger and C. Mart{\'i}nez},
title = {Analysis of {H}oare's {FIND} algorithm with median-of-three partition},
url = {http://www.lsi.upc.edu/~conrado/research/papers/rsa-kpm97.pdf},
journal = {Random Structures \& Algorithms},
year = {1997},
volume = 10,
number = {1--2},
pages = {143--156}
}
@article{MPP98,
author = {C. Mart{\'i}nez and A. Panholzer and H. Prodinger},
title = {On the number of descendants and ascendants in random search trees},
url = {http://www.lsi.upc.edu/~conrado/research/papers/ejc-mpp98.pdf},
journal = {Electronic Journal of Combinatorics},
year = {1998},
volume = 5,
number = {\#R20},
journalurl = {www.combinatorics.org}
}
@article{MR98,
author = {C. Mart{\'i}nez and S. Roura},
title = {Randomized binary search trees},
url = {http://www.lsi.upc.edu/~conrado/research/papers/jacm-mr98.pdf},
journal = {J. Assoc. Comput. Mach.},
year = 1998,
volume = 45,
number = 2,
pages = {288--323}
}
@article{MR00,
author = {C. Mart{\'i}nez and S. Roura},
title = {On the competitiveness of the move-to-front rule},
url = {http://www.lsi.upc.edu/~conrado/research/papers/tcs-mr00.pdf},
journal = {Theoret. Comput. Sci.},
year = 2000,
number = {1--2},
volume = 242,
pages = {313--325}
}
@article{MM01,
author = {C. Mart{\'i}nez and X. Molinero},
title = {A Generic Approach for the Unranking of Labelled Combinatorial Classes},
url = {http://www.lsi.upc.edu/~conrado/research/papers/rsa-mm01.pdf},
journal = {Random Structures \& Algorithms},
volume = 19,
number = {3--4},
pages = {472--497},
year = 2001
}
@article{MPP99,
author = {C. Mart{\'i}nez and A. Panholzer and H. Prodinger},
title = {Partial Match in Relaxed Multidimensional Search Trees},
url = {http://www.lsi.upc.edu/~conrado/research/papers/algorithmica-mpp01.pdf},
journal = {Algorithmica},
year = 2001,
volume = 29,
number = {1--2},
pages = {181--204}
}
@article{MR01,
author = {C. Mart{\'i}nez and S. Roura},
title = {Optimal Sampling Strategies in Quicksort and Quickselect},
url = {http://www.lsi.upc.edu/~conrado/research/papers/sicomp-mr01.pdf},
journal = {SIAM J. Comput.},
year = 2001,
volume = 31,
number = 3,
pages = {683--705}
}
@article{DM02,
author = {A. Duch and C. Mart{\'i}nez},
title = {On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures},
url = {http://www.lsi.upc.edu/~conrado/research/papers/jalgs-dm02.pdf},
journal = {J. Algorithms},
year = 2002,
xref = {DM02b,TRDM01},
volume = 44,
number = 1,
pages = {226--245}
}
@article{DM05,
author = {A. Duch and C. Mart{\'i}nez},
title = {Improving the Performance of Multidimensional Search using Fingers},
journal = {J. Experimental Algorithmics},
year = 2005,
volume = 10,
number = {2.4},
journalurl = {www.jea.acm.org},
url = {http://www.lsi.upc.edu/~conrado/research/papers/jea-dm05.pdf}
}
@article{MM05,
author = {C. Mart{\'i}nez and X. Molinero},
title = {Efficient Iteration in Admissible Combinatorial Classes},
journal = {Theoret. Comput. Sci.},
year = 2005,
volume = 346,
number = {2--3},
pages = {388--417}
}
@article{MP09,
author = {C. Mart{\'i}nez and H. Prodinger},
title = {Moves and displacements of particular elements in {Q}uicksort},
journal = {Theoret. Comput. Sci.},
year = 2009,
volume = 410,
pages = {2279--2284},
number = {21--23},
url = {http://www.lsi.upc.edu/~conrado/research/papers/tcs-mp09.pdf}
}
@article{MMPS09,
author = {C. Mart{\'i}nez and L. Moura and D. Panario and B. Stevens},
title = {Locating errors using {ELA}s, covering arrays and adaptive testing algorithms},
journal = {SIAM J. Discrete Mathematics},
year = 2009,
volume = 23,
number = 4,
pages = {1776--1799}
}
@article{DM07,
title = {Updating relaxed $K$-d trees},
author = {A. Duch and C. Mart{\'i}nez},
journal = {ACM Trans. on Algorithms},
year = 2009,
volume = 6,
number = 1,
pages = {4:1--4:24}
}
@article{MPV08,
author = {C. Mart{\'i}nez and D. Panario and A. Viola},
title = {Adaptive Sampling Strategies for Quickselect},
journal = {ACM Trans. on Algorithms},
year = 2010,
volume = 6,
number = 3,
pages = {53:1--53:32 + appendices (14 pages)}
}
@article{MPP09,
author = {C. Mart{\'i}nez and A. Panholzer and H. Prodinger},
title = {The Analysis of Range Quickselect and Related Problems},
journal = {Theoret. Comput. Sci.},
year = 2011,
url = {http://dx.doi.org/10.1016/j.tcs.2011.06.030},
pages = { 6537--6555},
volume = {412},
number = {46}
}
@article{CHM10,
title = {Psi-series method in random trees and moments of higher orders},
author = {H.-H. Chern and H.-K. Hwang and C. Mart{\'i}nez},
year = {2011},
journal = {Random Structures \& Algorithms},
note = {Submitted}
}
@article{DJM10b,
title = {Rank Selection for $K$-Dimensional Binary Search Trees},
author = {A. Duch and R. M. Jim{\'e}nez and C. Mart{\'i}nez},
year = 2011,
journal = {Random Structures \& Algorithms},
note = {Submitted}
}
@inproceedings{CDM91,
author = {R. Casas and J. D{\'i}az and C. Mart{\'i}nez},
title = {Average-case Analysis on Simple Families of Trees Using a Balanced Probability Model},
booktitle = {Proc. of the 3\rda\ Int. Col. on Formal Power Series and Algebraic Combinatorics (FPSAC)},
year = 1991,
editor = {M. Delest and G. Jacob and P. Leroux},
publisher = {LaBRI},
pages = {133--143},
note = {See also ~\cite{CDM93}}
}
@inproceedings{CDM91b,
author = {R. Casas and J. D{\'i}az and C. Mart{\'i}nez},
title = {Statistics on random trees},
booktitle = {Proc. of the 18\nth\ Int. Col. on Automata, Languages and Programming (ICALP)},
year = 1991,
series = {Lecture Notes in Computer Science },
editor = {J. Leach and B. Monien and M. Rodr{\'i}guez-Artalejo},
volume = 510,
pages = {186--203},
publisher = {Springer-Verlag},
note = {Invited lecture}
}
@inproceedings{Mar91,
author = {C. Mart{\'i}nez},
title = {Average-case analysis of equality of binary trees},
booktitle = {Proc. of the 8\tha\ Int. Conf. on Fundamentals of Computation Theory (FCT)},
year = 1991,
pages = {350--359},
volume = 529,
series = {Lecture Notes in Computer Science },
publisher = {Springer-Verlag},
editor = {L. Budach}
}
@incollection{GMM93,
author = {J. Gabarr{\'o} and C. Mart{\'i}nez and X. Messeguer},
title = {Parallel Update and Search in Skip Lists},
booktitle = {Computer Science 2: Research and Applications. Proc. of the 13\tha\ Int. Conf. Chilean Computer Science Society (SCCC)},
year = 1994,
editor = {R. {Baeza-Yates}},
pages = {15--26},
publisher = {Plenum Press},
note = {See also ~\cite{GMM96}}
}
@inproceedings{RM96,
key = {ESA'96},
author = {S. Roura and C. Mart{\'i}nez},
title = {Randomization of search trees by subtree size},
booktitle = {Proc. of the 4\nth\ European Symposium on Algorithms (ESA)},
year = 1996,
editor = {J. D{\'i}az and M.J. Serna},
publisher = {Springer-Verlag},
volume = 1136,
series = {Lecture Notes in Computer Science },
pages = {91--106},
note = {See also ~\cite{MR98}}
}
@inproceedings{VM97,
author = {G. Valiente and C. Mart{\'i}nez},
title = {An Algorithms for Graph Pattern-Matching},
booktitle = {Proc. of the 4\nth\ South American Workshop on String Processing},
volume = 8,
series = {International Informatics Series},
publisher = {Carleton University Press},
pages = {180--197},
year = 1997
}
@inproceedings{DEM98,
key = {ISAAC'98},
author = {A. Duch and V. Estivill-{C}astro and C. Mart{\'i}nez},
title = {Randomized $K$-Dimensional Binary Search Trees},
booktitle = {Proc. of the 9\nth\ Int. Symp. on Algorithms and Computation (ISAAC)},
year = 1998,
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science },
volume = 1533,
editor = {K.-Y. Chwa and O.H. Ibarra},
pages = {199--208}
}
@inproceedings{MR98b,
key = {ICALP'98},
author = {C. Mart{\'i}nez and S. Roura},
title = {Optimal sampling strategies in quicksort},
booktitle = {Proc. of the 25\nth\ Int. Col. on Automata, Languages and Programming (ICALP)},
year = 1998,
editor = {K.G. Larsen and S. Skyum and G. Winskel},
volume = 1443,
series = {Lecture Notes in Computer Science },
publisher = {Springer-Verlag},
pages = {327--338},
note = {See also ~\cite{MR01}}
}
@inproceedings{MM00,
author = {C. Mart{\'i}nez and X. Molinero},
title = {Unranking of Labelled Combinatorial Structures},
booktitle = {Proc. of the 12\tha\ Int. Col. on Formal Power Series and Algebraic Combinatorics (FPSAC)},
editor = {D. Krob and A. A. Mikhalev and A. V. Mikhalev},
pages = {288--299},
publisher = {Springer-Verlag},
year = 2000,
note = {See also ~\cite{MM01}}
}
@inproceedings{MM01b,
author = {C. Mart{\'i}nez and X. Molinero},
title = {Generic Algorithms for the Exhaustive Generation of Labelled Objects},
year = 2001,
pages = {53--58},
booktitle = {Proc. of the 4\nth\ Workshop on Random Generation of Combinatorial Structures and Bijective Combinatorics (GASCOM'01)},
note = {See also ~\cite{MM05}}
}
@inproceedings{DM02b,
key = {ICALP'02},
author = {A. Duch and C. Mart{\'i}nez},
title = {On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures},
booktitle = {Proc. of the 29\nth\ Int. Col. on Automata, Languages and Programming (ICALP)},
year = 2002,
series = {Lecture Notes in Computer Science },
volume = 2380,
editor = {P. Widmayer and F. Triguero and R. Morales and M. Hennessy and S. Eidenbenz and R. Conejo},
pages = {514--524},
publisher = {Springer-Verlag},
note = {See also ~\cite{DM02}}
}
@inproceedings{MPV02,
author = {C. Mart{\'i}nez and D. Panario and A. Viola},
title = {Analysis of Quickfind with small subfiles},
booktitle = {Proc. of the 2\nd\ Col. on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities (MathInfo)},
editor = {B. Chauvin and Ph. Flajolet and D. Gardy and A. Mokkadem},
publisher = {Birkh{\"a}user Verlag},
pages = {329--340},
year = 2002,
series = {Trends in Mathematics},
isbn = {3-7643-6933-7},
direccion = {Basel}
}
@inproceedings{MM03,
author = {C. Mart{\'i}nez and X. Molinero},
title = {Generic Algorithms for the Generation of Combinatorial Objects},
booktitle = {Proc. of the } # 28 # {\nth\ Int. Symposium on Mathematical Foundations of Computer Science (MFCS)},
year = 2003,
series = {Lecture Notes in Computer Science },
publisher = {Springer-Verlag},
volume = 2747,
editor = {B. Rovan and P. Vojt{\'a}\u{s}}
}
@inproceedings{DM04,
author = {A. Duch and C. Mart{\'i}nez},
title = {Fingered Multidimensional Search Trees},
booktitle = {Proc. of the } # 3 # {\rd\ Workshop on Efficient and Experimental Algorithms (WEA)},
year = 2004,
series = {Lecture Notes in Computer Science },
editor = {C. C. Ribeiro and S. L. Martins},
publisher = {Springer-Verlag},
pages = {228--242},
volume = 3059,
note = {See also ~\cite{DM05}}
}
@inproceedings{Mar04,
author = {C. Mart{\'i}nez},
title = {Partial Quicksort},
booktitle = {Proc. of the } # 6 # {\nth\ } # { ACM-SIAM Workshop on Algorithm Engineering and Experiments (ALENEX)} # { {\andthe} } # 1 # {\st\ ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO)},
year = 2004,
editor = {L. Arge and G.F. Italiano and R. Sedgewick},
pages = {224--228},
isbn = {0-89871-564-4},
publisher = {SIAM}
}
@inproceedings{MM04,
author = {C. Mart{\'i}nez and X. Molinero},
title = {An Experimental Study of Unranking Algorithms},
booktitle = {Proc. of the } # 3 # {\rd\ Workshop on Efficient and Experimental Algorithms (WEA)},
year = 2004,
series = {Lecture Notes in Computer Science },
editor = {C. C. Ribeiro and S. L. Martins},
publisher = {Springer-Verlag},
pages = {326--340},
volume = 3059
}
@inproceedings{MM04b,
author = {C. Mart{\'i}nez and X. Molinero},
title = {An Efficient Generic Algorithm for the Generation of Unlabelled Cycles},
booktitle = {Proc. of the } # 3 # {\rd\ Col. on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities (MathInfo)},
publisher = {Birkh{\"a}user Verlag},
year = 2004,
editor = {M. Drmota and Ph. Flajolet and D. Gardy and B. Gittenberger},
pages = {187--197},
series = {Trends in Mathematics},
isbn = {3-7643-7128-5},
direccion = {Basel}
}
@inproceedings{MPV04,
author = {C. Mart{\'i}nez and D. Panario and A. Viola},
title = {Adaptive Sampling for Quickselect},
booktitle = {Proc. of the } # 15 # {\nth\ Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
year = 2004,
pages = {440--448},
isbn = {0-89871-558-X},
note = {See also ~\cite{MPV08}}
}
@inproceedings{DalMar06,
author = {J. Daligault and C. Mart{\'i}nez},
title = {On the Variance of Quickselect},
booktitle = {Proc. of the } # 8 # {\nth\ } # { ACM-SIAM Workshop on Algorithm Engineering and Experiments (ALENEX)} # { {\andthe} } # 3 # {\rd\ ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO)},
year = 2006,
editor = {R. Raman and R. Sedgewick and M.F. Stallmann},
pages = {205--210},
isbn = {0-89871-610-1},
publisher = {SIAM}
}
@inproceedings{DucMar07,
author = {A. Duch and C. Mart{\'i}nez},
year = 2007,
booktitle = {Proc. of the } # 9 # {\nth\ } # { ACM-SIAM Workshop on Algorithm Engineering and Experiments (ALENEX)} # { {\andthe} } # 4 # {\nth\ ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO)},
editor = {D. Applegate and G. S. Brodal and D. Panario and R. Sedgewick},
pages = {194--200},
isbn = {978-0-898716-28-3},
publisher = {SIAM},
title = {On the Average Cost of Insertions on Random Relaxed $K$-d Trees},
note = {See also ~\cite{DM07}}
}
@inproceedings{MMPS08,
author = {C. Mart{\'i}nez and L. Moura and D. Panario and B. Stevens},
title = {Algorithms to locate errors using covering arrays},
booktitle = {Proc. of the } # 8 # {\nth\ Latin American Theoretical Informatics Conference (LATIN)},
year = 2008,
series = {Lecture Notes in Computer Science },
publisher = {Springer-Verlag},
editor = {E.S. Laber and C. Bornstein and L. T. Nogueira and L. Faria},
pages = {504--519},
volume = {4957},
note = {See also ~\cite{MMPS09}}
}
@inproceedings{MPP08,
title = {Generating Random Derangements},
booktitle = {Proc. of the } # 10 # {\nth\ } # { ACM-SIAM Workshop on Algorithm Engineering and Experiments (ALENEX)} # { {\andthe} } # 5 # {\nth\ ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO)},
publisher = {SIAM},
year = 2008,
author = {C. Mart{\'i}nez and A. Panholzer and H. Prodinger},
editor = {I. Munro and R. Sedgewick and W. Szpankowski and D. Wagner},
pages = {234--240}
}
@inproceedings{AM09,
author = {M. Archibald and C. Mart{\'i}nez},
title = {The Hiring Problem and Permutations},
booktitle = {Proc. of the } # 21 # {\st\ Int. Col. on Formal Power Series and Algebraic Combinatorics (FPSAC)},
year = 2009,
series = {Discrete Mathematics \& Theoretical Computer Science (Proceedings)},
pages = {63--76},
volume = {AK}
}
@inproceedings{DJM09,
title = {Rank Selection in Multidimensional Data},
booktitle = {Proc. of the } # 9 # {\nth\ Latin American Theoretical Informatics Conference (LATIN)},
series = {Lecture Notes in Computer Science },
publisher = {Springer-Verlag},
author = {A. Duch and R. M. Jim{\'e}nez and C. Mart{\'i}nez},
year = {2010},
volume = 6034,
pages = {674--685},
editor = {A. L{\'o}pez-Ortiz}
}
@inproceedings{JM10,
title = {Interval Sorting},
booktitle = {Proc. of the } # 37 # {\nth\ Int. Col. on Automata, Languages and Programming (ICALP)},
series = {Lecture Notes in Computer Science },
author = {R. M. Jim{\'e}nez and C. Mart{\'i}nez},
year = {2010},
volume = 6198,
editor = {S. Abramsky and C. Gavoille and C. Kirchner and F. Meyer auf der Heide and P.G. Spirakis},
pages = {238--249}
}
@inproceedings{MarRoe10,
title = {Partial Quicksort and Quickpartitionsort},
booktitle = {Proc. of the } # 21 # {\st\ Int. Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA)},
author = {C. Mart{\'i}nez and U. R{\"o}sler},
year = {2010},
series = {Discrete Mathematics \& Theoretical Computer Science (Proceedings)},
pages = {507--514},
volume = {AM},
editor = {M. Drmota and B. Gittenberger}
}
@inproceedings{LMP11,
title = {The {S}wedish Leader Election Protocol: Analysis and Variations},
booktitle = {Proc. of the } # 13 # {\nth\ } # { ACM-SIAM Workshop on Algorithm Engineering and Experiments (ALENEX)} # { {\andthe} } # 8 # {\nth\ ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO)},
publisher = {SIAM},
year = 2011,
author = {G. Louchard and C. Mart{\'i}nez and H. Prodinger},
editor = {Ph. Flajolet and D. Panario},
pages = {127--134}
}
@inproceedings{DMRR12,
author = {H. Daud{\'e} and C. Mart{\'i}nez and V. Rasendrahasina and V. Ravelomanana},
title = {The {MAX-CUT} of sparse random graphs},
booktitle = {Proc. of the } # 22 # {\nd\ Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
year = 2012,
note = {Accepted for publication}
}
@inproceedings{HMP12,
title = {Hiring above the $m$-th best candidate: a generalization of records in permutations},
booktitle = {Proc. of the } # 10 # {\nth\ Latin American Theoretical Informatics Conference (LATIN)},
author = {A. Helmi and C. Mart{\'i}nez and A. Panholzer},
year = {2012},
note = {Accepted for publication}
}
This file was generated by bibtex2html 1.95.