Rajesh Chitnis

Publications

  1. 2020
  2. Published

    Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)

    Rajesh Chitnis, , & , 25 Mar 2020, In: SIAM Journal on Computing. 49, 2, p. 318–364 47 p.

    Research output: Contribution to journalArticlepeer-review

  3. 2019
  4. Published

    FPT inapproximability of directed cut and connectivity problems

    Rajesh Chitnis & , 1 Dec 2019, 14th International Symposium on Parameterized and Exact Computation, (IPEC 2019). Jansen, B. M. P. & Telle, J. A. (eds.). Schloss Dagstuhl, 20 p. 8. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 148).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  5. Published

    Towards a theory of parameterized streaming algorithms

    Rajesh Chitnis & , 1 Dec 2019, 14th International Symposium on Parameterized and Exact Computation, (IPEC 2019). Jansen, B. M. P. & Telle, J. A. (eds.). Schloss Dagstuhl, 15 p. 7. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 148).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  6. Published

    A tight lower bound for planar Steiner Orientation

    Rajesh Chitnis, & , 1 Aug 2019, In: Algorithmica. 81, 8, p. 3200-3216 17 p.

    Research output: Contribution to journalArticlepeer-review

  7. 2018
  8. Published

    Parameterized approximation algorithms for bidirected steiner network problems

    Rajesh Chitnis, & , 1 Aug 2018, 26th European Symposium on Algorithms, (ESA 2018).. Bast, H., Herman, G. & Azar, Y. (eds.). Schloss Dagstuhl, 16 p. 20. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 112).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  9. Published

    A tight lower bound for steiner orientation

    Rajesh Chitnis & , 25 Apr 2018, Computer Science - Theory and Applications : 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Podolskii, V. V. & Fomin, F. V. (eds.). Springer Verlag, p. 65-77 13 p. (Lecture Notes in Computer Science ; vol. 10846 ).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  10. Published

    Can we create large k-cores by adding few edges?

    Rajesh Chitnis & , 25 Apr 2018, Computer Science - Theory and Applications : 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Podolskii, V. V. & Fomin, F. V. (eds.). Springer Verlag, p. 78-89 11 p. (Lecture Notes in Computer Science ; vol. 10846).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  11. Published

    Algorithms and hardness results for nearest neighbor problems in bicolored point sets

    Rajesh Chitnis, 13 Mar 2018, LATIN 2018 -Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. Mosteiro, M. A., Bender, M. A. & Farach-Colton, M. (eds.). Springer Verlag, p. 80-93 (Lecture Notes in Computer Science ; vol. 10807).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  12. 2017
  13. Published

    Faster exact algorithms for some terminal set problems

    Rajesh Chitnis, , , , & , 1 Sep 2017, In: Journal of Computer and System Sciences. 88, September, p. 195-207 13 p.

    Research output: Contribution to journalArticlepeer-review

  14. Published

    List H-coloring a graph by removing few vertices

    Rajesh Chitnis, & , May 2017, In: Algorithmica. 78, 1, p. 110-146 37 p.

    Research output: Contribution to journalArticlepeer-review

  15. Published

    A tight algorithm for Strongly Connected Steiner Subgraph on two terminals with demands

    Rajesh Chitnis, , , , & , 1 Apr 2017, In: Algorithmica. 77, 4, p. 1216-1239 24 p.

    Research output: Contribution to journalArticlepeer-review

  16. 2016
  17. Published

    Tight bounds for Gomory-Hu-like cut counting

    Rajesh Chitnis, & , 28 Sep 2016, Graph-Theoretic Concepts in Computer Science : 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers. Heggernes, P. (ed.). Springer Verlag, p. 133-144 (Lecture Notes in Computer Science ; vol. 9941).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  18. Published

    Designing FPT algorithms for cut problems using randomized contractions

    Rajesh Chitnis, , , & , 6 Jul 2016, In: SIAM Journal on Computing. 45, 4, p. 1171-1229 59 p.

    Research output: Contribution to journalArticlepeer-review

  19. Published

    Parameterized complexity of the anchored k-core problem for directed graphs

    Rajesh Chitnis, & , 1 Apr 2016, In: Information and Computation. 247, p. 11-22

    Research output: Contribution to journalArticlepeer-review

  20. Published

    Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams

    Rajesh Chitnis, , , , , & , 10 Jan 2016, Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms. Krauthgamer, R. (ed.). Society for Industrial and Applied Mathematics (SIAM), p. 1326-1344 19 p. (The Annual ACM - SIAM Symposium on Discrete Algorithms. Proceedings).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  21. 2015
  22. Published

    Brief announcement: New streaming algorithms for parameterized maximal matching & beyond

    Rajesh Chitnis, , , & , 13 Jun 2015, SPAA 2015: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery , p. 56-58 (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  23. Published

    Directed subset feedback vertex set is fixed-parameter tractable

    Rajesh Chitnis, , & , Apr 2015, In: ACM Transactions on Algorithms. 11, 4, 28 p., 28.

    Research output: Contribution to journalArticlepeer-review

  24. Published

    Parameterized Streaming: Maximal Matching and Vertex Cover

    Rajesh Chitnis, , & , 4 Jan 2015, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015). Indyk, P. (ed.). Association for Computing Machinery (ACM), p. 1234-1251 18 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  25. 2014
  26. Published

    A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)

    Rajesh Chitnis, , , , & , 3 Dec 2014, Parameterized and Exact Computation : 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers. Cygan, M. & Heggernes, P. (eds.). Springer Verlag, p. 159-171 (Lecture Notes in Computer Science ; vol. 8894).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  27. Published

    Tight bounds for planar strongly connected steiner subgraph with fixed number of terminals (and extensions)

    Rajesh Chitnis, & , 5 Jan 2014, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Chekuri, C. (ed.). Association for Computing Machinery , p. 1782-1801 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution