Mybiblio
Unpublished papers
@MISC{Fra07a,
AUTHOR = {Gianni Franceschini and Torben Hagerup},
TITLE = {Computing Maximum Suffixes with Fewer Comparisons},
HOWPUBLISHED = {Submitted for publication},
YEAR = 2007
}
@MISC{FK06a,
AUTHOR = {Gianni Franceschini and Jyrki Katajainen},
TITLE = {Generic Algorithm for 0/1-Sorting},
HOWPUBLISHED = {Submitted for publication},
YEAR = 2006
}
@MISC{Fra06c,
AUTHOR = {Gianni Franceschini and Roberto Grossi},
TITLE = {Stable Sorting of Multisets in the Cache-Oblivious Model
(and its application to Google's MapReduce)},
HOWPUBLISHED = {Submitted for publication},
YEAR = 2006
}
Conferences
@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{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
}