Research Publications/Reports
Listing last 25 publications. (View All) View/Hide Filter- Parameterized Saga of First-Fit and Last-Fit Coloring
Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Shaily Verma, To Appear in 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), Vol , No., Mar 2025.
- Tolerant Testing and Distance Estimation for Distributions Under Memory Constraints
Sampriti Roy, Yadu Vasudev, To Appear in International Conference on Current Trends in. Theory and Practice of Computer Science (SOFSEM 2025), Vol , No., Feb 2025.
- Boundedness for Unions of Conjunctive Regular Path Queries over Simple Regular Expressions
Diego Figueira, CNRS, Bordeaux, S. Krishna, Om Swostik Mishra, Anantha Padmanabha, Appeared in 21st International Conference on Principles of Knowledge Representation and Reasoning, Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, Vol , No., Nov 2024.
- Proper q-caterpillars are distinguished by their Chromatic Symmetric Functions
G Arun Kumar, Narayanan N., Raghavendra Rao B V, Sagar S. Sawant, Appeared in Discrete Mathematics, Vol 347, No.11, pp.114-162, Nov 2024.
- 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.
- Parameterised Counting in Logspace
Anselm Haak, Arne Meier, Om Prakash, Raghavendra Rao B V, Appeared in Algorithmica, Vol 85, No.10, pp.2923--2961, Oct 2023. A preliminary version appeared in The 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), Mar 2021.
- 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.