Publications

•           Min-Cost Popular Matchings in a Hospitals/Residents Instance with Complete Preferences
            T. Kavitha and K. Makino
            In MATCH-UP 2024 (oral presentation).


•           Popular Solutions for Optimal Matchings
            T. Kavitha
            In WG 2024.


•           Arborescences, Colorful Forests, and Popularity
            T. Kavitha, K. Makino, I. Schlotter, and Y. Yokoi
            In SODA 2024
            Journal version Popular Arborescences and Their Matroid Generalization in ACM Transactions on Algorithms.




• Envy-free relaxations for goods, chores, and mixed items
  K. Bérczi, E. Bérczi-Kovács, E. Boros, F. T. Gedefa, N. Kamiyama, T. Kavitha, Y. Kobayashi, and K. Makino
  In Theoretical Computer Science, 2024.


• Perfect Matchings and Popularity in the Many-to-Many Setting
  T. Kavitha and K. Makino
  In FSTTCS 2023.


• Semi-Popular Matchings and Copeland Winners
  T. Kavitha and R. Vaish
  In AAMAS 2023.


• Stable Matchings with One-Sided Ties and Approximate Popularity
  T. Kavitha
  In FSTTCS 2022 (journal version in Algorithmica).


• Fairly Popular Matchings and Optimality
  T. Kavitha
  In STACS 2022 (journal version in SIAM Journal on Discrete Mathematics).


• The popular assignment problem: when cardinality is more important than popularity
  T. Kavitha, T. Király, J. Matuschke, I. Schlotter, and U. Schmidt-Kraepelin
  In SODA 2022.


• Understanding Popular Matchings via Stable Matchings
  Á. Cseh, Y. Faenza, T. Kavitha, and V. Powers
  In SIAM Journal on Discrete Mathematics, 2022.


• Matchings, Critical Nodes, and Popular Solutions
  T. Kavitha
  In FSTTCS 2021.


• Maximum Matchings and Popularity
  T. Kavitha
  In ICALP 2021 (journal version in SIAM Journal on Discrete Mathematics).


• Min-Cost Popular Matchings
  T. Kavitha
  In FSTTCS 2020.


• Popular Matchings with One-Sided Bias
  T. Kavitha
  In ICALP 2020 (journal version in ACM Transactions on Algorithms).


• Popular Branchings and Their Dual Certificates
  T. Kavitha, T. Király, J. Matuschke, I. Schlotter, and U. Schmidt-Kraepelin
  In IPCO 2020 (journal version in Mathematical Programming).


• A Little Charity Guarantees Almost Envy-Freeness
  B. R. Chaudhury, T. Kavitha, K. Mehlhorn, and A. Sgouritsa
  In SODA 2020 (journal version in SIAM Journal on Computing).


• Quasi-popular Matchings, Optimality, and Extended Formulations
  Y. Faenza and T. Kavitha
  In SODA 2020 (journal version in Mathematics of Operations Research).


• Popular Roommates in Simply Exponential Time
  T. Kavitha
  In FSTTCS 2019 (journal version in Algorithmica).


• Popular Matchings and Limits to Tractability
  Y. Faenza, T. Kavitha, V. Powers, and X. Zhang
  In SODA 2019.


• Popular Matchings in Complete Graphs
  Á. Cseh and T. Kavitha
  In FSTTCS 2018 (journal version in Algorithmica).


• Popular Matchings of Desired Size
  T. Kavitha
  In WG 2018.


• Popular Matchings with Multiple Partners
  F. Brandl and T. Kavitha
  In FSTTCS 2017 (journal version in Algorithmica).


• New Algorithms for Maximum Weight Matching and a Decomposition Theorem
  C.-C. Huang and T. Kavitha
  In Mathematics of Operations Research, 2017.


• Popularity, Mixed Matchings, and Self-duality
  C.-C. Huang and T. Kavitha
  In SODA 2017 (journal version in Mathematics of Operations Research).


