vix.ing · top · new · best · stats · spec

Lokshtanov, Daniel

  1. Wordle is NP-hard
    2022/03/30 by Daniel Lokshtanov, Bernardo Subercaseaux, Lokshtanov, Daniel +1 · 5 voices
    #cs.CC
  2. (Meta) Kernelization
    2009/04/04 by Hans L. Bodlaender, Fedor V. Fomin, Bodlaender, Hans L. +9 · 7 citations
    Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation
  3. Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal
    2010/07/30 by Lokshtanov, Daniel, Marx, Dániel, Saurabh, Saket · 4 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  4. On Induced Versions of Menger's Theorem on Sparse Graphs
    2023/09/15 by Gartland, Peter, Korhonen, Tuukka, Lokshtanov, Daniel · 6 citations
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
  5. Hitting forbidden minors: Approximation and Kernelization
    2010/10/07 by Fomin, Fedor V., Lokshtanov, Daniel, Misra, Neeldhara +2 · 2 citations
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  6. Tree independence number II. Three-path-configurations
    2024/05/01 by Chudnovsky, Maria, Hajebi, Sepehr, Lokshtanov, Daniel +1 · 7 citations
    #Combinatorics (math.CO) #FOS: Mathematics
  7. Faster Parameterized Algorithms using Linear Programming
    2012/03/05 by Lokshtanov, Daniel, Narayanaswamy, N. S., Raman, Venkatesh +2 · 2 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  8. Minimum Bisection is fixed parameter tractable
    2013/11/11 by Marek Cygan, Cygan, Marek, Daniel Lokshtanov +7 · 2 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
  9. Lossy Kernelization
    2016/04/14 by Daniel Lokshtanov, Lokshtanov, Daniel, Fahad Panolan +5 · 2 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems
  10. The complexity of independent set reconfiguration on bipartite graphs
    2017/07/09 by Lokshtanov, Daniel, Mouawad, Amer E. · 2 citations
    #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  11. Approximation Schemes for Low-Rank Binary Matrix Approximation Problems
    2018/07/18 by Fomin, Fedor V., Golovach, Petr A., Lokshtanov, Daniel +2 · 2 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
  12. Randomized contractions meet lean decompositions
    2018/10/16 by Cygan, Marek, Komosa, Paweł, Lokshtanov, Daniel +4 · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  13. Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition
    2023/08/09 by Korhonen, Tuukka, Lokshtanov, Daniel · 4 citations
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
  14. An Improved Parameterized Algorithm for Treewidth
    2022/11/14 by Korhonen, Tuukka, Lokshtanov, Daniel · 3 citations
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  15. A Parameterized Approximation Scheme for Min k-Cut
    2020/04/30 by Daniel Lokshtanov, Lokshtanov, Daniel, Saket Saurabh +3 · 2 citations
    Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems
  16. b-Coloring Parameterized by Clique-Width
    2020/03/09 by Lars Jaffke, Jaffke, Lars, Paloma T. Lima +3 · 2 citations
    Computer Science · Engineering · #05C15 #05C85 #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Scheduling and Optimization Algorithms
  17. Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
    2023/05/25 by Gartland, Peter, Lokshtanov, Daniel, Masařík, Tomáš +3 · 3 citations
    #05C69 #05C85 #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2
  18. Parameterized Integer Quadratic Programming: Variables and Coefficients
    2015/11/01 by Daniel Lokshtanov, Lokshtanov, Daniel · 2 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
  19. A Constant Factor Approximation for Navigating Through Connected\n Obstacles in the Plane
    2020/11/29 by Neeraj Kumar, Kumar, Neeraj, Daniel Lokshtanov +5 · 2 citations
    Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Robotic Path Planning Algorithms
  20. Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth
    2024/02/22 by Chudnovsky, Maria, Gartland, Peter, Hajebi, Sepehr +2 · 3 citations
    #Combinatorics (math.CO) #FOS: Mathematics
  21. Tree Independence Number IV. Even-hole-free Graphs
    2024/07/12 by Maria Chudnovsky, Chudnovsky, Maria, Peter Gartland +7 · 4 citations
    Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
  22. Bidimensionality and EPTAS
    2010/05/29 by Fomin, Fedor V., Lokshtanov, Daniel, Raman, Venkatesh +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  23. Obtaining a Bipartite Graph by Contracting Few Edges
    2011/02/26 by Heggernes, Pinar, Hof, Pim van 't, Lokshtanov, Daniel +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  24. Contracting Graphs to Paths and Trees
    2011/04/19 by Heggernes, Pinar, Hof, Pim van 't, Lévêque, Benjamin +2 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  25. Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
    2013/04/16 by Fedor V. Fomin, Fomin, Fedor V., Daniel Lokshtanov +5 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization
  26. Tree Deletion Set has a Polynomial Kernel (but no OPTO(1) approximation)
    2013/09/30 by Giannopoulou, Archontia C., Lokshtanov, Daniel, Saurabh, Saket +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  27. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth
    2014/04/03 by Lokshtanov, Daniel, Pilipczuk, Marcin, Pilipczuk, Michał +1 · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  28. Uniform Kernelization Complexity of Hitting Forbidden Minors
    2015/02/13 by Archontia C. Giannopoulou, Bart M. P. Jansen, Giannopoulou, Archontia C. +5 · 1 citation
    Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory
  29. On the Threshold of Intractability
    2015/05/04 by Drange, Pål Grønås, Dregi, Markus Sortland, Lokshtanov, Daniel +1 · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Social and Information Networks (cs.SI)
  30. Lower bounds for approximation schemes for Closest String
    2015/09/18 by Marek Cygan, Cygan, Marek, Daniel Lokshtanov +7 · 1 citation
    Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  31. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering
    2016/04/20 by Fomin, Fedor V., Lokshtanov, Daniel, Marx, Dániel +3 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  32. Bidimensionality and Kernels
    2016/06/17 by Fedor V. Fomin, Daniel Lokshtanov, Fomin, Fedor V. +5 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Formal Methods in Verification #semigroups and automata theory
  33. Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk\n Graphs
    2017/04/24 by Fedor V. Fomin, Daniel Lokshtanov, Fomin, Fedor V. +7 · 1 citation
    Computer Science · #Distributed systems and fault tolerance #Advanced Graph Theory Research #Advanced Data Storage Technologies
  34. Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
    2017/04/13 by Lokshtanov, Daniel, Ramanujan, M. S., Saurabh, Saket +1 · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  35. Clustering with Local Restrictions
    2017/11/10 by Lokshtanov, Daniel, Marx, Dániel · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  36. FO Model Checking on Posets of Bounded Width
    2015/04/16 by Gajarský, Jakub, Hliněný, Petr, Lokshtanov, Daniel +4 · 1 citation
    #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
  37. Fixed-Parameter Tractability of Hedge Cut
    2024/10/23 by Fedor V. Fomin, Petr A. Golovach, Fomin, Fedor V. +7 · 3 citations
    Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Image Processing and 3D Reconstruction #Manufacturing Process and Optimization
  38. Hitting Topological Minors is FPT
    2019/04/05 by Fomin, Fedor V., Lokshtanov, Daniel, Panolan, Fahad +2 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  39. ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
    2020/03/02 by Fomin, Fedor V., Lokshtanov, Daniel, Panolan, Fahad +2 · 1 citation
    #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  40. The Parameterized Complexity of Guarding Almost Convex Polygons
    2020/03/17 by Akanksha Agrawal, Kristine V. K. Knudsen, Agrawal, Akanksha +7 · 1 citation
    Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  41. Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds
    2020/04/24 by Fomin, Fedor V., Lokshtanov, Daniel, Mihajlin, Ivan +2 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  42. Diversity in Kemeny Rank Aggregation: A Parameterized Approach
    2021/05/19 by Arrighi, Emmanuel, Fernau, Henning, Lokshtanov, Daniel +2 · 1 citation
    #Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  43. Finding large induced sparse subgraphs in C>t-free graphs in quasipolynomial time
    2020/07/21 by Gartland, Peter, Lokshtanov, Daniel, Pilipczuk, Marcin +2 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  44. Exact Algorithms via Monotone Local Search
    2015/12/05 by Fomin, Fedor V., Gaspers, Serge, Lokshtanov, Daniel +1 · 1 citation
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  45. An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
    2021/03/31 by Daniel Lokshtanov, Lokshtanov, Daniel, Pranabendu Misra +7 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  46. Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles
    2022/03/15 by Kumar, Neeraj, Lokshtanov, Daniel, Saurabh, Saket +2 · 1 citation
    #Computational Geometry (cs.CG) #FOS: Computer and information sciences
  47. Shortest Cycles With Monotone Submodular Costs
    2022/11/09 by Fomin, Fedor V., Golovach, Petr A., Korhonen, Tuukka +2 · 1 citation
    #05C38 #05C85 #68W25 #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2
  48. A Framework for Approximation Schemes on Disk Graphs
    2022/11/04 by Daniel Lokshtanov, Lokshtanov, Daniel, Fahad Panolan +7 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
  49. Meta-theorems for Parameterized Streaming Algorithms
    2023/08/03 by Daniel Lokshtanov, Lokshtanov, Daniel, Pranabendu Misra +9 · 2 citations
    Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems
  50. Tree independence number V. Walls and claws
    2025/01/24 by Chudnovsky, Maria, Codsi, Julien, Lokshtanov, Daniel +2 · 4 citations
    #05C75 (Primary) 05C40 #05C85 (Secondary) #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  51. Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor
    2022/10/26 by Lokshtanov, Daniel, Pilipczuk, Marcin, Pilipczuk, Michał +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  52. Parameterized Complexity of Fair Bisection: FPT-Approximation meets Unbreakability
    2023/08/21 by Inamdar, Tanmay, Lokshtanov, Daniel, Saurabh, Saket +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  53. Kernelization of Counting Problems
    2023/08/04 by Lokshtanov, Daniel, Misra, Pranabendu, Saurabh, Saket +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  54. Efficient Approximation of Fractional Hypertree Width
    2024/09/30 by Viktoriia Korchemna, Daniel Lokshtanov, Korchemna, Viktoriia +7 · 1 citation
    Computer Science · #Metaheuristic Optimization Algorithms Research #Advanced Data Compression Techniques #Digital Filter Design and Implementation