Daniel Lokshtanov

From MaRDI portal
Person:270004

Available identifiers

zbMath Open lokshtanov.danielWikidataQ102367011 ScholiaQ102367011MaRDI QIDQ270004

List of research outcomes

PublicationDate of PublicationType
The parameterized complexity of guarding almost convex polygons2024-02-09Paper
https://portal.mardi4nfdi.de/entity/Q61870412024-02-05Paper
An ETH-tight algorithm for bidirected Steiner connectivity2024-01-16Paper
https://portal.mardi4nfdi.de/entity/Q61472602024-01-15Paper
https://portal.mardi4nfdi.de/entity/Q61472612024-01-15Paper
https://portal.mardi4nfdi.de/entity/Q61473022024-01-15Paper
Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor2023-12-08Paper
Finding large induced sparse subgraphs in c >t -free graphs in quasipolynomial time2023-11-14Paper
https://portal.mardi4nfdi.de/entity/Q60896712023-11-13Paper
The Parameterized Complexity of Guarding Almost Convex Polygons.2023-11-02Paper
Removing Connected Obstacles in the Plane is FPT2023-11-02Paper
ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs2023-11-02Paper
On the Parameterized Approximability of Contraction to Classes of Chordal Graphs2023-10-31Paper
Polynomial Kernel for Interval Vertex Deletion2023-10-23Paper
Erdős–Pósa property of obstructions to interval graphs2023-10-09Paper
On Induced Versions of Menger's Theorem on Sparse Graphs2023-09-15Paper
Lower Bound for Independence Covering in $C_4$-Free Graphs2023-08-29Paper
Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition2023-08-09Paper
Gehrlein stable committee with multi-modal preferences2023-07-28Paper
Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems2023-04-26Paper
The chromatic number of squares of random graphs2023-04-19Paper
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering2023-04-04Paper
Computing the largest bond of a graph2023-02-03Paper
Parameterization Above a Multiplicative Guarantee2023-02-03Paper
https://portal.mardi4nfdi.de/entity/Q58757482023-02-03Paper
On the maximum number of edges in chordal graphs of bounded degree and matching number2022-12-08Paper
Highly unbreakable graph with a fixed excluded minor are almost rigid2022-10-26Paper
Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths2022-10-19Paper
On the maximum number of edges in chordal graphs of bounded degree and matching number2022-10-13Paper
Multiplicative Parameterization Above a Guarantee2022-09-24Paper
Path Contraction Faster Than 2^n2022-07-21Paper
Approximate Counting of k-Paths: Deterministic and in Polynomial Space2022-07-21Paper
https://portal.mardi4nfdi.de/entity/Q50912162022-07-21Paper
Decomposition of Map Graphs with Applications.2022-07-21Paper
https://portal.mardi4nfdi.de/entity/Q50923612022-07-21Paper
https://portal.mardi4nfdi.de/entity/Q50776472022-05-18Paper
https://portal.mardi4nfdi.de/entity/Q50757842022-05-11Paper
https://portal.mardi4nfdi.de/entity/Q50757902022-05-11Paper
On the Parameterized Approximability of Contraction to Classes of Chordal Graphs2022-03-29Paper
On the parameterized complexity of reconfiguration of connected dominating sets2022-03-25Paper
Computation of Hadwiger Number and Related Contraction Problems2022-03-22Paper
2-Approximating Feedback Vertex Set in Tournaments2022-02-16Paper
Approximate Counting of k -Paths: Simpler, Deterministic, and in Polynomial Space2022-02-16Paper
Randomized Contractions Meet Lean Decompositions2022-02-08Paper
Parameterized Algorithms2022-02-04Paper
On the threshold of intractability2021-11-25Paper
https://portal.mardi4nfdi.de/entity/Q50051552021-08-04Paper
The Parameterized Complexity of Finding Point Sets with Hereditary Properties2021-08-04Paper
https://portal.mardi4nfdi.de/entity/Q50094892021-08-04Paper
https://portal.mardi4nfdi.de/entity/Q50094912021-08-04Paper
https://portal.mardi4nfdi.de/entity/Q50027952021-07-28Paper
Reducing CMSO model checking to highly connected graphs2021-07-28Paper
https://portal.mardi4nfdi.de/entity/Q49932962021-06-15Paper
Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms2021-05-03Paper
Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems2021-05-03Paper
Computing the largest bond and the maximum connected cut of a graph2021-04-19Paper
Bisection of bounded treewidth graphs by convolutions2021-04-14Paper
2-Approximating Feedback Vertex Set in Tournaments2021-02-02Paper
Parameterized Complexity and Approximability of Directed Odd Cycle Transversal2021-02-02Paper
Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs2021-02-02Paper
An exponential time parameterized algorithm for planar disjoint paths2021-01-19Paper
Hitting topological minors is FPT2021-01-19Paper
Bidimensionality and Kernels2021-01-13Paper
https://portal.mardi4nfdi.de/entity/Q51362982020-11-25Paper
Balanced Judicious Bipartition is Fixed-Parameter Tractable2020-11-25Paper
Faster and enhanced inclusion-minimal cograph completion2020-11-02Paper
Going Far from Degeneracy2020-10-29Paper
A New Perspective on FO Model Checking of Dense Graph Classes2020-09-11Paper
https://portal.mardi4nfdi.de/entity/Q51157892020-08-18Paper
Erdös-Pósa Property of Obstructions to Interval Graphs2020-08-05Paper
Path Contraction Faster than $2^n$2020-07-30Paper
Dominated Minimal Separators are Tame (Nearly All Others are Feral)2020-07-17Paper
https://portal.mardi4nfdi.de/entity/Q51113872020-05-27Paper
Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs2020-05-27Paper
Packing Cycles Faster Than Erdos-Posa2020-05-27Paper
A Linear-Time Parameterized Algorithm for Node Unique Label Cover2020-05-27Paper
A polynomial sized kernel for tracking paths problem2020-02-12Paper
A polynomial sized kernel for tracking paths problem2020-01-16Paper
Wannabe bounded treewidth graphs admit a polynomial kernel for DFVS2020-01-16Paper
Simultaneous Feedback Vertex Set2019-12-16Paper
Split Contraction2019-12-16Paper
Spanning Circuits in Regular Matroids2019-12-02Paper
Approximation Schemes for Low-rank Binary Matrix Approximation Problems2019-12-02Paper
Exact Algorithms via Monotone Local Search2019-11-21Paper
Finding, hitting and packing cycles in subexponential time on unit disk graphs2019-11-07Paper
Balanced Judicious Bipartition is Fixed-Parameter Tractable2019-10-28Paper
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets2019-10-01Paper
Packing Cycles Faster Than Erdos--Posa2019-08-29Paper
Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms2019-06-20Paper
A Near-Optimal Planarization Algorithm2019-06-20Paper
https://portal.mardi4nfdi.de/entity/Q57433792019-05-10Paper
https://portal.mardi4nfdi.de/entity/Q57434992019-05-10Paper
Minimum Bisection Is Fixed-Parameter Tractable2019-05-07Paper
https://portal.mardi4nfdi.de/entity/Q46338952019-05-06Paper
The Complexity of Independent Set Reconfiguration on Bipartite Graphs2019-03-28Paper
Clique-width III2019-03-28Paper
Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion2019-03-28Paper
Subquadratic Kernels for Implicit 3-H <scp>itting</scp> S <scp>et</scp> and 3-S <scp>et</scp> P <scp>acking</scp> Problems2019-03-28Paper
Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs2019-02-14Paper
Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree2019-02-06Paper
Kernelization2019-01-14Paper
Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes2018-12-06Paper
Covering Vectors by Spaces: Regular Matroids2018-11-19Paper
Deterministic Truncation of Linear Matroids2018-11-13Paper
Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal2018-11-13Paper
Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth2018-11-13Paper
Independence and Efficient Domination on P 6 -free Graphs2018-11-12Paper
Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors2018-11-12Paper
Linear Time Parameterized Algorithms for S <scp>ubset</scp> F <scp>eedback</scp> V <scp>ertex</scp> S <scp>et</scp>2018-11-12Paper
Uniform Kernelization Complexity of Hitting Forbidden Minors2018-11-05Paper
On Problems as Hard as CNF-SAT2018-11-05Paper
Representative Families of Product Families2018-11-05Paper
Kernelization Lower Bounds Through Colors and IDs2018-10-30Paper
Faster Parameterized Algorithms Using Linear Programming2018-10-30Paper
Long directed \((s,t)\)-path: FPT algorithm2018-10-19Paper
Below All Subsets for Minimal Connected Dominating Set2018-09-26Paper
Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms2018-08-02Paper
(Meta) Kernelization2018-08-02Paper
Kernelization of Cycle Packing with Relaxed Disjointness Constraints2018-07-18Paper
Independence and Efficient Domination on P6-free Graphs2018-07-16Paper
Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion2018-07-16Paper
Fully polynomial-time parameterized computations for graphs and matrices of low treewidth2018-07-16Paper
Spanning Circuits in Regular Matroids2018-07-16Paper
Beating Brute Force for Systems of Polynomial Equations over Finite Fields2018-07-16Paper
Slightly Superexponential Parameterized Problems2018-06-05Paper
Reconfiguration on sparse graphs2018-05-08Paper
Matrix Rigidity from the Viewpoint of Parameterized Complexity2018-05-02Paper
A New Perspective on FO Model Checking of Dense Graph Classes2018-04-23Paper
https://portal.mardi4nfdi.de/entity/Q46365712018-04-19Paper
https://portal.mardi4nfdi.de/entity/Q46366022018-04-19Paper
Matrix Rigidity from the Viewpoint of Parameterized Complexity2018-04-19Paper
https://portal.mardi4nfdi.de/entity/Q46344032018-04-10Paper
https://portal.mardi4nfdi.de/entity/Q46078892018-03-15Paper
https://portal.mardi4nfdi.de/entity/Q46078952018-03-15Paper
https://portal.mardi4nfdi.de/entity/Q46078962018-03-15Paper
https://portal.mardi4nfdi.de/entity/Q46079012018-03-15Paper
https://portal.mardi4nfdi.de/entity/Q46080152018-03-15Paper
Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms2018-03-15Paper
Faster and enhanced inclusion-minimal cograph completion2018-02-26Paper
Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems2018-01-30Paper
Simultaneous Feedback Vertex Set: A Parameterized Perspective2018-01-24Paper
https://portal.mardi4nfdi.de/entity/Q46019012018-01-24Paper
Critical node cut parameterized by treewidth and solution size is \(W[1\)-hard]2018-01-04Paper
https://portal.mardi4nfdi.de/entity/Q45981622017-12-19Paper
Lower Bounds for Approximation Schemes for Closest String2017-10-17Paper
Quick but odd growth of cacti2017-10-10Paper
Solving d-SAT via Backdoors to Small Treewidth2017-10-05Paper
https://portal.mardi4nfdi.de/entity/Q53637802017-09-29Paper
https://portal.mardi4nfdi.de/entity/Q53650782017-09-29Paper
https://portal.mardi4nfdi.de/entity/Q53650792017-09-29Paper
https://portal.mardi4nfdi.de/entity/Q53650802017-09-29Paper
Exact Algorithms via Monotone Local Search2017-09-29Paper
Lossy kernelization2017-08-17Paper
Hitting Selected (Odd) Cycles2017-08-14Paper
Faster exact algorithms for some terminal set problems2017-06-30Paper
Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)2017-04-25Paper
Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth2017-03-10Paper
https://portal.mardi4nfdi.de/entity/Q29578742017-01-30Paper
https://portal.mardi4nfdi.de/entity/Q29575182017-01-26Paper
Irrelevant vertices for the planar disjoint paths problem2016-11-25Paper
Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation)2016-07-22Paper
A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion2016-05-03Paper
A $c^k n$ 5-Approximation Algorithm for Treewidth2016-04-11Paper
On the ordered list subgraph embedding problems2016-04-06Paper
Hitting Forbidden Minors: Approximation and Kernelization2016-03-04Paper
The Structure of $W_4$-Immersion-Free Graphs2016-02-05Paper
On the threshold of intractability2015-11-19Paper
Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints2015-11-19Paper
Reconfiguration on sparse graphs2015-10-30Paper
Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree2015-10-27Paper
Uniform Kernelization Complexity of Hitting Forbidden Minors2015-10-27Paper
Deterministic Truncation of Linear Matroids2015-10-27Paper
Linear Time Parameterized Algorithms for Subset Feedback Vertex Set2015-10-27Paper
Distortion is Fixed Parameter Tractable2015-09-24Paper
Parameterized Algorithms2015-08-17Paper
Minimum bisection is fixed parameter tractable2015-06-26Paper
Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width2015-02-09Paper
On cutwidth parameterized by vertex cover2014-12-02Paper
Representative Sets of Product Families2014-10-08Paper
Solving Multicut Faster Than 2 n2014-10-08Paper
Kernel(s) for problems with no kernel2014-09-09Paper
Saving space by algebraization2014-08-13Paper
(Meta) Kernelization2014-07-25Paper
Parameterized Complexity of Bandwidth on Trees2014-07-01Paper
https://portal.mardi4nfdi.de/entity/Q54176422014-05-22Paper
Bidimensionality and Geometric Graphs2014-05-22Paper
Imbalance is fixed parameter tractable2014-04-14Paper
Obtaining a Bipartite Graph by Contracting Few Edges2014-04-10Paper
On the hardness of losing width2014-03-25Paper
Contracting graphs to paths and trees2014-03-25Paper
Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization2014-01-16Paper
Beyond bidimensionality: parameterized subexponential algorithms on directed graphs2014-01-10Paper
On the ordered list subgraph embedding problems2013-12-10Paper
The Fine Details of Fast Dynamic Programming over Tree Decompositions2013-12-10Paper
Faster Exact Algorithms for Some Terminal Set Problems2013-12-10Paper
On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges2013-12-10Paper
Hardness of r-dominating set on Graphs of Diameter (r + 1)2013-12-10Paper
Quadratic Upper Bounds on the Erdős-Pósa Property for a Generalization of Packing and Covering Cycles2013-11-15Paper
Parameterized Tractability of Multiway Cut with Parity Constraints2013-08-12Paper
Computing optimal Steiner trees in polynomial space2013-08-05Paper
Clustering with local restrictions2013-06-06Paper
Subexponential algorithms for partial cover problems2013-04-04Paper
https://portal.mardi4nfdi.de/entity/Q49041442013-01-28Paper
Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time2013-01-04Paper
Cops and robber game without recharging2012-12-06Paper
Subexponential Algorithms for Partial Cover Problems2012-10-24Paper
Treewidth governs the complexity of target set selection2012-10-16Paper
On the directed full degree spanning tree problem2012-10-16Paper
Kernelization – Preprocessing with a Guarantee2012-09-05Paper
https://portal.mardi4nfdi.de/entity/Q29116262012-08-31Paper
Determining the winner of a Dodgson election is hard2012-08-29Paper
Faster algorithms for finding and counting subgraphs2012-08-17Paper
Local search: is brute-force avoidable?2012-08-17Paper
Contracting graphs to paths and trees2012-06-15Paper
On the Hardness of Losing Width2012-06-15Paper
On Cutwidth Parameterized by Vertex Cover2012-06-15Paper
Sharp separation and applications to exact and parameterized algorithms2012-04-26Paper
Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves2012-04-24Paper
Cutwidth of Split Graphs and Threshold Graphs2012-03-15Paper
https://portal.mardi4nfdi.de/entity/Q31136832012-01-23Paper
https://portal.mardi4nfdi.de/entity/Q31137542012-01-23Paper
Planar k-Path in Subexponential Time and Polynomial Space2011-12-16Paper
Guard games on graphs: keep the intruder out!2011-12-07Paper
Bandwidth on AT-free graphs2011-12-07Paper
On the complexity of reconstructing H-free graphs from their Star Systems2011-10-12Paper
Feedback Vertex Set in Mixed Graphs2011-08-12Paper
An exact algorithm for minimum distortion embedding2011-07-14Paper
Tight Bounds for Linkages in Planar Graphs2011-07-06Paper
Clustering with Local Restrictions2011-07-06Paper
Ranking and Drawing in Subexponential Time2011-05-19Paper
A linear kernel for a planar connected dominating set2011-05-18Paper
On the complexity of some colorful problems parameterized by treewidth2011-02-21Paper
Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time2010-11-16Paper
Generalized Graph Clustering: Recognizing (p,q)-Cluster Graphs2010-11-16Paper
Intractability of Clique-Width Parameterizations2010-11-04Paper
Imbalance Is Fixed Parameter Tractable2010-07-20Paper
Cops and Robber Game without Recharging2010-06-22Paper
Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing2010-06-22Paper
Characterizing and computing minimal cograph completions2010-05-25Paper
On the complexity of computing treelength2010-05-25Paper
Guard Games on Graphs: Keep the Intruder Out!2010-05-11Paper
Finding the longest isometric cycle in a graph2010-04-28Paper
Sharp Separation and Applications to Exact and Parameterized Algorithms2010-04-27Paper
An Exact Algorithm for Minimum Distortion Embedding2010-01-21Paper
Planar Capacitated Dominating Set Is W[1-Hard]2010-01-14Paper
On the Directed Degree-Preserving Spanning Tree Problem2010-01-14Paper
Even Faster Algorithm for Set Splitting!2010-01-14Paper
Bandwidth on AT-Free Graphs2009-12-17Paper
Simpler Parameterized Algorithm for OCT2009-12-11Paper
The complexity ecology of parameters: An illustration using bounded max leaf number2009-10-19Paper
Fast FAST2009-07-14Paper
Incompressibility through Colors and IDs2009-07-14Paper
Distortion Is Fixed Parameter Tractable2009-07-14Paper
Linear Kernel for Planar Connected Dominating Set2009-06-03Paper
On the Complexity of Some Colorful Problems Parameterized by Treewidth2009-03-03Paper
Graph Layout Problems Parameterized by Vertex Cover2009-01-29Paper
Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs2009-01-20Paper
On the Complexity of Computing Treelength2008-09-17Paper
Characterizing and Computing Minimal Cograph Completions2008-06-19Paper
Capacitated Domination and Covering: A Parameterized Perspective2008-06-05Paper
Wheel-Free Deletion Is W[2-Hard]2008-06-05Paper
On the Complexity of Reconstructing H-free Graphs from Their Star Systems2008-04-15Paper
Optimal broadcast domination in polynomial time2006-12-14Paper
Graph-Theoretic Concepts in Computer Science2006-11-01Paper

Research outcomes over time


Doctoral students

No records found.


Known relations from the MaRDI Knowledge Graph

PropertyValue
MaRDI profile typeMaRDI person profile
instance ofhuman


This page was built for person: Daniel Lokshtanov