• Distributed Construction of Purely Additive Spanners
  K. Censor-Hillel, A. Paz, T. Kavitha, and A. Yehudayoff
  In DISC 2016 (journal version in Distributed Computing).


• Popular Half-Integral Matchings
  T. Kavitha
  In ICALP 2016.


• Popular Edges and Dominant Matchings
  Á. Cseh and T. Kavitha
  In IPCO 2016 (journal version in Mathematical Programming, Ser. B).


• Popular Matchings with Two-Sided Preferences and One-Sided Ties
  Á. Cseh, C.-C. Huang, and T. Kavitha
  In ICALP 2015 (journal version in SIAM Journal on Discrete Mathematics).


• Maintaining Near-Popular Matchings
  S. Bhattacharya, M. Hoefer, C.-C. Huang, T. Kavitha, and L. Wagner
  In ICALP 2015.


• New Pairwise Spanners
  T. Kavitha
  Invited to a special issue of Theory of Computing Systems on STACS 2015.


• An Improved Algorithm for the Stable-Marriage Problem with One-Sided Ties
  C.-C. Huang and T. Kavitha
  In IPCO 2014 (journal version in Mathematical Programming).


• Fair Matchings and Related Problems
  C.-C. Huang, T. Kavitha, K. Mehlhorn, and D. Michail
  In FSTTCS 2013 (journal version in Algorithmica).


• Small Stretch Pairwise Spanners
  T. Kavitha and N. M. Varma
  In ICALP 2013 (journal version in SIAM Journal on Discrete Mathematics).


• On Pairwise Spanners
  M. Cygan, F. Grandoni, and T. Kavitha
  In STACS 2013.


• Popularity vs Maximum Cardinality in the Stable Marriage Setting
  T. Kavitha
  In SODA 2012 (journal version in SIAM Journal on Computing).


• Efficient Algorithms for Maximum Weight Matchings in General Graphs with Small Edge Weights
  C.-C. Huang and T. Kavitha
  In SODA 2012.


• Near-Popular Matchings in the Roommates Problem
  C.-C. Huang and T. Kavitha
  In ESA 2011 (journal version in SIAM Journal on Discrete Mathematics).


• Popular Matchings in the Stable Marriage Problem
  C.-C. Huang and T. Kavitha
  Invited to a special issue of Information and Computation on ICALP 2011.


• Assigning Papers to Referees
  N. Garg, T. Kavitha, A. Kumar, J. Mestre, and K. Mehlhorn.
  In Algorithmica, 2010.


• Popularity at Minimum Cost
  T. Kavitha, M. Nasre, and P. Nimbhorkar
  In ISAAC 2010 (journal version in Journal of Combinatorial Optimization).


• Popular Mixed Matchings
  T. Kavitha, J. Mestre, and M. Nasre
  Invited to a special issue of Theoretical Computer Science on ICALP 2009.


• Popular Matchings with Variable Job Capacities
  T. Kavitha and M. Nasre
  In ISAAC 2009 (journal version in Theoretical Computer Science)


• Max-Coloring Paths: Tight Bounds and Extensions
  T. Kavitha and J. Mestre
  Invited to a special issue of Journal of Combinatorial Optimization on ISAAC 2009.


• Optimal Popular Matchings
  T. Kavitha and M. Nasre
  In Discrete Applied Mathematics, 2009.


• Dynamic Matrix Rank with Partial Look-ahead
  T. Kavitha
  In FSTTCS 2008 (journal version in Theory of Computing Systems).


• An Improved Heuristic for Computing Short Integral Cycle Bases
  T. Kavitha and K. Vamsi Krishna
  In ACM Journal of Experimental Algorithmics.


• Faster Algorithms for Incremental Topological Ordering
  B. Haeupler, T. Kavitha, R. Mathew, S. Sen, and R. Tarjan
  In ICALP 2008 (journal version in ACM Transactions on Algorithms).


• On a Special Co-Cycle Basis of Graphs
  T. Kavitha.
  In SWAT 2008 (journal version in Theoretical Computer Science).


