Recent publications
Article
Chitnis, R, Feldmann, AE, Hajiaghayi, M & Marx, D 2020, 'Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)', SIAM Journal on Computing, vol. 49, no. 2, pp. 318–364. https://doi.org/10.1137/18M122371X
Chitnis, R, Feldmann, AE & Suchý, O 2019, 'A tight lower bound for planar Steiner Orientation', Algorithmica, vol. 81, no. 8, pp. 3200-3216. https://doi.org/10.1007/s00453-019-00580-x
Chitnis, R, Esfandiari, H, Hajiaghayi, MT, Khandekar, R, Kortsarz, G & Seddighin, S 2017, 'A tight algorithm for Strongly Connected Steiner Subgraph on two terminals with demands', Algorithmica, vol. 77, no. 4, pp. 1216-1239. https://doi.org/10.1007/s00453-016-0145-8
Chitnis, R, Fomin, FV, Lokshtanov, D, Misra, P, Ramanujan, MS & Saurabh, S 2017, 'Faster exact algorithms for some terminal set problems', Journal of Computer and System Sciences, vol. 88, no. September, pp. 195-207. https://doi.org/10.1016/j.jcss.2017.04.003
Chitnis, R, Egri, L & Marx, D 2017, 'List H-coloring a graph by removing few vertices', Algorithmica, vol. 78, no. 1, pp. 110-146. https://doi.org/10.1007/s00453-016-0139-6
Chitnis, R, Cygan, M, Hajiaghayi, M, Pilipczuk, M & Pilipczuk, M 2016, 'Designing FPT algorithms for cut problems using randomized contractions', SIAM Journal on Computing, vol. 45, no. 4, pp. 1171-1229. https://doi.org/10.1137/15M1032077
Chitnis, R, Fomin, FV & Golovach, PA 2016, 'Parameterized complexity of the anchored k-core problem for directed graphs', Information and Computation, vol. 247, pp. 11-22. https://doi.org/10.1016/j.ic.2015.11.002
Conference contribution
Chitnis, R & Feldmann, AE 2019, FPT inapproximability of directed cut and connectivity problems. in BMP Jansen & JA Telle (eds), 14th International Symposium on Parameterized and Exact Computation, (IPEC 2019)., 8, Leibniz International Proceedings in Informatics, LIPIcs, vol. 148, Schloss Dagstuhl, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, Munich, Germany, 11/09/19. https://doi.org/10.4230/LIPIcs.IPEC.2019.8
Chitnis, R & Cormode, G 2019, Towards a theory of parameterized streaming algorithms. in BMP Jansen & JA Telle (eds), 14th International Symposium on Parameterized and Exact Computation, (IPEC 2019)., 7, Leibniz International Proceedings in Informatics, LIPIcs, vol. 148, Schloss Dagstuhl, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, Munich, Germany, 11/09/19. https://doi.org/10.4230/LIPIcs.IPEC.2019.7
Chitnis, R & Feldmann, AE 2018, A tight lower bound for steiner orientation. in VV Podolskii & FV Fomin (eds), Computer Science - Theory and Applications : 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Lecture Notes in Computer Science , vol. 10846 , Springer Verlag, pp. 65-77, 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russian Federation, 6/06/18. https://doi.org/10.1007/978-3-319-90530-3_7
Banerjee, S, Bhore, S & Chitnis, R 2018, Algorithms and hardness results for nearest neighbor problems in bicolored point sets. in MA Mosteiro, MA Bender & M Farach-Colton (eds), LATIN 2018 -Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. Lecture Notes in Computer Science , vol. 10807, Springer Verlag, pp. 80-93, 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018, Buenos Aires, Argentina, 16/04/18. https://doi.org/10.1007/978-3-319-77404-6_7
Chitnis, R & Talmon, N 2018, Can we create large k-cores by adding few edges? in VV Podolskii & FV Fomin (eds), Computer Science - Theory and Applications : 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Lecture Notes in Computer Science , vol. 10846, Springer Verlag, pp. 78-89, 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russian Federation, 6/06/18. https://doi.org/10.1007/978-3-319-90530-3_8
Chitnis, R, Feldmann, AE & Manurangsi, P 2018, Parameterized approximation algorithms for bidirected steiner network problems. in H Bast, G Herman & Y Azar (eds), 26th European Symposium on Algorithms, (ESA 2018).., 20, Leibniz International Proceedings in Informatics, LIPIcs, vol. 112, Schloss Dagstuhl, 26th European Symposium on Algorithms, ESA 2018, Helsinki, Finland, 20/08/18. https://doi.org/10.4230/LIPIcs.ESA.2018.20
Chitnis, R, Cormode, G, Esfandiari, H, Hajiaghayi, M, McGregor, A, Monemizadeh, M & Vorotnikova, S 2016, Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. in R Krauthgamer (ed.), Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms. The Annual ACM - SIAM Symposium on Discrete Algorithms. Proceedings, Society for Industrial and Applied Mathematics (SIAM), pp. 1326-1344, Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, United States, 10/01/16. https://doi.org/10.1137/1.9781611974331.ch92
Chitnis, R, Kamma, L & Krauthgamer, R 2016, Tight bounds for Gomory-Hu-like cut counting. in P Heggernes (ed.), Graph-Theoretic Concepts in Computer Science : 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers. Lecture Notes in Computer Science , vol. 9941, Springer Verlag, pp. 133-144, 42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016, Istanbul, Turkey, 22/06/16. https://doi.org/10.1007/978-3-662-53536-3_12
View all publications in research portal