Research Publications/Reports
Listing last 25 publications. (View All) View/Hide Filter- Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
Girish Balakrishnan, Sankardeep Chakraborty, Narayanaswamy N S, Kunihiko Sadakane, Appeared in 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), Vol 294, No.4, pp.1-16, Jun 2024.
- Energy and Output Patterns in Boolean Circuits
Jayalal Sarma, Kei Uchizawa, Appeared in 18th Annual Conference on Theory and Applications of Models of Computation (TAMC 2024), May 2024.
- Succinct Data Structure for Graphs with d-Dimensional t-Representation
Girish Balakrishnan, Sankardeep Chakraborty, Seungbum Jo, Narayanaswamy N S, Kunihiko Sadakane, Appeared in Data Compression Conference (DCC 2024), pp.546, Mar 2024.
- On Rotation Distance of Rank Bounded Trees
Anoop S K M, Jayalal Sarma, Appeared in Fundamentae Informatica, Mar 2024. A preliminary version under the title "On Rotation Distance, Transpositions and Rank Bounded Trees" appeared in 28th International Computing and Combinatorics Conference (COCOON 2022), Oct 2022.
- A faster algorithm for Vertex Cover parameterized by solution size
David Harris, Narayanaswamy N S, Appeared in 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), Mar 2024.
- Succinct Data Structure for Path Graphs
Girish Balakrishnan, Sankardeep Chakraborty, Narayanaswamy N S, Kunihiko Sadakane, Appeared in Information and Computation, Vol 105124, Jan 2024. A preliminary version appeared in Data Compression Conference (DCC 2022), Mar 2022.
- Approximately interpolating between uniformly and non-uniformly polynomial kernels
Akanksha Agrawal, Ramanujan M S, Appeared in 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec 2023.
- Recognizing Well-Dominated Graphs is NP-complete
Akanksha Agrawal, Henning Fernau, Mann Kevin, Philipp Kindermann, Uéverton S. Souza, Appeared in Information Processing Letters, Oct 2023.
- Testing properties of distributions in the streaming model
Sampriti Roy, Yadu Vasudev, Appeared in 34th International Symposium on Algorithms and Computation (ISAAC 2023), Sep 2023.
- Matchings under One-Sided Preferences with Soft Quotas
Santhini K A, Meghana Nasre, Raghu Raman Ravi, Appeared in International Joint Conference on Artificial Intelligence (IJCAI), Aug 2023.
- On Separating Words Problem over Groups
Neha Kuntewar, Anoop S K M, Jayalal Sarma, Appeared in 25th International Conference on Descriptional Complexity of Formal Systems (DCFS 2023), Jul 2023.
- Optimal Cost based allocation under Two sided preferences
Girija Limaye, Meghana Nasre, Appeared in International Workshop on Combinatorial Algorithms (IWOCA), pp.259--270, Jun 2023.
- Critical Relaxed Stable Matchings with Two-Sided Ties
Keshav Ranjan, Meghana Nasre, Prajakta Nimbhorkar, Appeared in 49th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2023.
- Polynomial Kernel for Interval Vertex Deletion
Akanksha Agrawal, Daniel Lkoshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi, Appeared in ACM Transactions on Algorithms, Vol 19, No.2, pp.11:1-11:68, Apr 2023.
- Erdős-Pósa property of obstructions to interval graphs
Akanksha Agrawal, Daniel Lkoshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi, Appeared in Journal of Graph Theory, Vol 102, No.4, pp.702-727, Apr 2023.
- Clustering What Matters: Optimal Approximation for Clustering with Outliers
Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, Jie Xue, Appeared in The 37th AAAI Conference On Artificial Intelligence, Feb 2023.
- Envy-freeness and relaxed stability: hardness and approximation algorithms
Prem Krishnaa, Girija Limaye, Meghana Nasre, Prajakta Nimbhorkar, Appeared in Journal of Combinatorial Optimization, Vol 45, No.1, pp.41, Jan 2023.
- Trade-Offs in Dynamic Coloring for Bipartite and General Graphs
Manas Jyothi Kashyap, Narayanaswamy N S, Meghana Nasre, Sai Mohith Potluri, Appeared in Algorithmica, Vol 85, No.4, pp.854--878, Jan 2023.
- 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.
- 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.
- 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.