Items where Author is "Lokshtanov, Daniel"

Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket (2020) Approximation Schemes for Low-Rank Binary Matrix Approximation Problems ACM Transactions on Algorithms, 16 (1). pp. 1-39. ISSN 1549-6325

Fomin, Fedor V. ; Lokshtanov, Daniel ; Kolay, Sudeshna ; Panolan, Fahad ; Saurabh, Saket (2020) Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems ACM Transactions on Algorithms, 16 (2). pp. 1-37. ISSN 1549-6325

Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Saurabh, Saket ; Zehavi, Meirav (2019) Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring ACM Transactions on Algorithms, 15 (1). pp. 1-27. ISSN 1549-6325

Fomin, Fedor V. ; Gaspers, Serge ; Lokshtanov, Daniel ; Saurabh, Saket (2019) Exact Algorithms via Monotone Local Search Journal of the ACM, 66 (2). pp. 1-23. ISSN 0004-5411

Fomin, Fedor V. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav (2019) Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs Discrete & Computational Geometry, 62 (4). pp. 879-911. ISSN 0179-5376

Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Saurabh, Saket (2019) Spanning Circuits in Regular Matroids ACM Transactions on Algorithms, 15 (4). pp. 1-38. ISSN 1549-6325

Fomin, Fedor V. ; Le, Tien-Nam ; Lokshtanov, Daniel ; Saurabh, Saket ; Thomassé, Stéphan ; Zehavi, Meirav (2019) Subquadratic Kernels for Implicit 3-H itting S et and 3-S et P acking Problems ACM Transactions on Algorithms, 15 (1). pp. 1-44. ISSN 1549-6325

Lokshtanov, Daniel ; Pilipczuk, Michał ; Saurabh, Saket (2018) Below All Subsets for Minimal Connected Dominating Set SIAM Journal on Discrete Mathematics, 32 (3). pp. 2332-2345. ISSN 0895-4801

Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Saurabh, Saket (2018) Covering Vectors by Spaces: Regular Matroids SIAM Journal on Discrete Mathematics, 32 (4). pp. 2512-2565. ISSN 0895-4801

Lokshtanov, Daniel ; Misra, Pranabendu ; Panolan, Fahad ; Saurabh, Saket (2018) Deterministic Truncation of Linear Matroids ACM Transactions on Algorithms, 14 (2). pp. 1-20. ISSN 1549-6325

Fomin, Fedorr V. ; Lokshtanov, Daniel ; Saurabh, Saket (2018) Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes Journal of the ACM, 65 (2). pp. 1-44. ISSN 0004-5411

Agrawal, Akanksha ; Lokshtanov, Daniel ; Majumdar, Diptapriyo ; Mouawad, Amer E. ; Saurabh, Saket (2018) Kernelization of Cycle Packing with Relaxed Disjointness Constraints SIAM Journal on Discrete Mathematics, 32 (3). pp. 1619-1643. ISSN 0895-4801

Fomin, Fedor V. ; Lokshtanov, Daniel ; Saurabh, Saket ; Thilikos, Dimitrios M. (2018) Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors ACM Transactions on Algorithms, 14 (1). pp. 1-31. ISSN 1549-6325

Lokshtanov, Daniel ; Marx, Dániel ; Saurabh, Saket (2018) Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal ACM Transactions on Algorithms, 14 (2). pp. 1-30. ISSN 1549-6325

Lokshtanov, Daniel ; Ramanujan, M. S. ; Saurabh, Saket (2018) Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ACM Transactions on Algorithms, 14 (1). pp. 1-37. ISSN 1549-6325

Fomin, Fedor V. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav (2018) Long directed (s,t)-path: FPT algorithm Information Processing Letters, 140 . pp. 8-12. ISSN 0020-0190

Lokshtanov, Daniel ; Mouawad, Amer E. ; Panolan, Fahad ; Ramanujan, M.S. ; Saurabh, Saket (2018) Reconfiguration on sparse graphs Journal of Computer and System Sciences, 95 . pp. 122-131. ISSN 0022-0000

Agrawal, Akanksha ; Lokshtanov, Daniel ; Mouawad, Amer E. ; Saurabh, Saket (2018) Simultaneous Feedback Vertex Set: A Parameterized Perspective ACM Transactions on Computation Theory, 10 (4). pp. 1-25. ISSN 1942-3454

Lokshtanov, Daniel ; Saurabh, Saket ; Sharma, Roohani ; Zehavi, Meirav (2017) Balanced Judicious Partition is Fixed-Parameter Tractable SIAM Journal on Discrete Mathematics, 33 (4). pp. 1878-1911. ISSN 0895-4801

Chitnis, Rajesh ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Misra, Pranabendu ; Ramanujan, M.S. ; Saurabh, Saket (2017) Faster exact algorithms for some terminal set problems Journal of Computer and System Sciences, 88 . pp. 195-207. ISSN 0022-0000

