Hjem
Daniel Lokshtanovs bilde

Daniel Lokshtanov

Professor
  • E-postDaniel.Lokshtanov@uib.no
  • Telefon+47 55 58 41 56
  • Besøksadresse
    HIB - Thormøhlensgt. 55
  • Postadresse
    Postboks 7803
    5020 Bergen
Bøker
  • Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav. 2019. Kernelization. Theory of Parameterized Preprocessing. Cambridge University Press. 490 sider. ISBN: 9781107415157.
  • Cygan, Marek; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket. 2015. Parameterized Algorithms. 600 sider. ISBN: 978-3-319-21275-3.
Tidsskriftartikler
  • Fomin, Fedor; Gaspers, Serge; Lokshtanov, Daniel; Saurabh, Saket. 2019. Exact algorithms via monotone local search. Journal of the ACM. 66: 8:1-8:23. doi: 10.1145/3284176
  • Fomin, Fedor; Le, Tien-Nam; Lokshtanov, Daniel; Saurabh, Saket; Thomasse, Stephan; Zehavi, Meirav. 2019. Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems. ACM Transactions on Algorithms (TALG). 15. 44 sider. doi: 10.1145/3293466
  • Fomin, Fedor; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav. 2019. Decomposition of map graphs with applications. Leibniz International Proceedings in Informatics. 132: 60:1-60:15. doi: 10.4230/LIPIcs.ICALP.2019.60
  • Fomin, Fedor; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav. 2019. Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs. Discrete & Computational Geometry. 1-33. doi: 10.1007/s00454-018-00054-x
  • Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket; Zehavi, Meirav. 2019. Packing cycles faster than Erdos?Posa. SIAM Journal on Discrete Mathematics. 33: 1194-1215. doi: 10.1137/17M1150037
  • Agrawal, Akanksha; Jain, Pallavi; Kanesh, Lawqueen; Lokshtanov, Daniel; Saurabh, Saket. 2018. Conflict Free Feedback Vertex Set: A Parameterized Dichotomy. Leibniz International Proceedings in Informatics. 117: 53:1-53:15. doi: 10.4230/LIPIcs.MFCS.2018.53
  • Agrawal, Akanksha; Krithika, R; Lokshtanov, Daniel; Mouawad, Amer E.; Ramanujan, MS. 2018. On the parameterized complexity of simultaneous deletion problems. Leibniz International Proceedings in Informatics. 93: 9:1-9:14. doi: 10.4230/LIPIcs.FSTTCS.2017.9
  • Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav. 2018. Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion. ACM Transactions on Algorithms (TALG). 15. 28 sider. doi: 10.1145/3284356
  • Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav. 2018. Polylogarithmic approximation algorithms for weighted-F-Deletion problems. Leibniz International Proceedings in Informatics. 116: 1:1-1:15. doi: 10.4230/LIPIcs.APPROX-RANDOM.2018.1
  • Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav. 2018. Erdos-Posa property of obstructions to interval graphs. Leibniz International Proceedings in Informatics. 96: 1-15. doi: 10.4230/LIPIcs.STACS.2018.7
  • Agrawal, Akanksha; Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket. 2018. Simultaneous feedback vertex set: A parameterized perspective. ACM Transactions on Computation Theory. 10. doi: 10.1145/3265027
  • Bacso, Gabor; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Tuza, Zsolt; van Leeuwen, Erik Jan. 2018. Subexponential-Time Algorithms for Maximum Independent Set in Pt-Free and Broom-Free Graphs. Algorithmica. 81: 421-438. doi: 10.1007/s00453-018-0479-5
  • Banik, Aritra; Choudhary, Pratibha; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket. 2018. A polynomial sized kernel for tracking paths problem. Lecture Notes in Computer Science. 10807 LNCS: 94-107. doi: 10.1007/978-3-319-77404-6_8
  • Carpenter, Timothy; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Sidiropoulos, Anastasios. 2018. Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces. Leibniz International Proceedings in Informatics. 99: 21:1-21:14. doi: 10.4230/LIPIcs.SoCG.2018.21
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket. 2018. Covering Vectors by Spaces: Regular Matroids. SIAM Journal on Discrete Mathematics. 32: 2512-2565. doi: 10.1137/17M1151250
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav. 2018. Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring. ACM Transactions on Algorithms (TALG). 15. 27 sider. doi: 10.1145/3280824
  • Fomin, Fedor; Lokshtanov, Daniel; Meesum, Syed Mohammad; Saurabh, Saket; Zehavi, Meirav. 2018. Matrix rigidity from the viewpoint of parameterized complexity. SIAM Journal on Discrete Mathematics. 32: 966-985. doi: 10.1137/17M112258X
  • Fomin, Fedor; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav. 2018. Long directed (s,t)-path: FPT algorithm. Information Processing Letters. 140: 8-12. doi: 10.1016/j.ipl.2018.04.018
  • Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket. 2018. Excluded grid minors and efficient polynomial-time approximation schemes. Journal of the ACM. 65: 1-44. doi: 10.1145/3154833
  • Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Pilipczuk, Michal; Wrochna, Marcin. 2018. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Transactions on Algorithms (TALG). 14. doi: 10.1145/3186898
  • Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M. 2018. Kernels for (Connected) dominating set on graphs with excluded topological minors. ACM Transactions on Algorithms (TALG). 14. doi: 10.1145/3155298
  • Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav. 2018. Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 262-273.
  • Lokshtanov, Daniel; Maadapuzhi Shridharan, Ramanujan; Saurabh, Saket. 2018. Linear time parameterized algorithms for subset feedback vertex set. ACM Transactions on Algorithms (TALG). 14. 37 sider. doi: 10.1145/3155299
  • Lokshtanov, Daniel; Marx, Daniel; Saurabh, Saket. 2018. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Transactions on Algorithms (TALG). 14: 1-30. doi: 10.1145/3170442
  • Lokshtanov, Daniel; Marx, Daniel; Saurabh, Saket. 2018. Slightly superexponential parameterized problems. SIAM journal on computing (Print). 47: 675-702. doi: 10.1137/16M1104834
  • Lokshtanov, Daniel; Misra, Pranabendu; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav. 2018. Quasipolynomial representation of transversal matroids with applications in parameterized complexity. Leibniz International Proceedings in Informatics. 94: 1-13. doi: 10.4230/LIPIcs.ITCS.2018.32
  • Lokshtanov, Daniel; Mouawad, Amer E. 2018. The complexity of independent set reconfiguration on bipartite graphs. ACM Transactions on Algorithms (TALG). 15: 1-19. doi: 10.1145/3280825
  • Lokshtanov, Daniel; Mouawad, Amer E.; Panolan, Fahad; Maadapuzhi Shridharan, Ramanujan; Saurabh, Saket. 2018. Reconfiguration on sparse graphs. Journal of computer and system sciences (Print). 95: 122-131. doi: 10.1016/j.jcss.2018.02.004
  • Lokshtanov, Daniel; Nishimura, Naomi. 2018. Preface. Leibniz International Proceedings in Informatics. 89. doi: 10.4230/LIPIcs.IPEC.2017
  • Lokshtanov, Daniel; Pilipczuk, Michal; Saurabh, Saket. 2018. Below all subsets for minimal connected dominating set. SIAM Journal on Discrete Mathematics. 32: 2332-2345. doi: 10.1137/17M1138753
  • Lokshtanov, Daniel; Ramanujan, M.S.; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav. 2018. Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS. Leibniz International Proceedings in Informatics. 107: 110:1-110:4. doi: 10.4230/LIPIcs.ICALP.2018.110
  • Lokshtanov, Daniel; Ramanujan, MS; Saurabh, Saket; Zehavi, Meirav. 2018. Reducing CMSO model checking to highly connected graphs. Leibniz International Proceedings in Informatics. 107: 135:1-135:14. doi: 10.4230/LIPIcs.ICALP.2018.135
  • Lokshtanov, Daniel; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav. 2018. Balanced judicious bipartition is fixed-paramater tractable. Leibniz International Proceedings in Informatics. 93: 40:1-40:15. doi: 10.4230/LIPIcs.FSTTCS.2017.40
  • 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; Lokshtanov, Daniel; Mouawad, Amer E. 2017. Critical node cut parameterized by treewidth and solution size is W[1]-Hard. Lecture Notes in Computer Science. 10520 LNCS: 32-44. doi: 10.1007/978-3-319-68705-6_3
  • Agrawal, Akanksha; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav. 2017. Split contraction: The untold story. Leibniz International Proceedings in Informatics. 66:5: 1-14. doi: 10.4230/LIPIcs.STACS.2017.5
  • Chitnis, Rajesh; Fomin, Fedor; Lokshtanov, Daniel; Misra, Pranabendu; Maadapuzhi Shridharan, Ramanujan; Saurabh, Saket. 2017. Faster exact algorithms for some terminal set problems. Journal of computer and system sciences (Print). 88: 195-207. doi: 10.1016/j.jcss.2017.04.003
  • Crespelle, Christophe; Lokshtanov, Daniel; Phan, Thi Ha Duong; Thierry, Eric. 2017. Faster and enhanced inclusion-minimal cograph completion. Lecture Notes in Computer Science. 10627 LNCS: 210-224. doi: 10.1007/978-3-319-71150-8_19
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket. 2017. Spanning Circuits in Regular Matroids. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 1433-1441.
  • Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket. 2017. Covering vectors by spaces: Regular matroids. Leibniz International Proceedings in Informatics. 80: 1-15. doi: 10.4230/LIPIcs.ICALP.2017.56
  • Fomin, Fedor; Lokshtanov, Daniel; Meesum, Syed Mohammad; Saurabh, Saket; Zehavi, Meirav. 2017. Matrix rigidity from the viewpoint of parameterized complexity. Leibniz International Proceedings in Informatics. 66. doi: 10.4230/LIPIcs.STACS.2017.32
  • Fomin, Fedor; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket. 2017. Representative families of product families. ACM Transactions on Algorithms (TALG). 13:36: 1-29. doi: 10.1145/3039243
  • Fomin, Fedor; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav. 2017. Finding, hitting and packing cycles in subexponential time on unit disk graphs. Leibniz International Proceedings in Informatics. 80: 1-15. doi: 10.4230/LIPIcs.ICALP.2017.65
  • Giannopoulou, Archontia; Jansen, Bart M.P.; Lokshtanov, Daniel; Saurabh, Saket. 2017. Uniform kernelization complexity of hitting forbidden minors. ACM Transactions on Algorithms (TALG). 13:35: 1-35. doi: 10.1145/3029051
  • Jones, Mark; Lokshtanov, Daniel; Maadapuzhi Shridharan, Ramanujan; Saurabh, Saket; Suchy, Ondřej. 2017. Parameterized complexity of directed Steiner tree on sparse graphs. SIAM Journal on Discrete Mathematics. 31: 1294-1327. doi: 10.1137/15M103618X
  • Kolay, Sudeshna; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket. 2017. Quick but Odd Growth of Cacti. Algorithmica. 79: 271-290. doi: 10.1007/s00453-017-0317-1
  • Kumar, Mithilesh; Lokshtanov, Daniel. 2017. A 2lk kernel for l-component order connectivity. Leibniz International Proceedings in Informatics. 63:20: 1-14. doi: 10.4230/LIPIcs.IPEC.2016.20
  • Lokshtanov, Daniel; Misra, Pranabendu; Ramanujan, M. S.; Saurabh, Saket. 2017. Hitting selected (ODD) Cycles. SIAM Journal on Discrete Mathematics. 31: 1581-1615. doi: 10.1137/15M1041213
  • Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket; Zehavi, Meirav. 2017. Packing cycles faster than Erdös-Pósa. Leibniz International Proceedings in Informatics. 80: 1-15. doi: 10.4230/LIPIcs.ICALP.2017.71
  • Lokshtanov, Daniel; Panolan, Fahad; Ramanujan, M. S.; Saurabh, Saket. 2017. Lossy kernelization. Proceedings of the Annual ACM Symposium on Theory of Computing. Part F128415: 224-237. doi: 10.1145/3055399.3055456
  • 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
  • Lokshtanov, Daniel; Pilipczuk, Marcin; van Leeuwen, Erik Jan. 2017. Independence and efficient domination on P6-free graphs. ACM Transactions on Algorithms (TALG). 14. doi: 10.1145/3147214
  • Lokshtanov, Daniel; Ramanujan, M. S.; Saurabh, Saket. 2017. A linear-Time parameterized algorithm for node unique label cover. Leibniz International Proceedings in Informatics. 87. doi: 10.4230/LIPIcs.ESA.2017.57
  • 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
  • Bodlaender, Hans L.; Drange, Pål Grønås; Dregi, Markus Sortland; Fomin, Fedor; Lokshtanov, Daniel; Pilipczuk, Michal Pawel. 2016. A $c^k n$ 5-approximation algorithm for treewidth. SIAM journal on computing (Print). 45: 317-378. doi: 10.1137/130947374
  • 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 (TALG). 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 sider. 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; 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
  • Gajarský, Jakub; Hliněný, Petr; Obdržálek, Jan; Lokshtanov, Daniel; Ramanujan, M.S. 2016. A new perspective on FO model checking of dense graph classes. Logic in Computer Science. 05-08-July-2016: 176-184. doi: 10.1145/2933575.2935314
  • 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
  • Hassan, Olawale; Kanj, Iyad; Lokshtanov, Daniel; Perkovic, Ljubomir. 2016. On the ordered list subgraph embedding problems. Algorithmica. 74: 992-1018. doi: 10.1007/s00453-015-9980-2
  • Kumar, Mithilesh; Lokshtanov, Daniel. 2016. Faster exact and parameterized algorithm for feedback vertex set in tournaments. Leibniz International Proceedings in Informatics. 47:13: 24.1-24.15. doi: 10.4230/LIPIcs.STACS.2016.49
  • Boucher, Christina; Lo, Christine; Lokshtanov, Daniel. 2015. Consensus patterns (Probably) has no EPTAS. Lecture Notes in Computer Science. 9294: 239-250. doi: 10.1007/978-3-662-48350-3_21
  • Drange, Pål Grønås; Dregi, Markus Sortland; Lokshtanov, Daniel; Sullivan, Blair D. 2015. On the threshold of intractability. Lecture Notes in Computer Science. 9294: 411-423. doi: 10.1007/978-3-662-48350-3_35
  • 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
  • Gabizon, Ariel; Lokshtanov, Daniel; Pilipczuk, Michal Pawel. 2015. Fast algorithms for parameterized problems with relaxed disjointness constraints. Lecture Notes in Computer Science. 9294: 545-556. doi: 10.1007/978-3-662-48350-3_46
  • 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
  • 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
  • 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 (TALG). 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
  • Heggernes, Pinar; van 't Hof, Pim; Lévêque, Benjamin; Lokshtanov, Daniel; Paul, Christophe. 2014. Contracting graphs to paths and trees. Algorithmica. 68: 109-132. doi: 10.1007/s00453-012-9670-2
  • Lokshtanov, Daniel; Narayanaswamy, N.S.; Raman, Venkatesh; Ramanujan, M.S.; Saurabh, Saket. 2014. Faster parameterized algorithms using linear programming. ACM Transactions on Algorithms (TALG). 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
  • Bodlaender, Hans L.; Drange, Pål Grønås; Dregi, Markus Sortland; Fomin, Fedor; Lokshtanov, Daniel; Pilipczuk, Michal Pawel. 2013. An O(c^k n) 5-approximation algorithm for treewidth. Proceedings ... annual Symposium on Foundations of Computer Science. 54: 499-508. doi: 10.1109/FOCS.2013.60
  • 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; 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
  • 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
  • Heggernes, Pinar; van 't Hof, Pim; Lokshtanov, Daniel; Paul, Christophe. 2013. Obtaining a bipartite graph by contracting few edges. SIAM Journal on Discrete Mathematics. 27: 2143-2156. doi: 10.1137/130907392
  • Lokshtanov, Daniel; Marx, Daniel. 2013. Clustering with local restrictions. Information and Computation. 222: 278-292. doi: 10.1016/j.ic.2012.10.016
  • Lokshtanov, Daniel; Misra, Neeldhara; Saurabh, Saket. 2013. Imbalance is fixed parameter tractable. Information Processing Letters. doi: 10.1016/j.ipl.2013.06.010
  • 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 (TALG). 8. 19 sider. 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; Golovach, Petr; Lokshtanov, Daniel. 2012. Cops and robber game without recharging. Theory of Computing Systems. 50: 611-620. doi: 10.1007/s00224-011-9360-5
  • 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; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket; Rao, B.V. Raghavendra. 2012. Faster algorithms for finding and counting subgraphs. Journal of computer and system sciences (Print). 78: 698-706. doi: 10.1016/j.jcss.2011.10.001
  • Heggernes, Pinar; van 't Hof, Pim; Lokshtanov, Daniel; Nederlof, Jesper. 2012. Computing the cutwidth of bipartite permutation graphs in linear time. SIAM Journal on Discrete Mathematics. 26: 1008-1021. doi: 10.1137/110830514
  • Heggernes, Pinar; van 't Hof, Pim; Lévêque, Benjamin; Lokshtanov, Daniel; Paul, Christophe. 2012. Contracting graphs to paths and trees. Lecture Notes in Computer Science. 7112: 55-66. doi: 10.1007/978-3-642-28050-4_5
  • Ben-Zwi, Oren; Hermelin, Danny; Lokshtanov, Daniel; Newman, Ilan. 2011. Treewidth governs the complexity of target set selection. Discrete Optimization. 8: 87-96. doi: 10.1016/j.disopt.2010.09.007
  • 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; Golovach, Petr; Lokshtanov, Daniel. 2011. Guard games on graphs: Keep the intruder out! Theoretical Computer Science. 412: 6484-6497. doi: 10.1016/j.tcs.2011.08.024
  • Fomin, Fedor; Kratochvil, Jan; Lokshtanov, Daniel; Mancini, Federico; Telle, Jan Arne. 2011. On the Complexity of Reconstructing H-Free Graphs from Their Star Systems. Journal of Graph Theory. 68: 113-124. doi: 10.1002/jgt.20544
  • 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
  • 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
  • Heggernes, Pinar; Lokshtanov, Daniel; Mihai, Rodica; Papadopoulos, Charis. 2011. Cutwidth of Split Graphs and Threshold Graphs. SIAM Journal on Discrete Mathematics. 25: 1418-1437. doi: 10.1137/080741197
  • 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
  • Dorn, Frederic; Fomin, Fedor; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket. 2010. Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. Leibniz International Proceedings in Informatics. 5: 251-262.
  • 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.
  • Heggernes, Pinar; Lokshtanov, Daniel; Nederlof, Jesper; Paul, Christophe; Telle, Jan Arne. 2010. Generalized graph clustering: recognizing (p,q)-cluster graphs. Lecture Notes in Computer Science. 6410: 171-183.
  • Heggernes, Pinar; van 't Hof, Pim; Lokshtanov, Daniel; Nederlof, Jesper. 2010. Computing the cutwidth of bipartite permutation graphs in linear time. Lecture Notes in Computer Science. 6410: 75-87.
  • Lokshtanov, Daniel. 2010. On the complexity of computing treelength. Discrete Applied Mathematics. 158: 820-827. doi: 10.1016/j.dam.2009.10.007
  • Lokshtanov, Daniel. 2010. Algorithmic Lower Bounds for Problems on Decomposable Graphs. Lecture Notes in Computer Science. 6281: 37.
  • Lokshtanov, Daniel; Mancini, Federico; Papadopoulos, Charis. 2010. Characterizing and computing minimal cograph completions. Discrete Applied Mathematics. 158: 755-764. doi: 10.1016/j.dam.2009.01.016
  • 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
  • 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; 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. 2009. Finding the longest isometric cycle in a graph. Discrete Applied Mathematics. 157: 2670-2674. doi: 10.1016/j.dam.2008.08.008
  • 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
  • Saurabh, Saket; Lokshtanov, Daniel. 2009. Even Faster Algorithm for Set Splitting! Lecture Notes in Computer Science. 5917: 288-299.
  • 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; Kratochvil, Jan; Lokshtanov, Daniel; Mancini, Federico; Telle, Jan Arne. 2008. On the complexity of reconstructing H-free graphs from their Star Systems. Lecture Notes in Computer Science. 4957: 194-205.
  • Heggernes, Pinar; Lokshtanov, Daniel; Mihai, Rodica Georgeta; Papadopoulos, Charis. 2008. Cutwidth of split graphs, threshold graphs, and proper interval graphs. Lecture Notes in Computer Science. 5344: 218-229.
  • Lokshtanov, Daniel. 2008. Wheel-free deletion is W[2]-Hard. Lecture Notes in Computer Science. 5018: 141-147. doi: 10.1007/978-3-540-79723-4_14
  • Lokshtanov, Daniel; Mancini, Federico; Papadopoulos, Charis. 2008. Characterizing and Computing Minimal Cograph Completions. Lecture Notes in Computer Science. 5059: 147-158.
  • Lokshtanov, Daniel. 2007. On the Complexity of Computing Treelength. Lecture Notes in Computer Science. 4708: 276-287.
  • Heggernes, Pinar; Lokshtanov, Daniel. 2006. Optimal broadcast domination in polynomial time. Discrete Mathematics. 306: 3267-3280. doi: 10.1016/j.disc.2006.06.013
Rapporter/avhandlinger
  • Lokshtanov, Daniel. 2009. New methods in parameterized algorithms and complexity. 157 sider.
Bokkapitler
  • Heggernes, Pinar; van 't Hof, Pim; Lokshtanov, Daniel; Paul, Christophe. 2011. Obtaining a bipartite graph by contracting few edges. Session 4A, sider 217-228. I:
    • Chakraborty, Supratik; Kumar, Amit. 2011. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011. 480 sider. ISBN: 9783939897347.
  • Lokshtanov, Daniel; Nederlof, Jesper. 2010. Saving Space by Algebraization. -, sider 321-330. I:
    • Schulman, Leonard. 2010. STOC '10 Proceedings of the 42nd ACM symposium on Theory of computing. ACM Press. ISBN: 978-1-4503-0050-6.
  • Fellows, Michael; Rosamond, Frances; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Villanger, Yngve. 2009. Local Search: Is Brute-Force Avoidable? Raport, sider 486-491. I:
    • Boutilier, Craig. 2009. IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence. AAAI Press. 2106 sider. ISBN: 978-1-57735-426-0.

Se fullstendig oversikt over publikasjoner i CRIStin.