RESEARCH & PUBLICATIONS

I currently have 61 publications (24 journals) with 46 coauthors. According to Google Scholar, my papers received over 1000 citations and my h-index is 17.

RESEARCH INTERESTS
My research is focused on the design and analysis of algorithms and data structures. My main areas of interest are:
O Approximation algorithms [14,15,17,23,27,33,34,39,40,41,45,46,47,48,51,53,54,55,56,57,58,59,60]
O Exact and parameterized algorithms [4,5,6,9,10,11,12,16,19,20,21,35,36,37,38,42,49,61]
O Resilient algorithms and data structures [13,22,25,26,30,43,44,50]
O Distributed algorithms [7,8,28,29,31,32,52]
O Other
 [1,2,3,18,24]


PUBLICATIONS
These are the preprints of some papers of mine. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

To Appear
p 61) Sharp separation and applications to exact and parameterized algorithms. F. V. Fomin, F. Grandoni, D. Lokshtanov, and S. Saurabh. To appear in Algorithmica. DOI 10.1007/s00453-011-9555-9.

2011
p 60) Budgeted matching and budgeted matroid intersection via the gasoline puzzle. A. Berger, V. Bonifaci, F. Grandoni, and G. Schäfer. Mathematical Programming, 128(1-2): 355-372, 2011.
p 59) Approximation algorithms for union and intersection covering problems. M. Cygan, F. Grandoni, S. Leonardi, M. Mucha, M. Pilipczuk, and P. Sankowski. To appear in Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2011.
p 58) Pricing on paths: a PTAS for the highway problem. F. Grandoni and T. Rothvoß. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 675-684, 2011.
p 57) Approximation algorithms for single and multi-commodity connected facility location. F. Grandoni and T. Rothvoß. Conference on Integer Programming and Combinatorial Optimization (IPCO), 248-260, 2011.
p 56) From uncertainty to non-linearity: Solving virtual private network via single-sink buy-at-bulk. F. Grandoni, T. Rothvoß, and L. Sanità. Mathematics of Operations Research, 36(2): 185-204, 2011.

2010
p 55) Stable routing under the spanning tree protocol. F. Grandoni, G. Nicosia, G. Oriolo, and L. Sanità. Operations Research Letters, 38(5): 399-404, 2010.
p 54) Online network design with outliers. A. Anagnostopoulos, F. Grandoni, S. Leonardi, and P. Sankowski. In International Colloquium on Automata, Languages and Programming (ICALP), 114-126, 2010.
p 53) An improved LP-based approximation for Steiner tree. J. Byrka,  F. Grandoni, T. Rothvoß, and L. Sanità. In ACM Symposium on Theory of Computing (STOC), 583-592, 2010. Best Paper Award.
p 52) Low degree connectivity of ad-hoc networks via percolation. E. De Santis, F. Grandoni, and A. Panconesi. Advances in Applied Probability, 42(2): 559-576, 2010.
p 51) Connected facility location via random facility sampling and core detouring. F. Eisenbrand, F. Grandoni, T. Rothvoß, and G. Schäfer. Journal of Computer and System Sciences, 76: 709-726, 2010.
p 50) Data structures resilient to memory faults: an experimental study of dictionaries. U. Ferraro-Petrillo,  F. Grandoni, and G. F. Italiano. In International Symposium on Experimental Algorithms (SEA), 398-410, 2010.
p 49) Sharp separation and applications to exact and parameterized algorithms. F. V. Fomin, F. Grandoni, D. Lokshtanov, and S. Saurabh. In Latin American Theoretical Informatics Symposium (LATIN), 72-83, 2010.
p 48) Utilitarian mechanism design for multi-objective optimization. F. Grandoni, P. Krysta, S. Leonardi, and C. Ventre. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 573-584, 2010.
p 47) Network design via core detouring for problems without a core. F. Grandoni and T. Rothvoß. In International Colloquium on Automata, Languages and Programming (ICALP), 490-502, 2010.
p 46) Approximation schemes for multi-budgeted independence systems. F. Grandoni and R. Zenklusen. In European Symposium on Algorithms (ESA), 536-548, 2010.