Agrawal, Akanksha ; Lokshtanov, Daniel ; Misra, Pranabendu ; Saurabh, Saket ; Zehavi, Meirav (2017) Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion In: Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Jan 16-19, 2017, Rhode Island, USA.

Lokshtanov, Daniel ; Misra, Pranabendu ; Ramanujan, M. S. ; Saurabh, Saket (2017) Hitting Selected (Odd) Cycles SIAM Journal on Discrete Mathematics, 31 (3). pp. 1581-1615. ISSN 0895-4801

Adler, Isolde ; 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, 122 . pp. 815-843. ISSN 0095-8956

Kolay, Sudeshna ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket (2017) Quick but Odd Growth of Cacti Algorithmica, 79 (1). pp. 271-290. ISSN 0178-4617

Fomin, Fedor V. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket (2017) Representative Families of Product Families ACM Transactions on Algorithms, 13 (3). pp. 1-29. ISSN 1549-6325

Agrawal, Akanksha ; Lokshtanov, Daniel ; Saurabh, Saket ; Zehavi, Meirav (2017) Split Contraction: The Untold Story In: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Dagstuhl, Germany.

Giannopoulou, Archontia C. ; Jansen, Bart M. P. ; Lokshtanov, Daniel ; Saurabh, Saket (2017) Uniform Kernelization Complexity of Hitting Forbidden Minors ACM Transactions on Algorithms, 13 (3). pp. 1-35. ISSN 1549-6325

Fomin, Fedor V. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket (2016) Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms Journal of the ACM, 63 (4). pp. 1-60. ISSN 0004-5411

Fomin, Fedor V. ; Lokshtanov, Daniel ; Misra, Neeldhara ; Philip, Geevarghese ; Saurabh, Saket (2016) Hitting Forbidden Minors: Approximation and Kernelization SIAM Journal on Discrete Mathematics, 30 (1). pp. 383-410. ISSN 0895-4801

Bodlaender, Hans L. ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Penninkx, Eelko ; Saurabh, Saket ; Thilikos, Dimitrios M. (2016) (Meta) Kernelization Journal of the ACM, 63 (5). pp. 1-69. ISSN 0004-5411

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 (3). pp. 1-24. ISSN 1549-6325

Fomin, Fedor V. ; Lokshtanov, Daniel ; Pilipczuk, Michał ; Saurabh, Saket ; Wrochna, Marcin (2015) Fully polynomial-time parameterized computations for graphs and matrices of low treewidth Association for Computing Machinery.

Fomin, Fedor V. ; 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 . pp. 494-505. ISSN 0302-9743

Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Saurabh, Saket (2014) Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width SIAM Journal on Computing, 43 (5). pp. 1541-1563. ISSN 0097-5397

Lokshtanov, Daniel ; Narayanaswamy, N. S. ; Raman, Venkatesh ; Ramanujan, M. S. ; Saurabh, Saket (2014) Faster Parameterized Algorithms Using Linear Programming ACM Transactions on Algorithms, 11 (2). pp. 1-31. ISSN 1549-6325

Lokshtanov, Daniel ; Pilipczuk, Marcin ; Pilipczuk, Michal ; Saurabh, Saket (2014) Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth In: IEEE 55th Annual Symposium on Foundations of Computer Science, 18-21 Oct. 2014, Philadelphia, PA, USA.

Cygan, Marek ; Lokshtanov, Daniel ; Pilipczuk, Marcin ; Pilipczuk, Michał ; Saurabh, Saket (2014) Minimum bisection is fixed parameter tractable In: STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing, May 2014, NY, United States.

Cygan, Marek ; Lokshtanov, Daniel ; Pilipczuk, Marcin ; Pilipczuk, Michał ; Saurabh, Saket (2014) On Cutwidth Parameterized by Vertex Cover Algorithmica, 68 (4). pp. 940-953. ISSN 0178-4617

Dorn, Frederic ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Raman, Venkatesh ; Saurabh, Saket (2013) Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs Information and Computation, 233 . pp. 60-70. ISSN 0890-5401

Fomin, Fedor V. ; Lokshtanov, Daniel ; Saurabh, Saket ; Thilikos, Dimitrios M. (2013) Bidimensionality and Kernels In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, Jan 10-17, 2020, Austin, Texas.

Fomin, Fedor V. ; Grandoni, Fabrizio ; Kratsch, Dieter ; Lokshtanov, Daniel ; Saurabh, Saket (2013) Computing Optimal Steiner Trees in Polynomial Space Algorithmica, 65 (3). pp. 584-604. ISSN 0178-4617

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 . pp. 109-116. ISSN 0890-5401

Lokshtanov, Daniel ; Misra, Neeldhara ; Saurabh, Saket (2013) Imbalance is fixed parameter tractable Information Processing Letters, 113 (19-21). pp. 714-718. ISSN 0020-0190