• Bounded Unpopularity Matchings
  C.-C. Huang, T. Kavitha, D. Michail, and M. Nasre
  In SWAT 2008 (journal version in Algorithmica).


• Fast Edge Splitting and Edmonds' Arborescence Construction for Unweighted Graphs
  A. Bhalgat, R. Hariharan, T. Kavitha, and D. Panigrahi.
  In SODA 2008.


• Linear Time Algorithms for Abelian Group Isomorphism and Related Results
  T. Kavitha
  In Journal of Computer and System Sciences, 2007.


• Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs
  T. Kavitha
  In FSTTCS 2007 (journal version in Algorithmica).


• An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
  A. Bhalgat, R. Hariharan, T. Kavitha, and D. Panigrahi
  In STOC 2007.


• New Approximation Algorithms for Minimum Cycle Bases of Graphs
  T. Kavitha, K. Mehlhorn, and D. Michail
  In STACS 2007 (journal version in Algorithmica).


• Efficient Algorithms for computing all low s-t connectivities and Related Problems
  R. Hariharan, T. Kavitha, and D. Panigrahi
  In SODA 2007.


• Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems
  T. Kavitha and C. D. Shah
  In ISAAC 2006.


• Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths
  S. Baswana and T. Kavitha
  In FOCS 2006 (journal version in SIAM Journal on Computing).


• A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs
  R. Hariharan, T. Kavitha, and K. Mehlhorn
  In ICALP 2006 (journal version in SIAM Journal on Computing).


• Dynamic Matching Markets and Voting Paths
  D. J. Abraham and T. Kavitha
  In SWAT 2006 (journal version in SIAM Journal on Discrete Mathematics).


• An Õ(m^2n) Randomized Algorithm to Compute a Minimum Cycle Basis of a Directed Graph
  T. Kavitha
  In ICALP 2005.


• A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs
  T. Kavitha and K. Mehlhorn
  Invited to a special issue of Theory of Computing Systems on STACS 2005.


• New Constructions of (α,β)-Spanners and Purely Additive Spanners
  S. Baswana, T. Kavitha, K. Mehlhorn, and S. Pettie
  In SODA 2005 (journal version in ACM Transactions on Algorithms).


• Popular Matchings
  D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn.
  In SODA 2005 (journal version in SIAM Journal on Computing).


• Rank-Maximal Matchings
  R. W. Irving, T. Kavitha, K. Mehlhorn, D. Michail, and K. Paluch
  Invited to a special issue of ACM Transactions on Algorithms on SODA 2004.


• Strongly Stable Matchings in Time O(mn) and Extension to the Hospitals-Residents Problem
  T. Kavitha, K. Mehlhorn, D. Michail, and K. Paluch
  In STACS 2004 (journal version in ACM Transactions on Algorithms).


• A faster algorithm for Minimum Cycle Basis of Graphs
  T. Kavitha, K. Mehlhorn, D. Michail, and K. Paluch
  In ICALP 2004 (journal version in Algorithmica).


• Efficient Algorithms for Abelian Group Isomorphism and Related Problems
  T. Kavitha
  In FSTTCS 2003.


• On Shortest Paths in Line Arrangements
  T. Kavitha and K. R. Varadarajan
  In CCCG 2003.


• Isoperimetric Inequalities and Width Parameters of Graphs
  L. S. Chandran, T. Kavitha, and C. R. Subramanian
  In COCOON 2003.


• An Algorithm for Computing a Convex and Simple Path of Bounded Curvature in a Simple Polygon
  J.-D. Boissonnat, S.K. Ghosh, T. Kavitha, and S. Lazard
  In Algorithmica, 2002.


• Better Lower Bounds for Locally Decodable Codes
  A. Deshpande, R. Jain, T. Kavitha, S.V. Lokam, and J. Radhakrishnan
  In Computational Complexity Conference 2002 (journal version in Random Structures and Algorithms).