2020

Bhattacharya, Sayan, Nanongkai, Danupon and Saranurak, Thatchaphol (2020) Coarse-grained complexity for dynamic algorithms. In: 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Salt Lake City, Utah, U.S., 5-8 Jan 2020. Published in: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) (In Press)

Bhattacharya, Sayan and Kulkarni, Janardhan (2020) An improved algorithm for incremental cycle detection and topological ordering in sparse graphs. In: 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Salt Lake City, Utah, U.S., 5-8 Jan 2020. Published in: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) (In Press)

2019

Bhattacharya, Sayan and Kulkarni, Janardhan (2019) Deterministically maintaining a (2 + ∊)-approximate minimum vertex cover in O(1/∊2) amortized update time. In: Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, USA, 6-9 Jan 2019. Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1872-1885. ISBN 9781611975482. doi:10.1137/1.9781611975482.113

Bhattacharya, Sayan, Henzinger, Monika and Nanongkai, Danupon (2019) A new deterministic algorithm for dynamic set cover. In: FOCS 2019 60th Annual IEEE Symposium on Foundations of Computer Science, Baltimore, Maryland, 9-12 Nov 2019 (In Press)

2018

Bhattacharya, Sayan, Henzinger, Monika and Italiano, Giuseppe F. (2018) Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing, 47 (3). pp. 859-887. doi:10.1137/140998925

Bhattacharya, Sayan, Chakrabarty, Deeparnab, Henzinger, Monika and Nanongkai, Danupon (2018) Dynamic algorithms for graph coloring. In: Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, USA, 7-10 Jan 2018. Published in: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1-20. ISBN 9781611975031. doi:10.1137/1.9781611975031.1

2017

Bhattacharya, Sayan, Gupta, Manoj and Mohan, Divyarthi (2017) Improved algorithm for dynamic b-Matching. In: 25th Annual European Symposium on Algorithms (ESA 2017), Vienna, Austria, 4-6 Sep 2017. Published in: Leibniz International Proceedings in Informatics (LIPIcs) ISSN 1868-8969. (In Press)

Bhattacharya, Sayan, Chakraborty, Deeparnab and Henzinger, Monika (2017) Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) update time. In: IPCO 2017 (19th Conference on Integer Programming and Combinatorial Optimization), University of Waterloo, Canada, 26-28 Jun 2017. Published in: Lecture Notes in Computer Science, 10328 pp. 86-98. ISBN 9783319592497. ISSN 0302-9743. doi:10.1007/978-3-319-59250-3_8

Bhattacharya, Sayan, Henzinger, Monika and Nanongkai, Danupon (2017) Fully dynamic approximate maximum matching and minimum vertex cover in O(log3 n) worst case update time. In: Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 Jan 2017. Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 470-489. ISBN 9781611974782. doi:10.1137/1.9781611974782.30

2016

Bhattacharya, Sayan, Henzinger, Monika and Nanongkai, Danupon (2016) New deterministic approximation algorithms for fully dynamic matching. In: 48th Annual ACM Symposium on Theory of Computing, Cambridge, MA, USA, 19-21 Jun 2016 . Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing pp. 398-411. ISBN 9781450341325. doi:10.1145/2897518.2897568

2015

Bhattacharya, Sayan, Henzinger, Monika, Nanongkai, Danupon and Tsourakakis, Charalampos (2015) Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: Forty-seventh annual ACM symposium on Theory of computing, Portland, Oregon, USA, 14-17 Jun 2015 . Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of computing pp. 173-182. ISBN 9781450335362. doi:10.1145/2746539.2746592

Bhattacharya, Sayan, Henzinger, Monika and Italiano, Giuseppe F. (2015) Design of dynamic algorithms via primal-dual method. In: International Colloquium on Automata, Languages, and Programming, Kyoto, Japan, 6-10 Jul 2015. Published in: Automata, Languages, and Programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, 9134 pp. 206-218. ISBN 9783662476710. ISSN 0302-9743. doi:10.1007/978-3-662-47672-7_17

Bhattacharya, Sayan, Henzinger, Monika and Italiano, Giuseppe F. (2015) Deterministic fully dynamic data structures for vertex cover and matching. In: Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, 4-6 Jan 2015. Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 785-804. ISBN 9781611973747. doi:10.1137/1.9781611973730.54

Bhattacharya, Sayan, Hoefer, Martin, Huang, Chien-Chung, Kavitha, Telikepalli and Wagner, Lisa (2015) Maintaining near-popular matchings. In: International Colloquium on Automata, Languages, and Programming, Kyoto, Japan, 6-10 Jul 2015. Published in: Automata, Languages, and Programming, 9135 pp. 504-515. ISBN 9783662476659. ISSN 0302-9743. doi:10.1007/978-3-662-47666-6_40

Bhattacharya, Sayan, Dvorák, Wolfgang, Henzinger, Monika and Starnberger, Martin (2015) Welfare maximization with friends-of-friends network externalities. In: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), München, Germany , 4-7 Mar 2015. Published in: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), 30 pp. 90-102. ISBN 9783939897781.