2009
p 45) Balanced cut approximation in random geometric graphs. J. Diaz, F. Grandoni, and A. Marchetti-Spaccamela. Theoretical Computer Science, 410(27-29): 2725-2731, 2009.
p 44) Resilient dictionaries. I. Finocchi, F. Grandoni, and G. F. Italiano. ACM Transactions on Algorithms, 6(1), 2009.
p 43) Optimal resilient sorting and searching in the presence of dynamic memory faults. I. Finocchi, F. Grandoni, and G. F. Italiano. Theoretical Computer Science, 410(44): 4457--4470, 2009. Special issue devoted to the best papers of ICALP'06.
p 42) A measure & conquer approach for the analysis of exact algorithms. F. V. Fomin, F. Grandoni, and D. Kratsch. Journal of the ACM 56(5), 2009.
p 41) Iterative rounding for multi-objective optimization problems. F. Grandoni, R. Ravi, and M. Singh. In European Symposium on Algorithms (ESA), 95-106, 2009.

2008
p

40) Budgeted matching and budgeted matroid intersection via the gasoline puzzle. A. Berger, V. Bonifaci, F. Grandoni, and G. Schäfer. In Conference on Integer Programming and Combinatorial Optimization (IPCO), 273-287, 2008.
O

39) Approximating connected facility location problems via random facility sampling and core detouring. F. Eisenbrand, F. Grandoni, T. Rothvoß, and G. Schäfer. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1174-1183, 2008.
O 38) Solving connected dominating set faster than 2^n. F. V. Fomin, F. Grandoni, and D. Kratsch. Algorithmica, 52(2): 153-166, 2008.
p 37) Faster Steiner tree computation in polynomial space. F. V. Fomin, F. Grandoni, and D. Kratsch. In European Symposium on Algorithms (ESA), 430-441, 2008.
p 36) Exact algorithms for dominating set. F. V. Fomin, F. Grandoni, and D. Kratsch. Entry of Encyclopedia of Algorithms, 2008.
p 35) Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. F. V. Fomin, F. Grandoni, A. V. Pyatkin, and A. A. Stepanov. ACM Transactions on Algorithms, 5(1), 2008.
p 34) Set covering with our eyes closed. F. Grandoni, A. Gupta, S. Leonardi, P. Miettinen, P. Sankowski, M. Singh. In IEEE Symposium on Foundations of Computer Science (FOCS), 347-356, 2008.
p 33) A short proof of the VPN tree routing conjecture on ring networks. F. Grandoni, V. Kaibel, G. Oriolo, and M. Skutella. Operations Research Letters, 36(3): 361-365, 2008.
p 32) Distributed  weighted vertex cover via maximal matchings. F. Grandoni, J. Könemann, and A. Panconesi. ACM Transactions on Algorithms, 5(1), 2008.
p 31) A primal-dual bicriteria distributed algorithm for capacitated vertex cover.  F. Grandoni, J. Könemann, A. Panconesi, and M. Sozio. SIAM Journal on Computing, 38(3): 825-840, 2008.

2007
O

30) Optimal resilient dynamic dictionaries. G. S. Brodal, R. Fagerberg, I. Finocchi, F. Grandoni, G. F. Italiano, A. G. Jørgensen, G. Moruz, and T. Mølhave. In European Symposium on Algorithms (ESA), pages 347-358, 2007.
O

29) Fast low degree connectivity of ad-hoc networks via percolation. E. De Santis, F. Grandoni, and A. Panconesi. In European Symposium on Algorithms (ESA), pages 206-217, 2007.
O

28) Distributed approximation algorithms via LP-duality and randomization. D. Dubhashi, F. Grandoni, and A. Panconesi. Chapter 13 of “Handbook of Approximation Algorithms and Metaheuristics”. Taylor and Francis, 2007.
O 27) New approaches for virtual private network design. F. Eisenbrand, F. Grandoni, G. Oriolo, and M. Skutella. SIAM Journal on Computing, 37(3):706-721, 2007.
O

26) Resilient search trees. I. Finocchi, F. Grandoni, and G. F. Italiano. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 547-555, 2007.
p
 25) Designing reliable algorithms in unreliable memories. I. Finocchi, F. Grandoni, and G. F. Italiano.
Computer Science Review, 1(2): 77-87, 2007.

2006
O

24) A linear time algorithm to list the minimal separators of chordal graphs. L. S. Chandran and F. Grandoni. Discrete Mathematics, 306(3):351-358, 2006.
O

23) Balanced cut approximation in random geometric graphs. J. Diaz, F. Grandoni, and A. Marchetti-Spaccamela. In International Symposium on Algorithms and Computation (ISAAC), pages 527-536, 2006.
O

22) Optimal resilient sorting and searching in the presence of memory faults. I. Finocchi, F. Grandoni, and G. F. Italiano. In International Colloquium on Automata, Languages and Programming (ICALP), pages 286-298, 2006.
O

