Surveys
Fedor Fomin, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi:
Parameterized Algorithms. Chapter in "Beyond the Worst-Case Analysis of Algorithms", 2021.
Daniel Lokshtanov:
Bidimensionality And Kernels. Encyclopedia of Algorithms, 2016.
Daniel Lokshtanov, Neeldhara Misra and Saket Saurabh:
Kernelization - Preprocessing with A Guarantee. Chapter in "The Multivariate Algorithmic Revolution and Beyond", 2012.
Daniel Lokshtanov, Dániel Marx and Saket Saurabh:
Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, 2011.
Journal Publications
2022
Daniel Lokshtanov,
Amer E. Mouawad,
Fahad Panolan and
Sebastian Siebertz:
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets.
Algorithmica. Short version in the Proceedings of IPEC 2020.
Pål G. Drange,
Markus F. Dregi,
Daniel Lokshtanov,
Blair D. Sullivan:
On the threshold of intractability.
J. Comput. Syst. Sci. Short version in the Proceedings of ESA 2015.
2021
Gabriel L. Duarte,
Hiroshi Eto,
Tesshu Hanaka,
Yasuaki Kobayashi,
Yusuke Kobayashi,
Daniel Lokshtanov,
Lehilton L. C. Pedrosa,
Rafael C. S. Schouery and
Uéverton S. Souza:
Computing the Largest Bond and the Maximum Connected Cut of a Graph.
Algorithmica. Short version in the Proceedings of IPEC 2019.
Christophe Crespelle,
Daniel Lokshtanov,
Thi Ha Duong Phan and
Eric Thierry:
Faster and enhanced inclusion-minimal cograph completion.
Discret. Appl. Math. Short version in the Proceedings of COCOA 2017.
Eduard Eiben,
Daniel Lokshtanov and
Amer E. Mouawad:
Bisection of bounded treewidth graphs by convolutions.
J. Comput. Syst. Sci. Short version in the Proceedings of ESA 2019.
Meirav Zehavi,
Fedor V. Fomin,
Daniel Lokshtanov,
Fahad Panolan and
Saket Saurabh:
ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs.
J. Comput. Geom. Short version in the Proceedings of SoCG 2020.
Marek Cygan,
Pawel Komosa,
Daniel Lokshtanov,
Marcin Pilipczuk,
Michal Pilipczuk,
Saket Saurabh and
Magnus Wahlström:
Randomized Contractions Meet Lean Decompositions.
ACM Trans. Algorithms.
Daniel Lokshtanov,
Pranabendu Misra,
Joydeep Mukherjee,
Fahad Panolan,
Geevarghese Philip and
Saket Saurabh:
2-Approximating Feedback Vertex Set in Tournaments.
ACM Trans. Algorithms. Short version in the Proceedings of SODA 2020.
Andreas Björklund,
Daniel Lokshtanov,
Saket Saurabh and
Meirav Zehavi:
Approximate Counting of k-Paths: Simpler, Deterministic, and in Polynomial Space.
ACM Trans. Algorithms. Short version in the Proceedings of ICALP 2019.
Fedor V. Fomin,
Daniel Lokshtanov,
Ivan Mihajlin,
Saket Saurabh and
Meirav Zehavi:
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds.
ACM Trans. Comput. Theory. Short version in the Proceedings of ICALP 2020.
Fedor V. Fomin,
Petr A. Golovach,
Daniel Lokshtanov,
Fahad Panolan,
Saket Saurabh and
Meirav Zehavi:
Multiplicative Parameterization Above a Guarantee.
ACM Trans. Comput. Theory. Short version in the Proceedings of ITCS 2020.
Spoorthy Gunda,
Pallavi Jain,
Daniel Lokshtanov,
Saket Saurabh and
Prafullkumar Tale:
On the Parameterized Approximability of Contraction to Classes of Chordal Graphs.
ACM Trans. Comput. Theory. Short version in the Proceedings of APPROX 2020.
2020
Aritra Banik,
Pratibha Choudhary,
Daniel Lokshtanov,
Venkatesh Raman and
Saket Saurabh:
A Polynomial Sized Kernel for Tracking Paths Problem.
Algorithmica. Short version in the Proceedings of LATIN 2018.
Fedor V. Fomin,
Daniel Lokshtanov,
Saket Saurabh and
Dimitrios M. Thilikos:
Bidimensionality and Kernels.
SIAM J. Comput. Short version in the Proceedings of SODA 2010.
Akanksha Agrawal,
Fedor V. Fomin,
Daniel Lokshtanov,
Saket Saurabh and
Prafullkumar Tale:
Path Contraction Faster than 2^n.
SIAM J. Discret. Math. Short version in the Proceedings of ICALP 2019.
Fedor V. Fomin,
Petr A. Golovach,
Daniel Lokshtanov,
Fahad Panolan,
Saket Saurabh and
Meirav Zehavi:
Going Far from Degeneracy.
SIAM J. Discret. Math. Short version in the Proceedings of ESA 2019.
Fedor V. Fomin,
Petr A. Golovach,
Daniel Lokshtanov,
Fahad Panolan and
Saket Saurabh:
Approximation Schemes for Low-rank Binary Matrix Approximation Problems.
ACM Trans. Algorithms.
Fedor V. Fomin,
Daniel Lokshtanov,
Sudeshna Kolay,
Fahad Panolan and
Saket Saurabh:
Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems.
ACM Trans. Algorithms. Short version in the Proceedings of SoCG 2016.
Daniel Lokshtanov,
Fahad Panolan,
Saket Saurabh,
Roohani Sharma and
Meirav Zehavi:
Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms.
ACM Trans. Algorithms. Short version in the Proceedings of SODA 2018.
Akanksha Agrawal,
Daniel Lokshtanov,
Pranabendu Misra,
Saket Saurabh and
Meirav Zehavi:
Polylogarithmic Approximation Algorithms for Weighted-F-deletion Problems.
ACM Trans. Algorithms. Short version in the Proceedings of APPROX-RANDOM 2018.
Jakub Gajarský,
Petr Hlinený,
Daniel Lokshtanov,
Jan Obdrzálek and
M.S. Ramanujan:
A New Perspective on FO Model Checking of Dense Graph Classes.
ACM Trans. Comput. Log. Short version in the Proceedings of LICS 2016.
2019
Gábor Bacsó,
Daniel Lokshtanov,
Dániel Marx,
Marcin Pilipczuk,
Zsolt Tuza and
Erik Jan van Leeuwen:
Subexponential-Time Algorithms for Maximum Independent Set in P_t-Free and Broom-Free Graphs.
Algorithmica.
Fedor V. Fomin,
Serge Gaspers,
Daniel Lokshtanov and
Saket Saurabh:
Exact Algorithms via Monotone Local Search.
Journal of the ACM. Short version in the Proceedings of STOC 2016.
Marek Cygan,
Daniel Lokshtanov,
Marcin Pilipczuk,
Michal Pilipczuk and
Saket Saurabh:
Minimum Bisection Is Fixed-Parameter Tractable.
SIAM Journal on Computing. Short version in the Proceedings of STOC 2014.
Fedor V. Fomin,
Petteri Kaski,
Daniel Lokshtanov,
Fahad Panolan and
Saket Saurabh:
Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree.
SIAM Journal on Discrete Math. Short version in the Proceedings of ICALP 2015
Daniel Lokshtanov and
Amer E. Mouawad:
The Complexity of Independent Set Reconfiguration on Bipartite Graphs.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2018.
Fedor V. Fomin,
Petr A. Golovach,
Daniel Lokshtanov,
Saket Saurabh and
Meirav Zehavi:
Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2018.
Akanksha Agrawal,
Daniel Lokshtanov,
Pranabendu Misra,
Saket Saurabh and
Meirav Zehavi:
Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2017.
Fedor V. Fomin,
Tien-Nam Le,
Daniel Lokshtanov,
Saket Saurabh,
Stéphan Thomassé and
Meirav Zehavi:
Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2018.
Akanksha Agrawal,
Daniel Lokshtanov,
Saket Saurabh and
Meirav Zehavi:
Split Contraction: The Untold Story.
ACM Transactions on Computation Theory. Short version in the Proceedings of STACS 2017.
2018
Fedor V. Fomin,
Daniel Lokshtanov and
Saket Saurabh:
Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes.
Journal of the ACM. Based on short versions in the Proceedings of SODA 2011 and SODA 2012.
Fedor V. Fomin,
Daniel Lokshtanov,
Fahad Panolan,
Saket Saurabh and
Meirav Zehavi:
Long directed (s, t)-path: FPT algorithm.
Information Processing Letters.
Daniel Lokshtanov,
Amer E. Mouawad,
Fahad Panolan,
M. S. Ramanujan and
Saket Saurabh:
Reconfiguration on sparse graphs.
Journal of Computer and System Sciences. Short version in the Proceedings of WADS 2015.
Daniel Lokshtanov,
Dániel Marx and
Saket Saurabh:
Slightly Superexponential Parameterized Problems.
SIAM Journal on Computing. Short version in the Proceedings of SODA 2011.
Fedor V. Fomin,
Daniel Lokshtanov,
Syed Mohammad Meesum,
Saket Saurabh and
Meirav Zehavi:
Matrix Rigidity from the Viewpoint of Parameterized Complexity.
SIAM Journal on Discrete Math. Short version in the Proceedings of STACS 2017.
Akanksha Agrawal,
Daniel Lokshtanov,
Diptapriyo Majumdar,
Amer E. Mouawad and
Saket Saurabh:
Kernelization of Cycle Packing with Relaxed Disjointness Constraints.
SIAM Journal on Discrete Math. Short version in the Proceedings of ICALP 2016.
Daniel Lokshtanov,
Michal Pilipczuk and
Saket Saurabh:
Below All Subsets for Minimal Connected Dominating Set.
SIAM Journal on Discrete Math.
Fedor V. Fomin,
Petr A. Golovach,
Daniel Lokshtanov and
Saket Saurabh:
Covering Vectors by Spaces: Regular Matroids.
SIAM Journal on Discrete Math. Short version in the Proceedings of ICALP 2017.
Daniel Lokshtanov,
Marcin Pilipczuk and
Erik Jan van Leeuwen:
Independence and Efficient Domination on P6-free Graphs.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2016.
Fedor V. Fomin,
Daniel Lokshtanov,
Saket Saurabh and
Dimitrios M. Thilikos:
Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors.
ACM Transactions on Algorithms. Based on short versions in the Proceedings of SODA 2012 and STACS 2013.
Daniel Lokshtanov,
M. S. Ramanujan and
Saket Saurabh:
Linear Time Parameterized Algorithms for Subset Feedback Vertex Set.
ACM Transactions on Algorithms. Short version in the Proceedings of ICALP 2015.
Daniel Lokshtanov,
Dániel Marx and
Saket Saurabh:
Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2011.
Daniel Lokshtanov,
Pranabendu Misra,
Fahad Panolan and
Saket Saurabh:
Deterministic Truncation of Linear Matroids.
ACM Transactions on Algorithms. Short version in the Proceedings of ICALP 2015.
Fedor V. Fomin,
Daniel Lokshtanov,
Saket Saurabh,
Michal Pilipczuk and
Marcin Wrochna:
Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2017
2017
Daniel Lokshtanov,
Marcin Pilipczuk,
Michal Pilipczuk and
Saket Saurabh:
Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth.
SIAM Journal on Computing. FOCS 2014 Special Issue.
Rajesh Chitnis,
Fedor V. Fomin,
Daniel Lokshtanov,
Pranabendu Misra,
M.S. Ramanujan and
Saket Saurabh:
Faster Exact Algorithms for Some Terminal Set Problems.
Journal of Computer and System Sciences. Short version in the Proceedings of IPEC 2013.
Isolde Adler,
Stavros G. Kolliopoulos,
Philipp K. Krause,
Daniel Lokshtanov,
Saket Saurabh and
Dimitrios M. Thilikos:
Irrelevant Vertices for the planar Disjoint Paths Problem.
Journal of Combinatorial Theory, Series B. Short version in the Proceedings of ICALP 2011.
Mark Jones,
Daniel Lokshtanov,
M.S. Ramanujan,
Saket Saurabh and
Ondej Suchý:
Parameterized Complexity of Directed Steiner Tree on Sparse Graphs.
SIAM Journal on Discrete Math. Short version in the Proceedings of ESA 2013.
Sudeshna Kolay,
Daniel Lokshtanov,
Fahad Panolan,
Saket Saurabh:
Quick but Odd Growth of Cacti.
Algorithmica. Short version in Proceedings of IPEC 2015
Daniel Lokshtanov,
Pranabendu Misra,
M. S. Ramanujan,
Saket Saurabh:
Hitting Selected (Odd) Cycles.
SIAM Journal on Discrete Math.
Archontia C. Giannopoulou,
Bart M. P. Jansen,
Daniel Lokshtanov,
Saket Saurabh:
Uniform Kernelization Complexity of Hitting Forbidden Minors.
ACM Transactions on Algorithms. Short version in the Proceedings of ICALP 2015.
Fedor V. Fomin,
Daniel Lokshtanov,
Fahad Panolan,
Saket Saurabh:
Representative Families of Product Families.
ACM Transactions on Algorithms. Short version in Proceedings of ESA 2014.
2016
Olawale Hassan,
Iyad Kanj,
Daniel Lokshtanov and
Ljubomir Perkovic:
On the Ordered List Subgraph Embedding Problems. Algorithmica. Short version in the Proceedings of IPEC 2013.
Fedor V. Fomin,
Daniel Lokshtanov and
Saket Saurabh Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms. Journal of the ACM. Short version in the Proceedings of SODA 2014.
Hans L. Bodlaender,
Fedor V. Fomin,
Daniel Lokshtanov,
Eelko Penninkx,
Saket Saurabh and
Dimitrios M. Thilikos:
(Meta) Kernelization. Journal of the ACM. Short version in the Proceedings FOCS 2009.
Hans L. Bodlaender,
Pål G. Drange,
Markus S. Dregi,
Fedor V. Fomin,
Daniel Lokshtanov and
Michal Pilipczuk:
A c^kn 5-Approximation Algorithm for Treewidth. SIAM Journal on Computing. Short version in the Proceedings of FOCS 2013.
Fedor V. Fomin,
Daniel Lokshtanov,
Neeldhara Misra,
Geevarghese Philip and
Saket Saurabh:
Hitting forbidden minors: Approximation and Kernelization. SIAM Journal on Discrete Math. Short version in the Proceedings of STACS 2011.
Archontia Giannopoulou,
Daniel Lokshtanov,
Saket Saurabh and
Ondrej Suchý:
Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation). SIAM Journal on Discrete Math. Short version in the Proceedings of FSTTCS 2014.
Marek Cygan,
Holger Dell,
Daniel Lokshtanov,
Dániel Marx,
Jesper Nederlof,
Yoshio Okamoto,
Ramamohan Paturi,
Saket Saurabh and
Magnus Wahlström:
On Problems as Hard as CNF-SAT. ACM Transactions on Algorithms. Short version in the Proceedings of CCC 2012.
2014
Michael Dom,
Daniel Lokshtanov, and
Saket Saurabh:
Kernelization Lower Bounds Through Colors and IDs. ACM Transactions on Algorithms. Short version in the proceedings of ICALP 2009.
Daniel Lokshtanov,
N.S. Narayanaswamy,
Venkatesh Raman,
M.S. Ramanujan and
Saket Saurabh:
Faster Parameterized Algorithms using Linear Programming. ACM Transactions on Algorithms.
Fedor Fomin,
Petr Golovach,
Daniel Lokshtanov and
Saket Saurabh:
Almost Optimal Lower Bounds for Problems Parameterized by Clique-width.
SIAM Journal on Computing. Short version in the Proceedings of SODA 2010.
Pinar Heggernes,
Pim van't Hof,
Benjamin Lévêque,
Daniel Lokshtanov and
Christophe Paul:
Contracting Graphs to Paths and Trees.
Algorithmica. Short version in the Proceedings of IPEC 2011.
Marek Cygan,
Daniel Lokshtanov,
Marcin Pilipczuk,
Michal Pilipczuk and
Saket Saurabh:
On Cutwidth Parameterized by Vertex Cover.
Algorithmica. Short version in the Proceedings of IPEC 2011.
Marek Cygan,
Daniel Lokshtanov,
Marcin Pilipczuk,
Michal Pilipczuk and
Saket Saurabh:
On The Hardness of Losing Width.
Theory of Computing Systems. Short version in the Proceedings of IPEC 2011.
Christine Lo,
Boyko Kakadarov,
Daniel Lokshtanov and
Christina Boucher:
SeeSite: Characterizing Relationships Between Splice Junctions and Splicing Enhancers. Trans. Comput. Biology Bioinform. Short version in the Proceedings of APBC 2014.
2013
Daniel Lokshtanov,
Neeldhara Misra and
Saket Saurabh:
Imbalance is Fixed Parameter Tractable.
Information Processing Letters. Short version in the Proceedings of COCOON 2010.
Fedor V. Fomin,
Daniel Lokshtanov,
Neeldhara Misra,
Geevarghese Philip,
Saket Saurabh:
Quadratic Upper Bounds on the Erdos-Posa Property for a Generalization of Packing and Covering Cycles.
Journal of Graph Theory.
Pinar Heggernes,
Dieter Kratsch,
Daniel Lokshtanov,
Saket Saurabh and
Venkatesh Raman:
Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing. Information and Computation. Short version in the Proceedings of SWAT 2010.
Frederic Dorn,
Fedor V. Fomin,
Daniel Lokshtanov,
Venkatesh Raman and
Saket Saurabh:
Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. Information and Computation. Short version in the Proceedings of STACS 2010.
Pinar Heggernes,
Pim van't Hof,
Daniel Lokshtanov and
Cristophe Paul:
Obtaining a Bipartite Graph by Contracting Few Edges.
SIAM Journal on Discrete Math. Short version in the Proceedings of FSTTCS 2011.
Michael R. Fellows,
Fedor V. Fomin,
Daniel Lokshtanov,
Elena Losievskaja,
Frances A. Rosamond and
Saket Saurabh:
Distortion is Fixed Parameter Tractable.
Transactions on Computation Theory. Short version in the Proceedings of ICALP 2009.
Daniel Lokshtanov and
Dániel Marx:
Clustering with Local Restrictions. Information and Computation. Short version in the Proceedings of ICALP 2011.
Fedor V. Fomin,
Fabrizio Grandoni,
Dieter Kratsch,
Daniel Lokshtanov and
Saket Saurabh:
Computing Optimal Steiner Trees in Polynomial Space. Algorithmica.
2012
Henning Fernau,
Fedor V. Fomin,
Daniel Lokshtanov,
Daniel Raible,
Saket Saurabh and
Yngve Villanger:
Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves. ACM Transactions on Algorithms. Short version in the Proceedings of STACS 2009.
Pinar Heggernes,
Pim van't Hof,
Daniel Lokshtanov and
Jesper Nederlof:
Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time. SIAM Journal on Discrete Mathematics. Short verion in the Proceedings of WG 2010.
Fedor V. Fomin,
Fabrizio Grandoni,
Daniel Lokshtanov and
Saket Saurabh:
Sharp Separation and Applications to Exact and Parameterized Algorithms. Algorithmica. Short version in the Proceedings of LATIN 2010.
Fedor V. Fomin,
Daniel Lokshtanov,
Venkatesh Raman,
B.V. Raghavendra Rao and
Saket Saurabh:
Faster Algorithms for Finding and Counting Subgraphs. Journal of Computer and System Sciences.
Michael R. Fellows,
Fedor V. Fomin,
Daniel Lokshtanov,
Frances A. Rosamond,
Saket Saurabh and
Yngve Villanger:
Local Search: Is brute-force avoidable?
Journal of Computer and System Sciences. Short Version in the Proceedings of IJCAI 09.
Fedor V. Fomin,
Petr Golovach and
Daniel Lokshtanov:
Cops and Robber game without recharging.
Theory of Computing Systems. Short Version in the Proceedings of SWAT 2010.
2011
Petr A. Golovach,
Pinar Heggernes,
Dieter Kratsch,
Daniel Lokshtanov,
Daniel Meister, and
Saket Saurabh:
Bandwidth on AT-free graphs.
Theoretical Computer Science. Short Version in the Proceedings of ISAAC 2009.
Fedor V. Fomin,
Petr A. Golovach and
Daniel Lokshtanov:
Guard games on Graphs: Keep the Intruder Out!
Theoretical Computer Science. Short Version in the Proceedings of WAOA 2009
Fedor V. 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.
Michael R. Fellows,
Fedor V.Fomin,
Daniel Lokshtanov,
Frances A. Rosamond,
Saket Saurabh,
Stefan Szeider and
Carsten 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 thr Proceedings of EC 2009.
Daniel Lokshtanov,
Matthias Mnich and
Saket Saurabh:
A Linear Kernel for Planar Connected Dominating Set. Theoretical Computer Science. TAMC09 special issue. Short version in the Proceedings of TAMC 2009.
Fedor V. Fomin,
Jan Kratochvíl,
Daniel Lokshtanov,
Federico Mancini and
Jan Arne Telle:
On the Complexity of Reconstructing H-free Graphs from their Star Systems. Journal of Graph Theory. Short version in thr 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. Short version in the Proceedings of WG 2008.
2010
Fedor V. Fomin,
Petr A. Golovach,
Daniel Lokshtanov and
Saket Saurabh:
Intractability of Clique-width Parameterizations.
SIAM Journal on Computing. Short version in the Proceedings of SODA 2009.
Daniel Lokshtanov:
On the Complexity of Computing Treelength.
Discrete Applied Math. Short version in the 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 the Proceedings of FAW 2008.
2009
Michael R. Fellows,
Daniel Lokshtanov,
Neeldhara Misra,
Matthias Mnich,
Frances A. Rosamond and
Saket 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.
2006
Pinar Heggernes and
Daniel Lokshtanov:
Optimal broadcast domination of arbitrary graphs in polynomial time.
Discrete Mathematics. Short version in the Proceedings of WG 2005.
Conference Proceedings
(that do not have a journal version)
2022
Sayan Bandyapadhyay,
William Lochet,
Daniel Lokshtanov,
Saket Saurabh and
Jie Xue:
True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs.
Proceedings of the International Symposium on Computational Geometry (SoCG 2022).
Neeraj Kumar,
Daniel Lokshtanov,
Saket Saurabh,
Subhash Suri and
Jie Xue:
Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles.
Proceedings of the International Symposium on Computational Geometry (SoCG 2022).
Daniel Lokshtanov and
Bernardo Subercaseaux:
Wordle Is NP-Hard.
Proceedings of the International Conference on Fun with Algorithms (FUN 2022).
Daniel Lokshtanov,
Fahad Panolan and
M. S. Ramanujan:
Backdoor Sets on Nowhere Dense SAT.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2022).
Sushmita Gupta,
Pallavi Jain,
Daniel Lokshtanov,
Sanjukta Roy and
Saket Saurabh:
Gehrlein Stable Committee with Multi-modal Preferences.
Proceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT 2022).
Akanksha Agrawal,
Lawqueen Kanesh,
Daniel Lokshtanov,
Fahad Panolan,
M. S. Ramanujan,
Saket Saurabh and
Meirav Zehavi:
Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2022).
Daniel Lokshtanov,
Fahad Panolan,
Saket Saurabh,
Jie Xue and
Meirav Zehavi:
Subexponential Parameterized Algorithms on Disk Graphs.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2022).
Sayan Bandyapadhyay,
William Lochet,
Daniel Lokshtanov,
Saket Saurabh and
Jie Xue:
Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2022).
Daniel Lokshtanov,
Marcin Pilipczuk,
Michal Pilipczuk and
Saket Saurabh:
Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor.
Proceedings of the ACM Symposium on Theory of Computing (STOC 2022).
2021
Daniel Lokshtanov,
Subhash Suri and
Jie Xue:
Efficient Algorithms for Least Square Piecewise Polynomial Regression.
Proceedings of the European Symposium on Algorithms (ESA 2021).
Daniel Lokshtanov,
Saket Saurabh,
Subhash Suri and
Jie Xue:
An ETH-Tight Algorithm for Multi-Team Formation.
Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021).
Daniel Lokshtanov,
Vaishali Surianarayanan:
Dominating Set in Weakly Closed Graphs is Fixed Parameter Tractable.
Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021).
Emmanuel Arrighi,
Henning Fernau,
Daniel Lokshtanov,
Mateus de Oliveira Oliveira and
Petra Wolf:
Diversity in Kemeny Rank Aggregation: A Parameterized Approach.
Proceedings of the International Joint Conferences on Artificial Intelligence Organization (IJCAI 2021).
Peter Gartland,
Daniel Lokshtanov,
Marcin Pilipczuk,
Michał Pilipczuk and
Paweł Rzążewski:
Finding large induced sparse subgraphs in C>t-free graphs in quasipolynomial time.
Proceedings of the ACM Symposium on Theory of Computing (STOC 2021).
Lars Jaffke,
Paloma de Lima,
Daniel Lokshtanov:
b-Coloring Parameterized by Clique-Width.:
Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2021).
William Lochet,
Daniel Lokshtanov,
Saket Saurabh,
Meirav Zehavi:
Exploiting Dense Structures in Parameterized Complexity.
Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2021).
Daniel Lokshtanov,
Saket Saurabh and
Meirav Zehavi:
Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).
Neeraj Kumar,
Daniel Lokshtanov,
Saket Saurabh and
Subhash Suri:
A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).
Daniel Lokshtanov,
Pranabendu Misra,
M. S. Ramanujan,
Saket Saurabh and
Meirav Zehavi:
FPT Approximation for FPT Problems.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).
2020
Pratibha Choudhary,
Daniel Lokshtanov,
Lawqueen Kanesh,
Fahad Panolan and
Saket Saurabh:
Parameterized Complexity of Feedback Vertex Sets on Hypergraphs.
Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020).
Daniel Lokshtanov,
Saket Saurabh and
Vaishali Surianarayanan:
A Parameterized Approximation Scheme for Min k-Cut.
Proceedings of the Symposium on Foundations of Computer Science (FOCS 2020)
Peter Gartland and
Daniel Lokshtanov:
Independent Set on Pk-Free Graphs in Quasi-Polynomial Time.
Proceedings of the Symposium on Foundations of Computer Science (FOCS 2020)
Daniel Lokshtanov,
Chinmay Sonar,
Subhash Suri and
Jie Xue:
Fair Covering of Points by Balls.
Proceedings of the Canadian Conference on Computational Geometry (CCCG 2020).
Daniel Lokshtanov,
Pranabendu Misra,
Fahad Panolan,
Geevarghese Philip,
Saket Saurabh:
A (2 + ε)-factor Approximation Algorithm for Split Vertex Deletion.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2020).
Jean R.S. Blair,
Pinar Heggernes,
Paloma T. Lima and
Daniel Lokshtanov:
On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number.
Proceedings of Latin American Theoretical Informatics Symposium (LATIN 2020).
Eduard Eiben and
Daniel Lokshtanov:
Removing Connected Obstacles in the Plane is FPT.
Proceedings of the International Symposium on Computational Geometry (SoCG 2020).
Akanksha Agrawal,
Kristine Knudsen,
Daniel Lokshtanov,
Saket Saurabh, and
Meirav Zehavi:
The Parameterized Complexity of Guarding Almost Convex Polygons.
Proceedings of the International Symposium on Computational Geometry (SoCG 2020).
Daniel Lokshtanov,
Pranabendu Misra,
Michał Pilipczuk,
Saket Saurabh, and
Meirav Zehavi:
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths.
Proceedings of the ACM Symposium on Theory of Computing (STOC 2020).
Fedor Fomin,
Daniel Lokshtanov,
Fahad Panolan,
Saket Saurabh and
Meirav Zehavi:
Hitting Topological Minors is FPT.
Proceedings of the ACM Symposium on Theory of Computing (STOC 2020).
William Lochet,
Daniel Lokshtanov,
Pranabendu Misra,
Saket Saurabh,
Roohani Sharma and
Meirav Zehavi:
Fault Tolerant Subgraphs with Applications in Kernelization.
Proceedings of Innovations in Theoretical Computer Science (ITCS 2020).
Fedor Fomin,
Daniel Lokshtanov,
Saket Saurabh and
Meirav Zehavi:
Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2020).
M. S. Ramanujan,
Daniel Lokshtanov,
Saket Saurabh and
Meirav Zehavi:
Parameterized Complexity and Approximability of Directed Odd Cycle Transversal.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2020).
2019
Fedor Fomin,
Daniel Lokshtanov,
Fahad Panolan,
Saket Saurabh and
Meirav Zehavi:
Decomposition of Map Graphs with Applications.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2019).
Fedor Fomin,
Petr Golovach,
Daniel Lokshtanov,
Saket Saurabh and
Meirav Zehavi:
Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2019).
Daniel Lokshtanov,
Ramanujan M. Sridharan,
Saket Saurabh,
Roohani Sharma and
Meirav Zehavi:
Wannabe Bounded Treewidth Graphs Admit a Polynomial Kernel for DFVS.
Proceedings of Algorithms and Data Structures Symposium (WADS 2019).
2018
David Eppstein and
Daniel Lokshtanov:
The Parameterized Complexity of Finding Point Sets with Hereditary Properties.
Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2018).
Daniel Lokshtanov,
Mateus de Oliveira Oliveira and
Saket Saurabh:
A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem.
Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2018).
Timothy Carpenter,
Fedor Fomin,
Daniel Lokshtanov,
Saket Saurabh and
Anastasios Sidiropoulos:
Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces.
Proceedings of the Symposium on Computational Geometry (SoCG 2018).
Daniel Lokshtanov,
M.S. Ramanujan,
Saket Saurabh and Meirav Zehavi:
Reducing CMSO Model Checking to Highly Connected Graphs.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2018).
Akanksha Agrawal,
Pallavi Jain,
Lawqueen Kanesh,
Daniel Lokshtanov and
Saket Saurabh:
Conflict Free Feedback Vertex Set: A Parameterized Dichotomy.
Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS 2018).
Daniel Lokshtanov,
Pranabendu Misra,
Fahad Panolan,
Saket Saurabh and
Meirav Zehavi:
Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity.
Proceedings of Innovations in Theoretical Computer Science (ITCS 2018).
Akanksha Agrawal,
Daniel Lokshtanov,
Pranabendu Misra,
Saket Saurabh and
Meirav Zehavi:
Erdös-Pósa Property of Obstructions to Interval Graphs.
Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2018).
Daniel Lokshtanov,
M. S. Ramanujan and
Saket Saurabh:
When Recursion is Better than Iteration: A Linear-Time Algorithm for Acyclicity with Few Error Vertices.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
Daniel Lokshtanov,
Ivan Mikhailin,
Ramamohan Paturi and
Pavel Pudlak:
Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
2017
Akanksha Agrawal,
R. Krithika,
Daniel Lokshtanov,
Amer E.
Mouawad and
M. S. Ramanujan:
On the Parameterized Complexity of Simultaneous Deletion Problems.
Proceedings of Foundations of Software Technology and Theoretical Computer Science(FSTTCS 2017).
Daniel Lokshtanov,
Saket Saurabh,
Roohani Sharma and
Meirav Zehavi:
Balanced Judicious Bipartition is FPT.
Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017).
Daniel Lokshtanov,
M.S. Ramanujan and
Saket Saurabh:
A Linear-Time Parameterized Algorithm for Node Unique Label Cover.
Proceedings of European Symposium on Algorithms (ESA 2017).
Akanksha Agrawal,
Daniel Lokshtanov and
Amer Mouawad:
Critical node cut parameterized by treewidth and solution size is W[1]-hard.
Proceedings of Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017).
Daniel Lokshtanov,
Amer E. Mouawad,
Saket Saurabh and
Meirav Zehavi:
Packing Cycles Faster Than Erdos-Pósa.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2017).
Fedor V. Fomin,
Daniel Lokshtanov,
Fahad Panolan,
Saket Saurabh and
Meirav Zehavi:
Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2017).
Daniel Lokshtanov,
Fahad Panolan,
M.S. Ramanujan and
Saket Saurabh:
Lossy Kernelization.
Proceedings of the ACM Symposium on the Theory of Computing (STOC 2017).
Fedor V. Fomin,
Petr A. Golovach,
Daniel Lokshtanov and
Saket Saurabh:
Spanning Circuits in Regular Matroids.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).
Daniel Lokshtanov,
Ramamohan Paturi,
Suguru Tamaki,
R. Ryan Williams and
Huacheng Yu:
Beating Brute Force for Systems of Polynomial Equations over Finite Fields.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).
2016
Mithilesh Kumar and
Daniel Lokshtanov:
Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments.
Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016).
Mithilesh Kumar and
Daniel Lokshtanov:
A 2lk Kernel for l-Component Order Connectivity. Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2016).
Fedor V. Fomin,
D. Lokshtanov,
Dániel Marx,
Marcin Pilipczuk,
Michal Pilipczuk and
Saket Saurabh:
Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. Proceedings of the Symposium on Foundations of Computer Science (FOCS 2016).
Marek Cygan,
Daniel Lokshtanov,
Marcin Pilipczuk,
Michal Pilipczuk and
Saket Saurabh:
Lower bounds for Approximation Schemes for Closest String. Proceedings of the Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016).
Akanksha Agrawal,
Daniel Lokshtanov,
Amer E. Mouawad and
Saket Saurabh:
Simultaneous Feedback Vertex Set: A Parameterized Perspective. Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2016).
Mithilesh Kumar and
Daniel Lokshtanov:
Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments. Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2016).
Pål G. Drange,
Markus S. Dregi,
Fedor V. Fomin,
Stephan Kreutzer,
Daniel Lokshtanov,
Marcin Pilipczuk,
Michal Pilipczuk,
Felix Reidl,
Fernando S. Villaamil,
Saket Saurabh,
Sebastian Siebertz and
Somnath Sikdar.
Kernelization and Sparseness: the case of Dominating Set. Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2016).
Akanksha Agrawal,
Sudeshna Kolay,
Daniel Lokshtanov, and
Saket Saurabh:
A Faster FPT Algorithm and a Smaller Kernel for Block Graph
Vertex Deletion. Proceedings of the Latin American Theoretical Informatics Symposium (LATIN 2016).
2015
Jakub Gajarský,
Petr Hlinený,
Daniel Lokshtanov,
Jan Obdržálek,
Sebastian Ordyniak,
M.S. Ramanujan and
Saket Saurabh:
FO Model Checking on Posets of Bounded Width. Proceedings of Symposium on Foundations of Computer Science (FOCS 2015).
Christina Boucher,
Christine Lo and
Daniel Lokshtanov:
Consensus Patterns (Probably) Has no EPTAS. Proceedings of the European Symposium on Algorithms (ESA 2015).
Best ESA Paper Award.
Ariel Gabizon,
Daniel Lokshtanov and
Michal Pilipczuk:
Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints. Proceedings of the European Symposium on Algorithms (ESA 2015).
Fedor V. Fomin,
Daniel Lokshtanov,
Neeldhara Misra,
M.S. Ramanujan and
Saket Saurabh:
Solving d-SAT via Backdoors to Small Treewidth. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).
2014
Daniel Lokshtanov,
Saket Saurabh and
Ondrej Suchý:
Solving Multicut Faster than 2^n. Proceedings of European Symposium on Algorithms (ESA 2014).
Markus S. Dregi and
Daniel Lokshtanov:
Parameterized Complexity of Bandwidth on Trees. Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP 2014).
Bart Jansen,
Daniel Lokshtanov and
Saket Saurabh A Near-Optimal Planarization Algorithm. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).
Daniel Lokshtanov,
Martin Vatshelle and
Yngve Villanger Independent Set in P5-Free Graphs in Polynomial Time. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).
2013
Daniel Lokshtanov,
Neeldhara Misra, and
Saket Saurabh:
On the hardness of eliminating small induced subgraphs by contracting edges. Proceedings of International Symposium on Parameterized and Exact Computation (IPEC 2013).
Hans L. Bodlaender,
Paul S. Bonsma and
Daniel Lokshtanov:
The Fine Details of Fast Dynamic Programming over Tree Decompositions. Proceedings of International Symposium on Parameterized and Exact Computation (IPEC 2013).
Daniel Lokshtanov,
Neeldhara Misra,
Geevarghese Philip,
M.S. Ramanujan and
Saket Saurabh:
Hardness of r-dominating set on graphs of diameter (r + 1). Proceedings of International Symposium on Parameterized and Exact Computation (IPEC 2013).
Ravi Kumar,
Daniel Lokshtanov,
Sergei Vassilvitskii and
Andrea Vattani:
Near-Optimal Bounds for Cross-Validation via Loss Stability. Proceedings of International Conference on Machine Learning (ICML 2013).
2012
Daniel Lokshtanov,
Saket Saurabh and
Magnus Wahlström:
Subexponential Parameterized Odd Cycle Transversal on Planar Graphs. Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012).
Fedor V. Fomin,
Daniel Lokshtanov,
Neeldhara Misra and
Saket Saurabh:
Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. Proceedings of Symposium on Foundations of Computer Science (FOCS 2012).
Daniel Lokshtanov and
M.S. Ramanujan:
Parameterized Tractability of Multiway Cut with Parity Constraints. Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP 2012).
2011
Daniel Lokshtanov,
Matthias Mnich and
Saket Saurabh:
Planar k-Path in Subexponential Time and Polynomial Space. Proceedings of Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011).
Paul S. Bonsma and
Daniel Lokshtanov:
Feedback Vertex Set in Mixed Graps. Proceedings of the Algorithms and Data Structures Symposium (WADS 2011).
2010
Michael R. Fellows,
Bart M. P. Jansen,
Daniel Lokshtanov,
Frances A Rosamond and
Saket Saurabh:
Determining the Winner of a Dodgson Election is Hard. Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010).
Henning Fernau,
Fedor V. Fomin,
Daniel Lokshtanov,
Matthias Mnich,
Geevarghese Philip and
Saket Saurabh:
Ranking and Drawing in Subexponential Time. Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA 2010).
Pinar Heggernes,
Daniel Lokshtanov,
Jesper Nederlof,
Christophe Paul and
Jan Arne Telle:
Generalized graph clustering: recognizing (p,q)-cluster graphs. Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science (WG 2010).
Fedor V. 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)
Daniel Lokshtanov and
Jesper Nederlof:
Saving Space by Algebraization. Proceedings of ACM Symposium on Theory of Computing (STOC 2010).
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)
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)
2008
Michael R. Fellows,
Daniel Lokshtanov,
Neeldhara Misra,
Frances A. Rosamond and
Saket 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)
2005
Daniel Lokshtanov and
Christian Sloper:
Fixed Parameter Set Splitting, Obtaining a Linear Kernel and Improving Running Time. Proceedings of Algorithms and Complexity in Durham (ACID 2005).
Thesis
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.
Supervised by Pinar Heggernes. June 2006.