Somnath Sikdar

Publication Activity (10 Years)

Years Active: 2003-2019
Publications (10 Years): 6

Top Topics

Polynomial Kernels

Parameterized Complexity

Pspace Complete

Top Venues

J. Comput. Syst. Sci.

Publications

Erik D. Demaine, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar, Blair D. Sullivan
Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs. J. Comput. Syst. Sci. 105 (2019)
Maw-Shang Chang, Li-Hsuan Chen, Ling-Ju Hung, Yi-Zhi Liu, Peter Rossmanith, Somnath Sikdar
Moderately exponential time algorithms for the maximum bounded-degree-1 set problem. Discret. Appl. Math. 251 (2018)
Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar
Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci. 84 (2017)
Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, Somnath Sikdar
Kernelization and Sparseness: the Case of Dominating Set. STACS (2016)
Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, Somnath Sikdar
Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions. ACM Trans. Algorithms 12 (2) (2016)
Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar
Are there any good digraph width measures? J. Comb. Theory, Ser. B 116 (2016)
Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil, Somnath Sikdar
Fast Biclustering by Dual Parameterization. IPEC (2015)
Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil, Somnath Sikdar
Fast Biclustering by Dual Parameterization. CoRR (2015)
Robert Ganian, Petr Hlinený, Alexander Langer, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar
model-checking. J. Comput. Syst. Sci. 80 (1) (2014)
Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Saket Saurabh, Fernando Sánchez Villaamil, Somnath Sikdar
Kernelization and Sparseness: the case of Dominating Set. CoRR (2014)
Jan Dreier, Philipp Kuinke, Rafael Przybylski, Felix Reidl, Peter Rossmanith, Somnath Sikdar
Overlapping Communities in Social Networks. CoRR (2014)
Erik D. Demaine, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar, Blair D. Sullivan
Structural Sparsity of Complex Networks: Random Graph Models and Linear Algorithms. CoRR (2014)
Jakub Gajarský, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar
Finite Integer Index of Pathwidth and Treewidth. IPEC (2014)
Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar
A Faster Parameterized Algorithm for Treedepth. CoRR (2014)
Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar
A Faster Parameterized Algorithm for Treedepth. ICALP (1) (2014)
Alexander Langer, Felix Reidl, Peter Rossmanith, Somnath Sikdar
Practical algorithms for MSO model-checking on tree-decomposable graphs. Comput. Sci. Rev. (2014)
Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar
Kernelization Using Structural Parameters on Sparse Graph Classes CoRR (2013)
Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, Somnath Sikdar
Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions. ICALP (1) (2013)
Neeldhara Misra, Hannes Moser, Venkatesh Raman, Saket Saurabh, Somnath Sikdar
The Parameterized Complexity of Unique Coverage and Its Variants. Algorithmica 65 (3) (2013)
Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar
Kernelization Using Structural Parameters on Sparse Graph Classes. ESA (2013)
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh, Somnath Sikdar
FPT algorithms for Connected Feedback Vertex Set. J. Comb. Optim. 24 (2) (2012)
Alexander Langer, Felix Reidl, Peter Rossmanith, Somnath Sikdar
Linear Kernels on Graphs Excluding Topological Minors CoRR (2012)
Alexander Langer, Felix Reidl, Peter Rossmanith, Somnath Sikdar
Evaluation of an MSO-Solver. ALENEX (2012)
Robert Ganian, Petr Hlinený, Alexander Langer, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar
Lower Bounds on the Complexity of MSO_1 Model-Checking. STACS (2012)
Michael Dom, Michael R. Fellows, Frances A. Rosamond, Somnath Sikdar
The Parameterized Complexity of Stabbing Rectangles. Algorithmica 62 (1-2) (2012)
Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, Somnath Sikdar
Linear kernels and single-exponential algorithms via protrusion decompositions CoRR (2012)
Geevarghese Philip, Venkatesh Raman, Somnath Sikdar
Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms 9 (1) (2012)
Alexander Langer, Peter Rossmanith, Somnath Sikdar
Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory CoRR (2011)
Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, Somnath Sikdar
On the directed Full Degree Spanning Tree problem. Discret. Optim. 8 (1) (2011)
Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar, C. R. Subramanian
The Complexity of König Subgraph Problems and Above-Guarantee Vertex Cover. Algorithmica 61 (4) (2011)
Robert Ganian, Petr Hlinený, Alexander Langer, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar
Lower Bounds on the Complexity of MSO1 Model-Checking CoRR (2011)
Alexander Langer, Peter Rossmanith, Somnath Sikdar
Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory - (Extended Abstract). TAMC (2011)
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh, Somnath Sikdar
FPT Algorithms for Connected Feedback Vertex Set. WALCOM (2010)
Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar
Are There Any Good Digraph Width Measures? IPEC (2010)
Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar
Are there any good digraph width measures? CoRR (2010)
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh, Somnath Sikdar
FPT Algorithms for Connected Feedback Vertex Set CoRR (2009)
Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, Somnath Sikdar
On the Directed Degree-Preserving Spanning Tree Problem. IWPEC (2009)
Daniel Lokshtanov, Saket Saurabh, Somnath Sikdar
Simpler Parameterized Algorithm for OCT. IWOCA (2009)
Hannes Moser, Somnath Sikdar
The parameterized complexity of the induced matching problem. Discret. Appl. Math. 157 (4) (2009)
Geevarghese Philip, Venkatesh Raman, Somnath Sikdar
Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels. ESA (2009)
Meena Mahajan, Venkatesh Raman, Somnath Sikdar
Parameterizing above or below guaranteed values. J. Comput. Syst. Sci. 75 (2) (2009)
Neeldhara Misra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar
The Budgeted Unique Coverage Problem and Color-Coding. CSR (2009)
Geevarghese Philip, Venkatesh Raman, Somnath Sikdar
-free and d-degenerate Graphs CoRR (2009)
Michael Dom, Somnath Sikdar
The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants. FAW (2008)
Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar
König Deletion Sets and Vertex Covers above the Matching Size. ISAAC (2008)
Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar, C. R. Subramanian
The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number. ISAAC (2007)
Hannes Moser, Venkatesh Raman, Somnath Sikdar
The Parameterized Complexity of the Unique Coverage Problem. ISAAC (2007)
Venkatesh Raman, Somnath Sikdar
Parameterized complexity of the induced subgraph problem in directed graphs. Inf. Process. Lett. 104 (3) (2007)
Venkatesh Raman, Saket Saurabh, Somnath Sikdar
Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques. Theory Comput. Syst. 41 (3) (2007)
Hannes Moser, Somnath Sikdar
The Parameterized Complexity of the Induced Matching Problem in Planar Graphs. FAW (2007)
Meena Mahajan, Venkatesh Raman, Somnath Sikdar
Parameterizing MAX SNP Problems Above Guaranteed Values. IWPEC (2006)
Venkatesh Raman, Saket Saurabh, Somnath Sikdar
Improved Exact Exponential Algorithms for Vertex Bipartization and Other Problems. ICTCS (2005)
Avishek Adhikari, Somnath Sikdar
A New (2, n)-Visual Threshold Scheme for Color Images. INDOCRYPT (2003)