21) Measure and conquer: a simple O(2^{0.288 n}) independent set algorithm. F. Fomin, F. Grandoni, and D. Kratsch. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 18-25, 2006.
O

20) Solving connected dominating set faster than 2^n. F. Fomin, F. Grandoni, and D. Kratsch. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 152-163, 2006.
O

19) A note on the complexity of minimum dominating set. F. Grandoni. Journal of Discrete Algorithms, 4(2):209-214, 2006.
O

18) Algorithms and constraint programming. F. Grandoni and G. F. Italiano. In Principles and Practice of Constraint Programming (CP), pages 2-14, 2006.
O

17) Improved approximation for single-sink buy-at-bulk. F. Grandoni and G. F. Italiano. In International Symposium on Algorithms and Computation (ISAAC), pages 111-120, 2006.

2005
O

16) Refined memorisation for vertex cover. L. S. Chandran and F. Grandoni. Information Processing Letters, 93(3):123--131, 2005.
O

15) An improved approximation algorithm for virtual private network design. F. Eisenbrand and F. Grandoni. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 928--932, 2005.
O

14) New approaches for virtual private network design. F. Eisenbrand, F. Grandoni, G. Oriolo, and M. Skutella. In International Colloquium on Automata, Languages and Programming (ICALP), pages 1151-1162, 2005.
O

13) Designing reliable algorithms in unreliable memories. I. Finocchi, F. Grandoni, and G. F. Italiano. In European Symposium on Algorithms (ESA), pages 1-8, 2005.
O

12) Measure and conquer: domination - a case study. F. Fomin, F. Grandoni, and D. Kratsch. In International Colloquium on Automata, Languages and Programming (ICALP), pages 191-203, 2005.
O

11) Some new techniques in design and analysis of exact (exponential) algorithms. F.V. Fomin, F. Grandoni, and D. Kratsch. Bulletin of the European Association for Theoretical Computer Science 87:47--77, 2005.

O

10) Bounding the number of minimal dominating sets: a measure and conquer approach. F. Fomin, F. Grandoni, A. Pyatkin, and A. A. Stepanov. In International Symposium on Algorithms and Computation (ISAAC), pages 573-582, 2005.
O 9) On the maximum number of minimal dominating sets in graphs. F. Fomin, F. Grandoni, A. Pyatkin, and A. A. Stepanov. Electronic Notes in Discrete Mathematics 22: 157-162, 2005.
O

8) Distributed weighted vertex cover via maximal matchings. F. Grandoni, J. Könemann, and A. Panconesi. In International Computing and Combinatorics Conference (COCOON), pages 839-848, 2005.
O

7) Primal-dual based distributed algorithms for vertex cover with semi-hard capacities. F. Grandoni, J. Könemann, A. Panconesi, and M. Sozio. In ACM Symposium on Principles of Distributed Computing (PODC), pages 118-125, 2005.

2004
O
 6) Refined memorisation for vertex cover. L. S. Chandran and F. Grandoni. In International Workshop on Parameterized  and Exact Computation (IWPEC), pages 61--70, 2004.
O

5) On the complexity of fixed parameter clique and dominating set. F. Eisenbrand and F. Grandoni. Theoretical Computer Science, 326(1-3):57--67, 2004.
O

4) Exact algorithms for hard graph problems. F. Grandoni. PhD thesis, Università di Roma “Tor Vergata”, Roma, Italy, March 2004.
O

3) Decremental clique problem. F. Grandoni and G. F. Italiano. In International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pages 142--153, 2004.

2003
O

2) Detecting directed 4-cycles still faster. F. Eisenbrand and F. Grandoni. Information Processing Letters, 87(1):13--15, 2003.
O

1) Improved algorithms for max-restricted path consistency. F. Grandoni and G. F. Italiano. In Principles and Practice of Constraint Programming (CP), pages 858--862, 2003.



