Mybiblio




Conferences




@INPROCEEDINGS{FH10,
  AUTHOR        = {Gianni Franceschini and Torben Hagerup},
  TITLE         = {Computing Maximum Suffixes
with Fewer Comparisons},
  BOOKTITLE = {Proceedings of the 7th International Conference on Algorithms and
Complexity (CIAC)},
  YEAR          = 2010
}


@INPROCEEDINGS{FGM09a,
  AUTHOR        = {Gianni Franceschini, Roberto Grossi and S. Muthukrishnan},
  TITLE         = {Optimal Cache-Aware Suffix Selection},
  BOOKTITLE = {Proceedings of the 26th Symposium on Theoretical Aspects of Computer 
  Science (STACS)},
  YEAR          = 2009
}





@INPROCEEDINGS{FMP07,
  AUTHOR        = {Gianni Franceschini, S. Muthukrishnan and Mihai P\v{a}tra\c{s}cu},
  TITLE         = {Radix Sorting With No Extra Space},
  BOOKTITLE = {Proceedings of the 15th European Symposium on Algorithms ({ESA})},
  YEAR          = 2007
}



@INPROCEEDINGS{FM07b,
  AUTHOR = {Gianni Franceschini and S. Muthukrishnan},
  TITLE = {In-Place Suffix Sorting},
  BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming ({ICALP})},
  YEAR = 2007
}



@INPROCEEDINGS{FM07a,
  AUTHOR = {Gianni Franceschini and S. Muthukrishnan},
  TITLE = {Optimal Suffix Selection},
  BOOKTITLE = {Proceedings of the 39th {ACM} Symposium on Theory of Computing ({STOC})},
  YEAR = 2007
}



@INPROCEEDINGS{Fra06b,
  AUTHOR        = {Gianni Franceschini},
  TITLE         = {Sorting by Merging or Merging by Sorting?},
  BOOKTITLE = {Proceedings of the 10th Scandinavian 
               Workshop on Algorithm Theory ({SWAT})},
  PAGES = 77--89,
  YEAR          = 2006
}




@INPROCEEDINGS{FM06a,
  AUTHOR = {Gianni Franceschini and J. Ian Munro},
  TITLE = {Implicit Dictionaries with {$O(1)$} Modifications per Update and Fast 
  Search},
  BOOKTITLE = {Proceedings of the 17th Annual {ACM-SIAM} Symposium on
                 Discrete Algorithms ({SODA})},
  PAGES = 404--413,
  YEAR = 2006
}



@INPROCEEDINGS{FFFM05a,
  AUTHOR = {Arash Farzan, Paolo Ferragina, Gianni Franceschini and Ian Munro},
  TITLE = {Cache-oblivious comparison-based algorithms on multisets},
  BOOKTITLE = {Proceedings of the 13th European Symposium on Algorithms ({ESA})},
  PAGES = 305--316,
  YEAR = 2005
}


@INPROCEEDINGS{FG05a,
  AUTHOR = {Gianni Franceschini and Roberto Grossi},
  TITLE = {Optimal In-Place Sorting of Vectors and Records},
  BOOKTITLE = {Proceedings of the 32nd International Colloquium on Automata,
  Languages and Programming ({ICALP})},
  PAGES = 90--102,
  YEAR = 2005
}



@INPROCEEDINGS{Fra05a,
  AUTHOR = {Gianni Franceschini},
  TITLE = {{S}orting {S}tably, {I}n-{P}lace, with {$O(n\log n)$} {C}omparisons and  
  {$O(n)$} {M}oves},
  BOOKTITLE = {Proceedings of the 22nd Symposium on Theoretical Aspects of Computer 
  Science (STACS)},
  PAGES = 629--640,
  YEAR = 2005
}



@INPROCEEDINGS{FG04b,
  AUTHOR = {Gianni Franceschini and Roberto Grossi},
  TITLE = {No {S}orting? Better {S}earching!},
  BOOKTITLE = {Proceedings of the 45th Annual IEEE Symposium on Foundations of 
  Computer Science (FOCS)},
  PAGES = 491--498,
  YEAR = 2004
}



@INPROCEEDINGS{FG04a,
  AUTHOR = {Gianni Franceschini and Roberto Grossi},
  TITLE = {A General Technique for Managing Strings in Comparison-Driven Data 
  Structures},
  BOOKTITLE = {Proceedings of the 31st International Colloquium on Automata,
  Languages and Programming ({ICALP})},
  PAGES = 606--617,
  YEAR = 2004
}



@INPROCEEDINGS{Fra04a,
  AUTHOR = {Gianni Franceschini},
  TITLE = {Proximity Mergesort: Optimal In-Place Sorting in the 
  Cache-Oblivious Model},
  BOOKTITLE = {Proceedings of the 15th Annual {ACM-SIAM} Symposium on
                 Discrete Algorithms ({SODA})},
  PUBLISHER = {SIAM},
  PAGES = 291--299,
  YEAR = 2004
}



