Research Publications/Reports
Listing last 25 publications. (View All) View/Hide Filter- Computing Square Colorings on Bounded-Treewidth and Planar Graphs
Akanksha Agrawal, Daniel Marx, Daniel Neuen, Jasper Slusallek, Appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Jan 2023.
- On finding short reconfiguration sequences between independent sets
Akanksha Agrawal, Soumita Hait, Amer E. Mouawad, Appeared in The 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Dec 2022.
- On Rotation Distance, Transpositions and Rank Bounded Trees
Anoop S K M, Jayalal Sarma, Appeared in 28th International Computing and Combinatorics Conference (COCOON 2022), Oct 2022.
- Parameterized Complexity of Perfectly Matched Sets
Akanksha Agrawal, Sutanay Bhattacharjee, Abhishek Sahu, Satyabrata Jana, Appeared in The 17th International Symposium on Parameterized and Exact Computation (IPEC), Sep 2022.
- A Finite Algorithm for the Realizability of a Delaunay Triangulation
Akanksha Agrawal, Saket Saurabh, Meirav Zehavi, Appeared in The 17th International Symposium on Parameterized and Exact Computation (IPEC), Sep 2022.
- Distance From Triviality 2.0: Hybrid Parameterizations
Akanksha Agrawal, M.S. Ramanujan, Appeared in International Workshop on Combinatorial Algorithms (IWOCA), Jun 2022.
- Succinct Data Structure for Path Graphs
Girish Balakrishnan, Sankardeep Chakraborty, Narayanaswamy N S, Kunihiko Sadakane, Appeared in Data Compression Conference (DCC 2022), Mar 2022.
- Fine-grained complexity of rainbow coloring and its variants
Akanksha Agrawal, Appeared in Journal of Computer and System Sciences, Vol 124, Mar 2022.
- Parameterized Complexity of Minimum Membership Dominating Set
Akanksha Agrawal, Pratibha Choudhary, Narayanaswamy N S, Nisha K K, Vijayaraghunathan Ramamoorthi, Appeared in WALCOM, Mar 2022.
- Isomorphism Testing of Read-once Functions and Polynomials
Raghavendra Rao B V, Jayalal Sarma, Appeared in Information and Computation, Feb 2022. A preliminary version appeared in Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), LIPIcs–Leibniz International Proceedings in Informatics, Vol 13, pp.115-126, Dec 2011.
- Optimal Matchings with One-sided Preferences : Fixed and Cost Based Quotas
Santhini K A, Govind S. Sankar, Meghana Nasre, Appeared in Proc. of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022),, To Appear, Jan 2022.
- Deleting, Eliminating and Decomposing to Hereditary Graph Classes Are All FPT Equivalent
Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi, Appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), Jan 2022.
- Popular Matchings in the Hospital-Residents Problem with Two-sided Lower Quotas
Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan, Ankita Sarkar, Appeared in 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec 2021.
- Refuting FPT Algorithms for Some Parameterized Problems Under Gap-ETH
Akanksha Agrawal, Allumalla Ravi Kiran, Dhanekula Varun Teja, Appeared in 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Sep 2021.
- A Polynomial Kernel for Deletion to Ptolemaic Graphs
Akanksha Agrawal, Aditya Anand, Saket Saurabh, Appeared in 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Aug 2021.
- Budgeted Dominating Sets in Uncertain Graphs
Narayanaswamy N S, David Peleg, Vijayaraghunathan Ramamoorthi, Keerti Choudhary, Avi Cohen, Appeared in 46th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2021.
- Matchings with Group Fairness Constraints: Online and Offline Algorithms
Govind S. Sankar, Anand Louis, Meghana Nasre, Prajakta Nimbhorkar, Appeared in 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), Aug 2021.
- On Alternation, VC-dimension and k-fold Union of Sets
Amit Kumar Roy, Jayalal Sarma, Appeared in European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB 2021), Jul 2021.
- Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
Dániel Marx, Govind S. Sankar, Philipp Schepper, Appeared in nternational Colloquium on Automata, Languages and Programming (ICALP 2021), Jun 2021.
- Dynamic Complexity of Expansion
Samir Dutta, Anuj Tawari, Yadu Vasudev, Appeared in The 16th International Computer Science Symposium in Russia (CSR 2021), Jun 2021.
- Limitations of Sums of Bounded Read Formulas and ABPs
Purnata Ghosal, Raghavendra Rao B V, Appeared in The 16th International Computer Science Symposium in Russia (CSR 2021), Jun 2021.
- Paths to Trees and Cacti
Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh, Prafullkumar Tale, Appeared in Theoretical Computer Science, Vol 860, Mar 2021.
- An FPT Algorithm for Elimination Distance to Bounded Degree Graphs
Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Appeared in Symposium on Theoretical Aspects of Computer Science (STACS 2021), Mar 2021.
- Parameterised Counting in Logspace
Anselm Haak, Arne Meier, Om Prakash, Raghavendra Rao B V, Appeared in The 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), Mar 2021.
- On the Computational Power of Programs over BA_2 Monoid
Manasi Kulkarni, Jayalal Sarma, Janani Sundaresan, Appeared in 14th-15th International Conference on Language and Automata Theory and Applications (LATA 2021), Mar 2021.