Fomin, Fedor V. ; 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 (4). pp. 417-424. ISSN 0364-9024

Lokshtanov, Daniel ; Marx, Daniel ; Saurabh, Saket (2013) Slightly Superexponential Parameterized Problems In: ACM-SIAM Symposium on Discrete Algorithms (SODA), Jan -23-25, 2011, California, USA.

Giannopoulou, Archontia C. ; Lokshtanov, Daniel ; Saurabh, Saket ; Suchy, Ondrej (2013) Tree Deletion Set has a Polynomial Kernel (but no OPT^O(1) Approximation) Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik.

Fomin, Fedor V. ; Lokshtanov, Daniel ; Raman, Venkatesh ; Saurabh, Saket ; Rao, B.V. Raghavendra (2012) Faster algorithms for finding and counting subgraphs Journal of Computer and System Sciences, 78 (3). pp. 698-706. ISSN 0022-0000

Binkele-Raible, Daniel ; Fernau, Henning ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Saurabh, Saket ; Villanger, Yngve (2012) Kernel(s) for problems with no kernel ACM Transactions on Algorithms, 8 (4). pp. 1-19. ISSN 1549-6325

Fellows, Michael R. ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Rosamond, Frances ; Saurabh, Saket ; Villanger, Yngve (2012) Local search: Is brute-force avoidable? Journal of Computer and System Sciences, 78 (3). pp. 707-719. ISSN 0022-0000

Cygan, Marek ; Lokshtanov, Daniel ; Pilipczuk, Marcin ; Pilipczuk, Michał ; Saurabh, Saket (2012) On the Hardness of Losing Width Lecture Notes in Computer Science, 7112 . pp. 159-168. ISSN 0302-9743

Jones, Mark ; Lokshtanov, Daniel ; Ramanujan, M. S. ; Saurabh, Saket ; Suchý, Ondřej (2012) Parameterized Complexity of Directed Steiner Tree on Sparse Graphs In: Proceedings of the 21st European Symposium on Algorithms, ESA 2013, September 2-4, 2013, Sophia Antipolis, France.

Lokshtanov, Daniel ; Mnich, Matthias ; Saurabh, Saket (2011) A Linear Kernel for Planar Connected Dominating Set Theoretical Computer Science, 412 (23). pp. 2536-2543. ISSN 0304-3975

Cygan, Marek ; Fomin, Fedor V. ; Kowalik, Łukasz ; Lokshtanov, Daniel ; Marx, Dániel ; Pilipczuk, Marcin ; Pilipczuk, Michał ; Saurabh, Saket (2011) Lower bounds based on the Exponential Time Hypothesis EATCS Bulletin, 105 . pp. 41-71.

Fellows, Michael R. ; Fomin, Fedor V. ; 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 (2). pp. 143-153. ISSN 0890-5401

Fomin, Fedor V. ; Lokshtanov, Daniel ; Raman, Venkatesh ; Saurabh, Saket (2011) Subexponential algorithms for partial cover problems Information Processing Letters, 111 (16). pp. 814-818. ISSN 0020-0190

Fomin, Fedor V. ; Lokshtanov, Daniel ; Saurabh, Saket (2011) An exact algorithm for minimum distortion embedding Theoretical Computer Science, 412 (29). pp. 3530-3536. ISSN 0304-3975

Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Saurabh, Saket (2010) Intractability of Clique-Width Parameterizations SIAM Journal on Computing, 39 (5). pp. 1941-1956. ISSN 0097-5397

Fomin, Fedor V. ; Lokshtanov, Daniel ; Grandoni, Fabrizio ; Saurabh, Saket (2010) Sharp Separation and Applications to Exact and Parameterized Algorithms Lecture Notes in Computer Science, 6034 . pp. 72-83. ISSN 0302-9743

Golovach, Petr ; Heggernes, Pinar ; Kratsch, Dieter ; Lokshtanov, Daniel ; Meister, Daniel ; Saurabh, Saket (2009) Bandwidth on AT-Free Graphs Lecture Notes in Computer Science, 5878 . pp. 573-582. ISSN 0302-9743

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 (4). pp. 822-848. ISSN 1432-4350

Fellows, Michael R. ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Losievskaja, Elena ; Rosamond, Frances A. ; Saurabh, Saket (2009) Distortion Is Fixed Parameter Tractable Lecture Notes in Computer Science, 5555 . pp. 463-474. ISSN 0302-9743

Dom, Michael ; Lokshtanov, Daniel ; Saurabh, Saket (2009) Incompressibility through Colors and IDs Lecture Notes in Computer Science, 5555 . pp. 378-389. ISSN 0302-9743

Lokshtanov, Daniel ; Raman, Venkatesh ; Saurabh, Saket ; Sikdar, Somnath (2009) On the Directed Degree-Preserving Spanning Tree Problem Lecture Notes in Computer Science, 5917 . pp. 276-287. ISSN 0302-9743