|
Name: What: Where: E-mail: Phone: Fax: Mail Address: |
Daniel Lokshtanov Postdoc at UCSD CS Building Room 4226, San Diego daniello [4t] ii [d0t] uib [d0t] no +1 858-534-5172 +1 858-534-7029 Department of Computer Science and Engineering University of California, San Diego La Jolla, CA 92093-0404 |
| JOB OPENING; Starting September 2012 I will have a 4-year Phd. student position and a 2-year PostDoc position availiable as a part of the BeHard project on kernelization at the University of Bergen (Norway). Conctact me by e-mail if you are interested and have an excellent background in Combinatorics, Algorithms, Kernelization and/or Complexity Theory. |
| I enjoy hiking, skiing, fantasy, sci-fi, tennis, pants, cognac, parmesan and soccer. A couple (now way more than a couple) years ago I starred in Fana school theatre. I'm also the coordinator of the Norwegian high school Informatics Olympiad, NIO. Most of the reasearch I do is in algorithmic graph theory. My Phd. is in parameterized algorithms and complexity. Check out the Parameterized Complexity Wiki. |
|
Fedor Fomin, Daniel Lokshtanov, Venkatesh Raman and Saket Saurabh: Subexponential Algorithms for Partial Cover Problems. Information Processing Letters. Short version in the proceedings of FSTTCS 2009. M.Fellows, F.Fomin, D.Lokshtanov, F. Rosamond, S. Saurabh, S. Szeider and C. Thomassen: On the Complexity of Some Colorful Problems Parameterized by Treewidth. Information and Computation. Short version in proceedings of COCOA 2007. Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh: An Exact Algorithm for Minimum Distortion Embedding Theoretical Computer Science. Short version in the proceedings of WG 2009. Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh and Somnath Sikdar: On the Directed Degree-Preserving Spanning Tree Problem Journal of Discrete Optimization. Short version in the proceedings of IWPEC 2009. Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, and Ilan Newman: Treewidth governs the complexity of target set selection. Journal of Discrete Optimization. Short version in proceedings of EC 2009 Daniel Lokshtanov, Matthias Mnich and Saket Saurabh: Linear Kernel for Planar Connected Dominating Set. Theoretical Computer Science. To appear. TAMC09 special issue. Short version in proceedings of TAMC 2009. F.Fomin, J.Kratochvíl, D.Lokshtanov, F.Mancini and J.A.Telle: On the Complexity of Reconstructing H-free Graphs from their Star Systems. Journal of Graph Theory. To appear. Short version in proceedings of LATIN 2008. Pinar Heggernes, Daniel Lokshtanov, Rodica Mihai and Charis Papadopoulos: Cutwidth of split graphs and threshold graphs. SIAM Journal on Discrete Mathematics. To appear. Short version in proceedings of WG 2008. Fedor Fomin, Petr Golovach, Daniel Lokshtanov and Saket Saurabh: Intractability of Clique-width Parameterizations. SIAM Journal on Computing. To appear. Short version in proceedings of SODA 2009. Daniel Lokshtanov: On the Complexity of Computing Treelength. Discrete Applied Math. Short version in proceedings of MFCS 2007. Daniel Lokshtanov, Federico Mancini and Charis Papadopoulos: Computing and extracting minimal cograph completions in linear time. Discrete Applied Math. Short version in proceedings of FAW 2008. M.Fellows, D.Lokshtanov, N.Misra, M.Mnich, F.Rosamond and S.Saurabh: The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number. Theory Of Computing Systems. CIE07 special issue. Daniel Lokshtanov: Finding the longest isometric cycle in a graph. Discrete Applied Math. WLAB05 special issue. Pinar Heggernes and Daniel Lokshtanov: Optimal broadcast domination of arbitrary graphs in polynomial time. Discrete Mathematics. Short version in proceedings of WG 2005. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh and Dimitrios M. Thilikos: Linear Kernels for (Connected) Dominating Set on H-minor-free graphs. To appear in the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2012). Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh: Bidimensionality and Geometric Graphs. To appear in the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2012). Pinar Heggernes, Pim van't Hof, Daniel Lokshtanov and Cristophe Paul: Obtaining a Bipartite Graph by Contracting Few Edges. To appear in the proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). P.Heggernes, P.van't Hof, B.Leveque, D.Lokshtanov and C.Paul: Contracting Graphs to Paths and Trees. Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2011). M.Cygan, D.Lokshtanov, M.Pilipczuk, M.Pilipczuk and S.Saurabh: On Cutwidth Parameterized by Vertex Cover. Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2011). M.Cygan, D.Lokshtanov, M.Pilipczuk, M.Pilipczuk and S.Saurabh: On The Hardness of Losing Width. Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2011). Daniel Lokshtanov, Matthias Mnich and Saket Saurabh: Planar k-Path in Subexponential Time and Polynomial Space. To appear in the proceedings of Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011). I.Adler, S.G.Kolliopoulos, P.K.Krause, D.Lokshtanov, S.Saurabh and D.Thilikos: Tight Bounds for Linkages in Planar Graphs. Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP 2011). Daniel Lokshtanov and Dániel Marx: Clustering with Local Restrictions. Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP 2011). Paul Bonsma and Daniel Lokshtanov: Feedback Vertex Set in Mixed Graps. Proceedings of the Algorithms and Data Structures Symposium (WADS 2011). F.V.Fomin, D.Lokshtanov, N.Misra, G.Philip and S.Saurabh: Hitting forbidden minors: Approximation and Kernelization Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2011). Also on arXiv. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman and Saket Saurabh: Bidimensionality and EPTAS. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2011). Also on arXiv. Daniel Lokshtanov, Dániel Marx and Saket Saurabh: Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2011). Also on arXiv. Daniel Lokshtanov, Dániel Marx and Saket Saurabh: Slightly Superexponential Parameterized Problems. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2011). M.Fellows, B.Jansen, D.Lokshtanov, F.Rosamond and S.Saurabh: Determining the Winner of a Dodgson Election is Hard. Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). H.Fernau, F.V.Fomin, D.Lokshtanov, M. Mnich, G.Philip and S.Saurabh: Ranking and Drawing in Subexponential Time. Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA 2010). P.Heggernes, D.Lokshtanov, J.Nederlof, C.Paul and J.A.Telle: Generalized graph clustering: recognizing (p,q)-cluster graphs Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science (WG 2010). Pinar Heggernes, Pim van't Hof, Daniel Lokshtanov and Jesper Nederlof: Computing the cutwidth of bipartite permutation graphs in linear time Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science (WG 2010). Daniel Lokshtanov, Neeldhara Misra and Saket Saurabh: Imbalance is Fixed Parameter Tractable. Proceedings of International Computing and Combinatorics Conference (COCOON 2010) Fedor Fomin, Daniel Lokshtanov, Venkatesh Raman and Saket Saurabh: Fast Local Search Algorithm for Weighted Feedback Arc Set in Tournaments. Proceedings of the Conference on Artificial Intelligence (AAAI 2010) P.Heggernes, D.Kratsch, D.Lokshtanov, S. Saurabh and V.Raman: Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing. Proceedings of Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010) Fedor V. Fomin, Petr Golovach and Daniel Lokshtanov: Cops and Robber game without recharging. Proceedings of Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010) Daniel Lokshtanov and Jesper Nederlof: Saving Space by Algebraization. Proceedings of ACM Symposium on Theory of Computing (STOC 2010). F. Dorn,F. Fomin, D. Lokshtanov, V. Raman and S. Saurabh: Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. Proceedings of International Symposium on Theoretical Aspects of Computer Science (STACS 2010). Fedor Fomin, Fabrizio Grandoni, Daniel Lokshtanov and Saket Saurabh: Sharp Separation and Applications to Exact and Parameterized Algorithms Proceedings of Latin American Theoretical Informatics Symposium (LATIN 2010). Fedor Fomin, Daniel Lokshtanov, Saket Saurabh and Dimitrios M. Thilikos: Bidimensionality and Kernels Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). Fedor Fomin, Petr Golovach, Daniel Lokshtanov and Saket Saurabh: Algorithmic Lower Bounds for Problems Parameterized by Clique-width Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). P.Golovach, P.Heggernes, D.Kratsch, D.Lokshtanov, D.Meister, and S.Saurabh: Bandwidth on AT-free graphs Proceedings of the International Symposium on Algorithms and Computation (ISAAC 2009). Fedor V. Fomin, Petr Golovach and Daniel Lokshtanov: Guard games on Graphs: Keep the Intruder Out! Proceedings of Workshop on Approximation and Online Algorithms (WAOA 2009) Daniel Lokshtanov and Saket Saurabh: Even Faster Algorithm for Set Splitting! Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC 2009) Hans L. Bodlaender, Daniel Lokshtanov and Eelko Penninkx: Planar Capacitated Dominating Set is W[1]-hard. Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC 2009) H.L.Bodlaender, F.V.Fomin, D.Lokshtanov, E.Penninkx, S.Saurabh and D.M.Thilikos: (Meta) Kernelization. Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS 2009). Daniel Lokshtanov, Saket Saurabh and Somnath Sikdar: Simpler Parameterized Algorithm for OCT Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA09) Noga Alon, Daniel Lokshtanov, and Saket Saurabh: Fast FAST. Proceedings of the International Colloquium on Automata, Languages and Programming, Track A (ICALP09) M.Fellows, F.Fomin, D.Lokshtanov, E.Losievskaja, F.Rosamond and S.Saurabh: Distortion is Fixed Parameter Tractable. Proceedings of the International Colloquium on Automata, Languages and Programming, Track A (ICALP09) Michael Dom, Daniel Lokshtanov, and Saket Saurabh: Incompressibility through Colors and IDs. Proceedings of the International Colloquium on Automata, Languages and Programming, Track A (ICALP09) M. Fellows, F. V. Fomin, D.Lokshtanov, F. A. Rosamond, S. Saurabh and Y. Villanger: Local Search: Is brute-force avoidable? To appear in the proceedings of the Joint Conference on Artificial Intelligence (IJCAI-09) H.Fernau, F.Fomin, D.Lokshtanov, D.Raible, S.Saurabh and Y.Villanger: Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves. Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009) M.Fellows, D.Lokshtanov, N.Misra, F. Rosamond and S. Saurabh: Graph Layout problems Parameterized by Vertex Cover. Proceedings of the International Symposium on Algorithms and Computation (ISAAC 2008). Michael Dom, Daniel Lokshtanov, Saket Saurabh and Yngve Villanger: Capacitated Domination and Covering: A Parameterized Perspective. Proceedings of International Workshop on Exact and Parameterized Computation (IWPEC 2008) Daniel Lokshtanov: Wheel-free deletion is W[2]-Hard. Proceedings of International Workshop on Exact and Parameterized Computation (IWPEC 2008) Daniel Lokshtanov and Christian Sloper: Fixed Parameter Set Splitting, Obtaining a Linear Kernel and Improving Running Time. Proceedings of ACID 2005. F.V.Fomin and Daniel Lokshtanov, V.Raman, B.V.R.Rao and S.Saurabh Faster Algorithms for Finding and Counting Subgraphs. On Arxiv. Daniel Lokshtanov: Phd Thesis, New Methods in Parameterized Algorithms and Complexity. Supervised by Pinar Heggernes. Submitted April 2009, Defended June 2009. Daniel Lokshtanov: Master Thesis, Broadcast Domination. June 2006.
|
