2021

Bhattacharya, Sayan, Grandoni, Fabrizio and Wajc, David (2021) Online edge coloring algorithms via the nibble method. In: ACM-SIAM Symposium on Discrete Algorithms (SODA21), Virtual, 10-13 Jan 2021. Published in: SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms pp. 2830-2841. ISBN 9781611976465. doi:10.1137/1.9781611976465.168

Bhattacharya, Sayan and Kiss, Peter (2021) Deterministic rounding of dynamic fractional matchings. In: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Virtual, 12-16 Jul 2021. Published in: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) ISSN 1868-8969. (In Press)

Bhattacharya, Sayan, Henzinger, Monika, Nanongkai, Danupon and Wu, Xiaowei (2021) Dynamic set cover : improved amortized and worst-case update time. In: ACM-SIAM Symposium on Discrete Algorithms (SODA21), Virtual, 10-13 Jan 2021. Published in: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 2537-2549. ISBN 9781611976465. doi:10.1137/1.9781611976465.150

2020

Bhattacharya, Sayan, Henzinger, Monika and Nanongkai, Danupon (2020) 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. Published in: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) ISBN 9781728149530. ISSN 2575-8454. doi:10.1109/FOCS.2019.00033

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) pp. 476-494. ISBN 9781611975994. doi:10.1137/1.9781611975994.29

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) 2509-2521 . ISBN 9781611975994. doi:10.1137/1.9781611975994.153

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

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: 25th Annual European Symposium on Algorithms (ESA 2017), 87 1:1-1:5. ISBN 9783959770491. ISSN 1868-8969. doi:10.4230/LIPIcs.ESA.2017.1

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.