A list of some of my papers and manuscripts.
Algorithmic Lower Bounds for Problems Parameterized by Clique-width (with F. Fomin, P. Golovach and D. Lokshtanov). To appear in the proceedings of SODA '10. |
Bidimensionality and Kernels (with F. Fomin, D. Lokshtanov and D. M. Thilikos). To appear in the proceedings of SODA '10. |
Subexponential Algorithms for Partial Cover Problems (with F. Fomin, D. Lokshtanov and V. Raman). To appear in the proceedings of FSTTCS '09. |
Kernels for Feedback Arc Set In Tournaments (with S. Bessy, F. V. Fomin, S. Gaspers, C. Paul, A. Perez and S. Thomasse). To appear in the proceedings of FSTTCS '09. |
Bandwidth on AT-free graphs (with P. Golovach, P. Heggernes, D. Kratsch, D. Lokshtanov and D. Meister). To appear in the proceedings of ISAAC '09. |
A Linear Vertex Kernel for Maximum Internal Spanning Tree (with F. V. Fomin, S. Gaspers and S. Thomasse). To appear in the proceedings of ISAAC '09. |
(Meta) Kernelization (with H.L.Bodlaender, F.V.Fomin, D.Lokshtanov, E.Penninkx and D.M.Thilikos). To appear in the proceedings of FOCS '09. |
Even Faster Algorithm for Set Splitting! (with D. Lokshtanov). To appear in the proceedings of IWPEC '09. |
On the Directed Degree-Preserving Spanning Tree Problem (with D. Lokshtanov, V. Raman and S. Sikdar). To appear in the proceedings of IWPEC '09. |
Simpler Parameterized Algorithm for OCT (with D. Lokshtanov and S. Sikdar). To appear in the proceedings of IWOCA '09. |
An Exact Algorithm for Minimum Distortion Embedding (with F. V. Fomin and D. Lokshtanov). To appear in the proceedings of WG '09. |
The Budgeted Unique Coverage Problem and Color Coding (with N. Misra, V. Raman and S. Sikdar). In the proceedings of CSR '09 (Springer Verlag, LNCS 5675), 310-321. |
Fast FAST (with N. Alon and D. Lokshtanov). In the proceedings of ICALP '09 (Springer Verlag, ARCoSS, LNCS 5555), 49-58. |
Counting Subgraphs via Homomorphisms (with O. Amini and F. V. Fomin). In the proceedings of ICALP '09(Springer Verlag, ARCoSS, LNCS 5555), 71-82. |
Incompressibility through Colors and IDs (with M. Dom and D. Lokshtanov). In the proceedings of ICALP '09(Springer Verlag, ARCoSS, LNCS 5555), 378-389. |
Distortion is Fixed Parameter Tractable (with M. Fellows, F. V. Fomin D. Lokshtanov, E.Losievskaja and F. A. Rosamond). In the proceedings of ICALP '09(Springer Verlag, ARCoSS, LNCS 5555), 463-474. |
Local Search: Is brute-force avoidable? (with M. Fellows, F. V. Fomin, D. Lokshtanov, F. A. Rosamond and Y. Villanger). In the proceedings of IJCAI '09, 486-491. |
Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem (with N. Cohen, F. V. Fomin, G. Gutin, E. J. Kim and A. Yeo). In the proceedings of COCOON '09(Springer Verlag, LNCS 5609), 37-46. |
Linear Kernel for Planar Connected Dominating Set (with D. Lokshtanov and M. Mnich). In the proceedings of TAMC '09(Springer Verlag, LNCS 5532), 281-290. |
Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves (with H. Fernau, F. V. Fomin, D. Lokshtanov, D. Raible and Y. Villanger). In the proceedings of STACS '09, 421-432. |
Clique-width: On the Price of Generality (with F. V. Fomin, D. Lokshtanov and P. A. Golovach). In the proceedings of SODA '09, 825-834. |
Spanning Directed Tree with many Leaves (with N. Alon, F. V. Fomin, G. Gutin and M. Krivelevich). Siam Journal on Discrete Mathematics. Volume 23, Issue 1, Pages 466-476. Preliminary version of the paper appeared in the proceedings of FSTTCS 2007. |
The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number (with M. Fellows, D. Lokshtanov, N. Misra, M. Mnich and F. A. Rosamond). Accepted to appear in `Theory of Computing Systems', Springer Verlag. |
Konig Deletion Sets and Vertex Covers Above the Matching Size (with S. Mishra, V. Raman, and S. Sikdar). In the proceedings of ISAAC '08(Springer Verlag, LNCS 5369), 836-847. |
Graph Layout problems Parameterized by Vertex Cover (with M. Fellows, D. Lokshtanov, N. Misra and F. A. Rosamond). In the proceedings of ISAAC '08(Springer Verlag, LNCS 5369), 294-305. |
Implicit Branching and Parameterized Partial Cover Problems (with O. Amini and F. Fomin). In the proceedings of FSTTCS '08. |
Degree-Constrained Subgraph Problems : Hardness and Approximation Results (with O. Amini, D. Peleg, S. PĂ©rennes, and I. Sau). In the proceedings of WAOA '08(Springer Verlag, LNCS 5426), 29-42. |
Parametrized Complexity of the Smallest Degree Constrained Subgraph Problem (with O. Amini and I. Sau). In the proceedings of IWPEC'08 (Springer Verlag, LNCS 5018), 13-29. |
Capacitated Domination and Covering: A Parameterized Perspective (with M. Dom, D. Lokshtanov and Y. Villanger). In the proceedings of IWPEC'08: (Springer Verlag, LNCS 5018) 78-90. |
A Moderately Exponential Time Algorithm for Full Degree Spanning Tree (with S. Gaspers, and A. A. Stepanov). In the proceedings of TAMC'08: (Springer Verlag, LNCS 4978) 479-489. |
Parameterized Algorithms for Generalized Domination (with V. Raman, and S. Srihari). In the proceedings of COCOA 2008: (Springer Verlag, LNCS 5165) 116-126. |
Iterative Compression and Exact Algorithms (with F. V. Fomin, S. Gaspers, D. Kratsch, and M. Liedloff). In the proceedings of MFCS 2008: (Springer Verlag, LNCS 5162) 335-346. |
Improving the gap of Erdos-Posa property for minor-closed graph classes (with F. V. Fomin and D. M. Thilikos). In the proceedings of 7th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2008. |
On Two Techniques of Combining Branching and Treewidth (with F. V. Fomin, S. Gaspers, and A. A. Stepanov). Algorithmica. Volume 54, Issue 2, Pages 181-207 (2009). A preliminary version of the paper appeared in the proceedings of ISAAC 2006. |
Short Cycles make W-hard problems hard: FPT algorithms for W-hard problems in Graphs with no short cycles (with V. Raman) Algorithmica. Volume 52, Issue 2, Pages 203-225 (2008). A preliminary version of the paper appeared in the proceedings of SWAT 2006. |
The Complexity of Finding Subgraphs whose Matching Number Equals the Vertex Cover Number (with S. Mishra, V. Raman, S. Sikdar, C. R. Subramanian). In the proceedings of ISSAC '07: (Springer Verlag, LNCS 4835) 268-279. |
On the Complexity of Some Colorful Problems Parameterized by Treewidth (with M. Fellows, F. V. Fomin, D. Lokshtanov, F. Rosamond, S. Szeider and C. Thomassen). In the proceedings of COCOA'07: (Springer Verlag, LNCS 4616) 366-377. (Invited Paper.) |
Parameterized Algorithms for Directed Maximum Leaf Problems (with N. Alon, F. V. Fomin, G. Gutin and M. Krivelevich). In the proceedings of ICALP'07: (Springer Verlag, LNCS 4596) 352-362. |
Improved Exact Algorithms for Counting 3- and 4- Colorings (with F. V. Fomin and S. Gaspers) In the proceedings of COCOON'07: (Springer Verlag, LNCS 4598) 65-74. |
Improved Fixed Parameter Tractable Algorithms for Two Edge Problems -- MAXCUT and MAXDAG (with V. Raman). Information Processing Letters (IPL). Volume 104(2), Pages 65-72 (2007) |
Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques (with V. Raman and S. Sikdar). Theory of Computing Systems. Volume 41, Issue 3, Pages 563-587 (2007). A preliminary version of the paper appeared in the proceedings of ICTCS 2005. |
Exact and Parameterized Algorithms through (old and new) Structural Graph theoretical Results (with V. Raman). In the proceedings of the International Conference on Discrete Mathematics (2006), 177-189. |
Fast Exponential Algorithms for Maximum $r$-Regular Induced Subgraph Problems (with S. Gupta and V. Raman). In the proceedings of FSTTSC '06: (Springer Verlag, LNCS 4337) 139-151. |
Faster Fixed Parameter Tractable Algorithms for Finding Feedback Vertex Sets (with V. Raman and C. R. Subramanian). ACM Transactions on Algorithms (TALG). Volume 2, Issue 3, Pages 403-415 (2006). Preliminary versions of the paper appeared in the proceedings of ISAAC 2002 and GRACO 2005. |
Parameterized Algorithms for Feedback Set Problems and Their Duals in Tournaments (with V. Raman). Theoretical Computer Science (TCS). Volume 351, Issue 3, Pages 446-458 (2006). Preliminary versions of the paper appeared in the proceedings of WADS 2003 and IWPEC 2004. |