CITATIONS
The number of citations of my 17 most cited papers is:
O 116 Measure and conquer: domination - a case study. F. Fomin, F. Grandoni, and D. Kratsch. In International Colloquium on Automata, Languages and Programming (ICALP), pages 191-203, 2005.
O 114 Measure and conquer: a simple O(2^{0.288 n}) independent set algorithm. F. Fomin, F. Grandoni, and D. Kratsch. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 18-25, 2006.
O 75 Some new techniques in design and analysis of exact (exponential) algorithms. F.V. Fomin, F. Grandoni, and D. Kratsch. Bulletin of the European Association for Theoretical Computer Science 87:47--77, 2005.
O 61 A measure & conquer approach for the analysis of exact algorithms. F. V. Fomin, F. Grandoni, and D. Kratsch. Journal of the ACM 56(5), 2009.
O 55 A note on the complexity of minimum dominating set. F. Grandoni. Journal of Discrete Algorithms, 4(2):209-214, 2006.
O 53 An improved LP-based approximation for Steiner tree. J. Byrka,  F. Grandoni, T. Rothvoß, and L. Sanità. In ACM Symposium on Theory of Computing (STOC), 583-592, 2010. Best Paper Award.
O 34 Solving connected dominating set faster than 2^n. F. V. Fomin, F. Grandoni, and D. Kratsch. Algorithmica, 52(2): 153-166, 2008.
O 33 Approximating connected facility location problems via random facility sampling and core detouring. F. Eisenbrand, F. Grandoni, T. Rothvoß, and G. Schäfer. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1174-1183, 2008.
O 31 Refined memorisation for vertex cover. L. S. Chandran and F. Grandoni. Information Processing Letters, 93(3):123--131, 2005.
O 29 Bounding the number of minimal dominating sets: a measure and conquer approach. F. Fomin, F. Grandoni, A. Pyatkin, and A. A. Stepanov. In International Symposium on Algorithms and Computation (ISAAC), pages 573-582, 2005.
O 27 Solving connected dominating set faster than 2^n. F. Fomin, F. Grandoni, and D. Kratsch. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 152-163, 2006.
O 25 Improved approximation for single-sink buy-at-bulk. F. Grandoni and G. F. Italiano. In International Symposium on Algorithms and Computation (ISAAC), pages 111-120, 2006.
O 24 An improved approximation algorithm for virtual private network design. F. Eisenbrand and F. Grandoni. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 928--932, 2005.
O 22 On the complexity of fixed parameter clique and dominating set. F. Eisenbrand and F. Grandoni. Theoretical Computer Science, 326(1-3):57--67, 2004.
O 22 Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. F. V. Fomin, F. Grandoni, A. V. Pyatkin, and A. A. Stepanov. ACM Transactions on Algorithms, 5(1), 2008.
O 21 Resilient search trees. I. Finocchi, F. Grandoni, and G. F. Italiano. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 547-555, 2007.
O 19 New approaches for virtual private network design. F. Eisenbrand, F. Grandoni, G. Oriolo, and M. Skutella. In International Colloquium on Automata, Languages and Programming (ICALP), pages 1151-1162, 2005.



COAUTHORS
My 46 coauthors are:
O A. Anagnostopoulos [54]
O A. Berger [40,60]
O V. Bonifaci [40,60]
O J. Byrka [53]
O G. S. Brodal [30]
O L. S. Chandran [6,16,24]
O M. Cygan [59]
O E. De Santis [29,52]
O J. Diaz [23,45]
O D. Dubhashi [28]
O F. Eisenbrand [2,5,14,15,27,39,51]
O R. Fagerberg [30]
O U. Ferraro-Petrillo [50]
O I. Finocchi [13,22,25,26,30,43,44]
O F. V. Fomin [9,10,11,12,20,21,35,36,37,38,42,49,61]
O A. Gupta [34]
O G. F. Italiano [1,3,13,17,18,22,25,26,30,43,44,50]
O A. G. Jørgensen [30]
O V. Kaibel [33]
O J. Könemann [7,8,31,32]
O D. Kratsch [11,12,20,21,36,37,38,42]
O P. Krysta [48]
O S. Leonardi [34,48,54,59]
O D. Lokshtanov [49,61]
O A. Marchetti-Spaccamela [23,45]
O P. Miettinen [34]
O T. Mølhave [30]
O G. Moruz [30]
O M. Mucha [59]
O G. Nicosia [53]
O G. Oriolo [14,27,33,55]
O A. Panconesi [7,8,28,29,31,32,52]
O M. Pilipczuk [59]
O V. Pyatkin [9,10,35]
O R. Ravi [41]
O T. Rothvoß [39,47,52,51,56,57,58]
O L. Sanità [52,55,56]
O P. Sankowski [34,54,59]
O S. Saurabh [49,61]
O G. Schäfer [39,40,51,60]
O M. Singh [34,41]
O M. Skutella [14,27,33]
O M. Sozio [7,31]
O A. A. Stepanov [9,10,35]
O C. Ventre [48]
O R. Zenklusen [46]




Updated 28/10/2011