@INPROCEEDINGS{FG03d,
  AUTHOR = {Gianni Franceschini and Viliam Geffert},
  TITLE = {An {I}n-{P}lace {S}orting with {$O(n\log n)$}~{C}omparisons and 
  {$O(n)$}~{M}oves},
  BOOKTITLE = {Proceedings of the 44th Annual IEEE Symposium on Foundations of 
  Computer Science (FOCS)},
  PAGES = 242--250,
  YEAR = 2003
}



@INPROCEEDINGS{FG03c,
  AUTHOR = {Gianni Franceschini and Roberto Grossi},
  TITLE = {Optimal Worst-Case Operations for Implicit
  Cache-Oblivious Search Trees},
  BOOKTITLE = {Proceedings of the 8th International Workshop on Algorithms and Data
  Structures ({WADS})},
  PAGES = 114--126,
  YEAR = 2003
}


@INPROCEEDINGS{FG03b,
  AUTHOR = {Gianni Franceschini and Roberto Grossi},
  TITLE = {Optimal Cache-Oblivious Implicit Dictionaries},
  BOOKTITLE = {Proceedings of the 30th International Colloquium on Automata, 
Languages and Programming ({ICALP})},
  PAGES = 316--331,
  YEAR = 2003
}


@INPROCEEDINGS{FG03a,
  AUTHOR = {Gianni Franceschini and Roberto Grossi},
  TITLE = {Implicit Dictionaries Supporting Searches and Amortized
   Updates in {$O(\log n \log\log n)$}},
  BOOKTITLE = {Proceedings of the 14th Annual {ACM-SIAM} Symposium on
                 Discrete Algorithms ({SODA})},
  PUBLISHER = {SIAM},
  PAGES = {670--678},
  YEAR = 2003
}


@INPROCEEDINGS{FGMP02,
  AUTHOR = {Gianni Franceschini and Roberto Grossi and J. Ian Munro and Linda Pagli},
  TITLE = {Implicit {B}-trees: New Results for the Dictionary Problem},
  BOOKTITLE = {Proceedings of the 43rd Annual IEEE Symposium on Foundations of
   Computer Science (FOCS)},
  PAGES = 145--154,
  YEAR = {2002}
}


@INPROCEEDINGS{FFLP01,
  AUTHOR = {Lino Flores Pacheco and Gianni Franceschini and Fabrizio Luccio 
  and Linda Pagli},
  TITLE = {{D}ecomposition of $k$-{D}ense {T}rees},
  BOOKTITLE = {Proceedings of 3rd Symposium on Distributed Data and Structures},
  YEAR = 2001
}



Journals



@article{Franceschini2011279,
title = "Finding the maximum suffix with fewer comparisons",
journal = "Journal of Discrete Algorithms",
volume = "9",
number = "3",
pages = "279 - 286",
year = "2011",
note = "Selected papers from the 7th International Conference on Algorithms and Complexity (CIAC 2010)",
issn = "1570-8667",
doi = "10.1016/j.jda.2011.03.008",
url = "http://www.sciencedirect.com/science/article/pii/S1570866711000384",
author = "Gianni Franceschini and Torben Hagerup",
keywords = "String algorithms",
keywords = "Maximum suffix",
keywords = "Character comparisons"
}




@ARTICLE{FG07a,
  AUTHOR = {Gianni Franceschini and Roberto Grossi},
  TITLE = {No {S}orting? Better {S}earching!},
  JOURNAL = {ACM Transactions on Algorithms},
  YEAR = 2007
}




@ARTICLE{FG06a,
  AUTHOR = {Gianni Franceschini and Roberto Grossi},
  TITLE = {Optimal Implicit Dictionaries over Unbounded Universes},
  JOURNAL = {Theory of Computing Systems},
  VOLUME = 39,
  NUMBER = 2,
  PAGES = "321--345",
  YEAR = 2006
}



@ARTICLE{Fra06a,
  AUTHOR = {Gianni Franceschini},
  TITLE = {Sorting Stably, In-Place, with $O(n\log n)$ Comparisons and  $O(n)$ Moves},
  JOURNAL = {Theory of Computing Systems. To appear.},
  YEAR = 2006
}


@ARTICLE{FG05c,
  AUTHOR = {Gianni Franceschini and Viliam Geffert},
  TITLE = {In-Place Sorting with $O(n\log n)$ Comparisons and $O(n)$ Moves},
  JOURNAL = {Journal of the ACM},
  VOLUME = 52,
  NUMBER = 4,
  PAGES = 515--537,
  YEAR = 2005
}


@ARTICLE{FLP05a,
  AUTHOR = {Gianni Franceschini, Fabrizio Luccio and Linda Pagli},
  TITLE = {Dense trees: a new look at degenerate graphs},
  JOURNAL = {Journal of Discrete Algorithms. To appear.},
  YEAR = 2005
}




@ARTICLE{FGMP04,
  AUTHOR = {Gianni Franceschini and Roberto Grossi and J. Ian Munro
  and Linda Pagli},
  TITLE = {Implicit B-trees: A New Data Structure for the Dictionary Problem},
  JOURNAL = {Journal of Computer and System Sciences},
  VOLUME = 68,
  NUMBER = 4,
  PAGES = "788--807",
  YEAR = 2004
}