Home
Saket Saurabh's picture

Saket Saurabh

Professor
  • E-mailSaket.Saurabh@uib.no
  • Visitor Address
    HIB - Thormøhlensgt. 55
  • Postal Address
    Postboks 7803
    5020 Bergen
Journal articles
  • Adler, Isolde Marianne; Kolliopoulos, Stavros G.; Krause, Philipp Klaus; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M. 2017. Irrelevant vertices for the planar Disjoint Paths Problem. Journal of combinatorial theory. Series B (Print). 122: 815-843. doi: 10.1016/j.jctb.2016.10.001
  • Agrawal, Akanksha; Gupta, Sushmita; Saurabh, Saket; Sharma, Roohani. 2017. Improved algorithms and combinatorial bounds for independent Feedback Vertex Set. Leibniz International Proceedings in Informatics. 63: 1-14. doi: 10.4230/LIPIcs.IPEC.2016.2
  • Ashok, Pradeesha; Kolay, Sudeshna; Meesum, Syed Mohammad; Saurabh, Saket. 2017. Parameterized complexity of strip packing and minimum volume packing. Theoretical Computer Science. 661: 56-64. doi: 10.1016/j.tcs.2016.11.034
  • Krithika, Ramaswamy; Rai, Ashutosh; Saurabh, Saket; Tale, Prafullkumar. 2017. Parameterized and exact algorithms for class domination coloring. Lecture Notes in Computer Science. 10139 LNCS: 336-349. doi: 10.1007/978-3-319-51963-0_26
  • Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Saurabh, Saket. 2017. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. SIAM journal on computing (Print). 46: 161-189. doi: 10.1137/140999980
  • Agrawal, Akanksha; Kolay, Sudeshna; Lokshtanov, Daniel; Saurabh, Saket. 2016. A faster FPT algorithm and a smaller kernel for block graph vertex deletion. Lecture Notes in Computer Science. 9644: 1-13. doi: 10.1007/978-3-662-49529-2_1
  • Agrawal, Akanksha; Lokshtanov, Daniel; Abdo Mouawad, Amer; Saurabh, Saket. 2016. SIMULTANEOUS Feedback Vertex set: A parameterized perspective. Leibniz International Proceedings in Informatics. 47: 7:1-7:15. doi: 10.4230/LIPIcs.STACS.2016.7
  • Agrawal, Akanksha; Lokshtanov, Daniel; Majumdar, Diptapriyo; Abdo Mouawad, Amer; Saurabh, Saket. 2016. Kernelization of cycle packing with relaxed disjointness constraints. Leibniz International Proceedings in Informatics. 55:26: 1-14. doi: 10.4230/LIPIcs.ICALP.2016.26
  • Agrawal, Akanksha; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav. 2016. Simultaneous feedback edge set: A parameterized perspective. Leibniz International Proceedings in Informatics. 64: 5.1-5.13. doi: 10.4230/LIPIcs.ISAAC.2016.5
  • Agrawal, Akanksha; Saurabh, Saket. 2016. Kernels for deletion to classes of acyclic digraphs. Leibniz International Proceedings in Informatics. 64: 6.1-6.12. doi: 10.4230/LIPIcs.ISAAC.2016.6
  • Ashok, Pradeesha; Kolay, Sudeshna; Saurabh, Saket. 2016. Parameterized complexity of red blue set cover for lines. Lecture Notes in Computer Science. 9644: 96-109. doi: 10.1007/978-3-662-49529-2_8
  • Bliznets, Ivan; Fomin, Fedor; Golovach, Petr; Karpov, Nikolay; Kulikov, Alexander S.; Saurabh, Saket. 2016. Parameterized Complexity of Superstring Problems. Algorithmica. Published ahead of print: 1-16. doi: 10.1007/s00453-016-0193-0
  • Bodlaender, Hans L.; Fomin, Fedor; Lokshtanov, Daniel; Penninkx, Eelko; Saurabh, Saket; Thilikos, Dimitrios M. 2016. (Meta) Kernelization. Journal of the ACM. 63:44. doi: 10.1145/2973749
  • Cygan, Marek; Dell, Holger; Lokshtanov, Daniel; Marx, Dániel; Nederlof, Jesper; Okamoto, Yoshio; Paturi, Ramamohan; Saurabh, Saket; Wahlström, Magnus. 2016. On problems as hard as CNF-SAT. ACM Transactions on Algorithms. 12:41. doi: 10.1145/2925416
  • Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket. 2016. Lower bounds for approximation schemes for closest string. Leibniz International Proceedings in Informatics. 53:12: 12.1-12.10. doi: 10.4230/LIPIcs.SWAT.2016.12
  • Drange, Pål Grønås; Dregi, Markus Sortland; Fomin, Fedor; Kreutzer, Stephan; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Reidl, Felix; Villaamil, Fernando Sánchez; Saurabh, Saket; Siebertz, Sebastian; Sikdar, Somnath. 2016. Kernelization and sparseness: The case of dominating set. Leibniz International Proceedings in Informatics. 47:31. 14 pages. doi: 10.4230/LIPIcs.STACS.2016.31
  • Fomin, Fedor; Gaspers, Serge; Lokshtanov, Daniel; Saurabh, Saket. 2016. Exact algorithms via monotone local search. Proceedings of the Annual ACM Symposium on Theory of Computing. 19-21-June-2016: 764-775. doi: 10.1145/2897518.2897551
  • Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Saurabh, Saket. 2016. Editing to connected f-degree graph. Leibniz International Proceedings in Informatics. 47:36: 1-15. doi: 10.4230/LIPIcs.STACS.2016.36
  • Fomin, Fedor; Kolay, Sudeshna; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket. 2016. Subexponential algorithms for rectilinear Steiner tree and arborescence problems. Leibniz International Proceedings in Informatics. 51: 39.1-39.15. doi: 10.4230/LIPIcs.SoCG.2016.39
  • Fomin, Fedor; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Saurabh, Saket. 2016. Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. Proceedings ... annual Symposium on Foundations of Computer Science. 2016-December: 515-524. doi: 10.1109/FOCS.2016.62
  • Fomin, Fedor; Lokshtanov, Daniel; Misra, Neeldhara; Philip, Geevarghese; Saurabh, Saket. 2016. Hitting forbidden minors: Approximation and kernelization. SIAM Journal on Discrete Mathematics. 30: 383-410. doi: 10.1137/140997889
  • Fomin, Fedor; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket. 2016. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM. 63:29. doi: 10.1145/2886094
  • Giannopoulou, Archontia; Lokshtanov, Daniel; Saurabh, Saket; Suchý, Ondřej. 2016. Tree deletion set has a polynomial kernel (but No OPTο(1) Approximation). SIAM Journal on Discrete Mathematics. 30: 1371-1384. doi: 10.1137/15M1038876
  • Kolay, Sudeshna; Panolan, Fahad; Raman, Venkatesh; Saurabh, Saket. 2016. Parameterized algorithms on perfect graphs for deletion to (r,l)-Graphs. Leibniz International Proceedings in Informatics. 58:75: 1-13. doi: 10.4230/LIPIcs.MFCS.2016.75
  • Meesum, Syed Mohammad; Saurabh, Saket. 2016. Rank reduction of directed graphs by vertex and edge deletions. Lecture Notes in Computer Science. 9644: 619-633. doi: 10.1007/978-3-662-49529-2_46
  • Rai, Ashutosh; Ramanujan, M.S.; Saurabh, Saket. 2016. A parameterized algorithm for mixed-cut. Lecture Notes in Computer Science. 9644: 672-685. doi: 10.1007/978-3-662-49529-2_50
  • Saurabh, Saket; Zehavi, Meirav. 2016. (k,n−k) -Max-Cut: An O∗(2p) - time algorithm and a polynomial kernel. Lecture Notes in Computer Science. 9644: 686-699. doi: 10.1007/978-3-662-49529-2_51
  • Bliznets, Ivan; Fomin, Fedor; Golovach, Petr; Karpov, Nikolay; Kulikov, Alexander S; Saurabh, Saket. 2015. Parameterized complexity of superstring problems. Lecture Notes in Computer Science. 9133: 89-99. doi: 10.1007/978-3-319-19929-0_8
  • Fernau, Henning; Fomin, Fedor; Philip, Geevarghese; Saurabh, Saket. 2015. On the parameterized complexity of vertex cover and edge cover with connectivity constraints. Theoretical Computer Science. 565: 1-15. doi: 10.1016/j.tcs.2014.10.035
  • Fomin, Fedor; Kaski, Petteri; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket. 2015. Parameterized single-exponential time polynomial space algorithm for steiner tree. Lecture Notes in Computer Science. 9134: 494-505. doi: 10.1007/978-3-662-47672-7_40
  • Fomin, Fedor; Saurabh, Saket; Misra, Neeldhara. 2015. Graph modification problems: A modern perspective. Lecture Notes in Computer Science. 9130: 3-6. doi: 10.1007/978-3-319-19647-3_1
  • Giannopoulou, Archontia; Jansen, Bart Maarten Paul; Lokshtanov, Daniel; Saurabh, Saket. 2015. Uniform kernelization complexity of hitting forbidden minors. Lecture Notes in Computer Science. 9134: 629-641. doi: 10.1007/978-3-662-47672-7_51
  • Goyal, Prachi; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket. 2015. Finding even subgraphs even faster. Leibniz International Proceedings in Informatics. 45: 434-447. doi: 10.4230/LIPIcs.FSTTCS.2015.434
  • Kolay, Sudeshna; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket. 2015. Quick but odd growth of cacti. Leibniz International Proceedings in Informatics. 43: 258-269. doi: 10.4230/LIPIcs.IPEC.2015.258
  • Lokshtanov, Daniel; Maadapuzhi Shridharan, Ramanujan; Saurabh, Saket. 2015. Linear time parameterized algorithms for subset feedback vertex set. Lecture Notes in Computer Science. 9134: 935-946. doi: 10.1007/978-3-662-47672-7_76
  • Lokshtanov, Daniel; Misra, Pranabendu; Panolan, Fahad; Saurabh, Saket. 2015. Deterministic truncation of linear matroids. Lecture Notes in Computer Science. 9134: 922-934. doi: 10.1007/978-3-662-47672-7_75
  • Lokshtanov, Daniel; Mouawad, Amer E.; Panolan, Fahad; Maadapuzhi Shridharan, Ramanujan; Saurabh, Saket. 2015. Reconfiguration on sparse graphs. Lecture Notes in Computer Science. 9214: 506-517. doi: 10.1007/978-3-319-21840-3_42
  • Meesum, Syed Mohammad; Misra, Pranabendu; Saurabh, Saket. 2015. Reducing rank of the adjacency matrix by graph modification. Lecture Notes in Computer Science. 9198: 361-373. doi: 10.1007/978-3-319-21398-9_29
  • Panolan, Fahad; Maadapuzhi Shridharan, Ramanujan; Saurabh, Saket. 2015. On the parameterized complexity of GIRTH and CONNECTIVITY problems on linear matroids. Lecture Notes in Computer Science. 9214: 566-577. doi: 10.1007/978-3-319-21840-3_47
  • Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket. 2015. B-chromatic number: Beyond NP-hardness. Leibniz International Proceedings in Informatics. 43: 389-401. doi: 10.4230/LIPIcs.IPEC.2015.389
  • Basavaraju, Manu; Fomin, Fedor; Golovach, Petr; Misra, Pranabendu; Maadapuzhi Shridharan, Ramanujan; Saurabh, Saket. 2014. Parameterized algorithms to preserve connectivity. Lecture Notes in Computer Science. 8572 LNCS: 800-811. doi: 10.1007/978-3-662-43948-7_66
  • Basavaraju, Manu; Fomin, Fedor; Golovach, Petr; Saurabh, Saket. 2014. Connecting vertices by independent trees. Leibniz International Proceedings in Informatics. 29: 73-84. doi: 10.4230/LIPIcs.FSTTCS.2014.73
  • Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Saurabh, Saket. 2014. On cutwidth parameterized by vertex cover. Algorithmica. 68: 940-953. doi: 10.1007/s00453-012-9707-6
  • Dom, Michael; Lokshtanov, Daniel; Saurabh, Saket. 2014. Kernelization lower bounds through colors and IDs. ACM Transactions on Algorithms. 11. doi: 10.1145/2650261
  • Fernau, Henning; Fomin, Fedor; Lokshtanov, Daniel; Mnich, Matthias; Philip, Geevarghese; Saurabh, Saket. 2014. Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems. Tsinghua Science and Technology. 19: 374-386. doi: 10.1109/TST.2014.6867519
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket. 2014. Almost optimal lower bounds for problems parameterized by clique-width. SIAM journal on computing (Print). 43: 1541-1563. doi: 10.1137/130910932
  • Fomin, Fedor; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket. 2014. Representative sets of product families. Lecture Notes in Computer Science. 8737 LNCS: 443-454. doi: 10.1007/978-3-662-44777-2_37
  • Giannopoulou, Archontia; Lokshtanov, Daniel; Saurabh, Saket; Suchy, Ondřej. 2014. Tree deletion set has a polynomial kernel (but no OPTO(1) approximation). Leibniz International Proceedings in Informatics. 29: 85-96. doi: 10.4230/LIPIcs.FSTTCS.2014.85
  • Lokshtanov, Daniel; Narayanaswamy, N.S.; Raman, Venkatesh; Ramanujan, M.S.; Saurabh, Saket. 2014. Faster parameterized algorithms using linear programming. ACM Transactions on Algorithms. 11. doi: 10.1145/2566616
  • Lokshtanov, Daniel; Saurabh, Saket; Suchy, Ondrej. 2014. Solving Multicut faster than 2n. Lecture Notes in Computer Science. 8737 LNCS: 666-676. doi: 10.1007/978-3-662-44777-2_55
  • Dorn, Frederic; Fomin, Fedor; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket. 2013. Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs. Information and Computation. 233: 60-70. doi: 10.1016/j.ic.2013.11.006
  • Fomin, Fedor; Gaspers, Serge; Saurabh, Saket; Thomasse, Stephane. 2013. A linear vertex kernel for maximum internal spanning tree. Journal of computer and system sciences (Print). 79: 1-6. doi: 10.1016/j.jcss.2012.03.004
  • Fomin, Fedor; Grandoni, Fabrizio; Kratsch, Dieter; Lokshtanov, Daniel; Saurabh, Saket. 2013. Computing optimal Steiner trees in polynomial space. Algorithmica. 65: 584-604. doi: 10.1007/s00453-012-9612-z
  • Fomin, Fedor; Lokshtanov, Daniel; Misra, Neeldhara; Philip, Geevarghese; Saurabh, Saket. 2013. Quadratic upper bounds on the Erdős–Pósa property for a generalization of packing and covering cycles. Journal of Graph Theory. 74: 417-424. doi: 10.1002/jgt.21720
  • Fomin, Fedor; Saurabh, Saket; Villanger, Yngve. 2013. A polynomial kernel for proper interval vertex deletion. SIAM Journal on Discrete Mathematics. 27: 1964-1976. doi: 10.1137/12089051X
  • Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket. 2013. Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization. Information and Computation. 231: 109-116. doi: 10.1016/j.ic.2013.08.007
  • Lokshtanov, Daniel; Misra, Neeldhara; Saurabh, Saket. 2013. Imbalance is fixed parameter tractable. Information Processing Letters. doi: 10.1016/j.ipl.2013.06.010
  • Amini, Omid; Fomin, Fedor; Saurabh, Saket. 2012. Counting subgraphs via homomorphisms. SIAM Journal on Discrete Mathematics. 26: 695-717. doi: 10.1137/100789403
  • Binkele-Raible, Daniel; Fernau, Henning; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Villanger, Yngve. 2012. Kernel(s) for Problems with no Kernel: On Out-Trees with Many Leaves. ACM Transactions on Algorithms. 8. 19 pages. doi: 10.1145/2344422.2344428
  • Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Saurabh, Saket. 2012. On Cutwidth Parameterized by Vertex Cover. Algorithmica.
  • Fomin, Fedor; Grandoni, Fabrizio; Lokshtanov, Daniel; Saurabh, Saket. 2012. Sharp separation and applications to exact and parameterized algorithms. Algorithmica. 63: 692-706. doi: 10.1007/s00453-011-9555-9
  • Fomin, Fedor; Lokshtanov, Daniel; Misra, Neeldhara; Saurabh, Saket. 2012. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms (extended abstract). Proceedings ... annual Symposium on Foundations of Computer Science. 470-479. doi: 10.1109/FOCS.2012.62
  • Fomin, Fedor; Saurabh, Saket; Villanger, Yngve. 2012. A Polynomial Kernel for Proper Interval Vertex Deletion. Lecture Notes in Computer Science. 7501: 467-478.
  • Amini, Omid; Fomin, Fedor; Saurabh, Saket. 2011. Implicit branching and parameterized partial cover problems. Journal of computer and system sciences (Print). 77: 1159-1171. doi: 10.1016/j.jcss.2010.12.002
  • Bessy, Stephane; Fomin, Fedor; Gaspers, Serge; Paul, Christophe; Perez, Anthony; Saurabh, Saket; Thomasse, Stephane. 2011. Kernels for feedback arc set in tournaments. Journal of computer and system sciences (Print). 77: 1071-1078. doi: 10.1016/j.jcss.2010.10.001
  • Fellows, Michael R.; Fomin, Fedor; Lokshtanov, Daniel; Rosamond, Frances; Saurabh, Saket; Szeider, Stefan; Thomassen, Carsten. 2011. On the complexity of some colorful problems parameterized by treewidth. Information and Computation. 209: 143-153. doi: 10.1016/j.ic.2010.11.026
  • Fomin, Fedor; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket. 2011. Subexponential algorithms for partial cover problems. Information Processing Letters. 111: 814-818. doi: 10.1016/j.ipl.2011.05.016
  • Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket. 2011. An exact algorithm for minimum distortion embedding. Theoretical Computer Science. 412: 3530-3536. doi: 10.1016/j.tcs.2011.02.043
  • Fomin, Fedor; Saurabh, Saket; Thilikos, Dimitrios M. 2011. Strengthening Erdos-Posa Property for Minor-Closed Graph Classes. Journal of Graph Theory. 66: 235-240. doi: 10.1002/jgt.20503
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Meister, Daniel; Saurabh, Saket. 2011. Bandwidth on AT-free graphs. Theoretical Computer Science. 412: 7001-7008. doi: 10.1016/j.tcs.2011.09.011
  • Lokshtanov, Daniel; Mnich, Matthias; Saurabh, Saket. 2011. A linear kernel for a planar connected dominating set. Theoretical Computer Science. 412: 2536-2543. doi: 10.1016/j.tcs.2010.10.045
  • Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket; Sikdar, Somnath. 2011. On the directed Full Degree Spanning Tree problem. Discrete Optimization. 8: 97-109. doi: 10.1016/j.disopt.2010.09.001
  • Cohen, Nathann; Fomin, Fedor; Gutin, Gregory; Kim, Eun Jung; Saurabh, Saket; Yeo, Anders. 2010. Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. Journal of computer and system sciences (Print). 76: 650-662. doi: 10.1016/j.jcss.2010.01.001
  • Fomin, Fedor; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket. 2010. Iterative compression and exact algorithms. Theoretical Computer Science. 411: 1045-1053. doi: 10.1016/j.tcs.2009.11.012
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket. 2010. Intractability of clique-width parameterizations. SIAM journal on computing (Print). 39: 1941-1956. doi: 10.1137/080742270
  • Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket. 2010. Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing. Lecture Notes in Computer Science. 6139: 334-345.
  • Lokshtanov, Daniel; Misra, Neeldhara; Saurabh, Saket. 2010. Imbalance is fixed parameter tractable. Lecture Notes in Computer Science. 6196: 199-208. doi: 10.1007/978-3-642-14031-0_23
  • Alon, Noga; Lokshtanov, Daniel; Saurabh, Saket. 2009. Fast FAST. Lecture Notes in Computer Science. 5555: 49-58. doi: 10.1007/978-3-642-02927-1_6
  • Amini, Omid; Fomin, Fedor; Saurabh, Saket. 2009. Counting Subgraphs via Homomorphisms. Lecture Notes in Computer Science. 5555: 71-82. doi: 10.1007/978-3-642-02927-1_8
  • Bessy, Stephane; Fomin, Fedor; Gaspers, Serge; Paul, Christophe; Perez, Anthony; Saurabh, Saket; Thomasse, Stephane. 2009. Kernels for Feedback Arc Set In Tournaments. Leibniz International Proceedings in Informatics. 4: 37-47.
  • Cohen, Nathann; Fomin, Fedor; Gutin, Gregory; Kim, Eun Jung; Saurabh, Saket; Yeo, Anders. 2009. Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem. Lecture Notes in Computer Science. 5609: 37-46. doi: 10.1007/978-3-642-02882-3_5
  • Dom, Michael; Lokshtanov, Daniel; Saurabh, Saket. 2009. Incompressibility through Colors and IDs. Lecture Notes in Computer Science. 5555: 378-389. doi: 10.1007/978-3-642-02927-1_32
  • Fellows, Michael; Fomin, Fedor; Lokshtanov, Daniel; Losievskaja, Elena; Rosamond, Frances; Saurabh, Saket. 2009. Distortion Is Fixed Parameter Tractable. Lecture Notes in Computer Science. 5555: 463-474. doi: 10.1007/978-3-642-02927-1_39
  • Fellows, Michael; Lokshtanov, Daniel; Misra, Neeldhara; Mnich, Matthias; Rosamond, Frances; Saurabh, Saket. 2009. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems. 45: 822-848. doi: 10.1007/s00224-009-9167-9
  • Fernau, Henning; Fomin, Fedor; Lokshtanov, Daniel; Raible, Daniel; Saurabh, Saket; Villanger, Yngve. 2009. Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. Leibniz International Proceedings in Informatics. 3: 421-432.
  • Fomin, Fedor; Gaspers, Serge; Saurabh, Saket; Stepanov, Alexey. 2009. On two techniques of combining branching and treewidth. Algorithmica. 54: 181-207. doi: 10.1007/s00453-007-9133-3
  • Fomin, Fedor; Gaspers, Serge; Saurabh, Saket; Thomasse, Stephane. 2009. A Linear Vertex Kernel for Maximum Internal Spanning Tree. Lecture Notes in Computer Science. 5878: 275-282. doi: http://dx.doi.org/10.1007/978-3-642-10631-6_29
  • Fomin, Fedor; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket. 2009. Subexponential Algorithms for Partial Cover Problems. Leibniz International Proceedings in Informatics. 4: 193-201.
  • Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket. 2009. An Exact Algorithm for Minimum Distortion Embedding. Lecture Notes in Computer Science. 5911: 112-121. doi: 10.1007/978-3-642-11409-0_10
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Meister, Daniel; Saurabh, Saket. 2009. Bandwidth on AT-Free Graphs. Lecture Notes in Computer Science. 5878: 573-582. doi: 10.1007/978-3-642-10631-6_59
  • Lokshtanov, Daniel; Mnich, Matthias; Saurabh, Saket. 2009. Linear Kernel for Planar Connected Dominating Set. Lecture Notes in Computer Science. 5532: 281-290. doi: 10.1007/978-3-642-02017-9_31
  • Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket; Sikdar, Somnath. 2009. On the Directed Degree-Preserving Spanning Tree Problem. Lecture Notes in Computer Science. 5917: 276-287. doi: 10.1007/978-3-642-11269-0_23
  • Lokshtanov, Daniel; Saurabh, Saket; Sikdar, Somnath. 2009. Simpler Parameterized Algorithm for OCT. Lecture Notes in Computer Science. 5874: 380-384. doi: 10.1007/978-3-642-10217-2_37
  • Misra, Neeldhara; Raman, Venkatesh; Saurabh, Saket; Sikdar, Somnath. 2009. The Budgeted Unique Coverage Problem and Color-Coding. Lecture Notes in Computer Science. 5675: 310-321. doi: 10.1007/978-3-642-03351-3_29
  • Saurabh, Saket; Lokshtanov, Daniel. 2009. Even Faster Algorithm for Set Splitting! Lecture Notes in Computer Science. 5917: 288-299.
  • Alon, Noga; Fomin, Fedor; Gutin, Gregory; Krivelevich, Michael; Saurabh, Saket. 2008. Spanning directed trees with many leaves. SIAM Journal on Discrete Mathematics. 23: 466-476. doi: 10.1137/070710494
  • Amini, Omid; Fomin, Fedor; Saurabh, Saket. 2008. Implicit Branching and Parameterized Partial Cover Problems (Extended Abstract). Dagstuhl Seminar Proceedings. 08004. 12 pages.
  • Amini, Omid; Peleg, David; Pérennes, Stéphane; Sau, Ignasi; Saurabh, Saket. 2008. Degree-Constrained Subgraph Problems: Hardness and Approximation Results. Lecture Notes in Computer Science. 5426: 29-42. doi: 10.1007/978-3-540-93980-1_3
  • Amini, Omid; Sau, Ignasi; Saurabh, Saket. 2008. Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem. Lecture Notes in Computer Science. 5018: 13-29. doi: 10.1007/978-3-540-79723-4_4
  • Dom, Michael; Lokshtanov, Daniel; Saurabh, Saket; Villanger, Yngve. 2008. Capacitated Domination and Covering: A Parameterized Perspective. Lecture Notes in Computer Science. 5018: 78-90.
  • Fellows, Michael; Lokshtanov, Daniel; Misra, Neeldhara; Rosamond, Frances; Saurabh, Saket. 2008. Graph Layout problems Parameterized by Vertex Cover. Lecture Notes in Computer Science. 5369: 294-305. doi: 10.1007/978-3-540-92182-0_28
  • Fomin, Fedor; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket. 2008. Iterative Compression and Exact Algorithms. Lecture Notes in Computer Science. 5162: 335-346.
  • Gaspers, Serge; Saurabh, Saket; Stepanov, Alexey. 2008. A Moderately Exponential Time Algorithm for Full Degree Spanning Tree. Lecture Notes in Computer Science. 4978: 479-489.
  • Mishra, Sounaka; Raman, Venkatesh; Saurabh, Saket; Sikdar, Somnath. 2008. König Deletion Sets and Vertex Covers above the Matching Size. Lecture Notes in Computer Science. 5369: 836-847. doi: 10.1007/978-3-540-92182-0_73
  • Raman, Venkatesh; Saurabh, Saket. 2008. Short Cycles Make W -hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles. Algorithmica. 52: 203-225. doi: 10.1007/s00453-007-9148-9
  • Raman, Venkatesh; Saurabh, Saket; Srihari, Sriganesh. 2008. Parameterized Algorithms for Generalized Domination. Lecture Notes in Computer Science. 5165: 116-126. doi: 10.1007/978-3-540-85097-7_11
  • Alon, Noga; Fomin, Fedor; Gutin, Gregory; Krivelevich, Michael; Saurabh, Saket. 2007. Better Algorithms and Bounds for Directed Maximum Leaf Problems. Lecture Notes in Computer Science. 4855: 316-327.
  • Alon, Noga; Fomin, Fedor; Gutin, Gregory; Krivelevich, Michael; Saurabh, Saket. 2007. Parameterized Algorithms for Directed Maximum Leaf Problems. Lecture Notes in Computer Science. 4596: 352-362.
  • Fomin, Fedor; Gaspers, Serge; Saurabh, Saket. 2007. Improved Exact Algorithms for Counting 3- and 4-Colorings. Lecture Notes in Computer Science. 4598: 65-74.
Book sections
  • Fellows, Michael; Rosamond, Frances; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Villanger, Yngve. 2009. Local Search: Is Brute-Force Avoidable? Raport, pages 486-491. In:
    • Boutilier, Craig. 2009. IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence. AAAI Press. 2106 pages. ISBN: 978-1-57735-426-0.

More information in national current research information system (CRIStin)