Hjem
Daniel Lokshtanovs bilde

Daniel Lokshtanov

Professor
  • E-postDaniel.Lokshtanov@uib.no
  • Telefon+47 55 58 41 56
  • Besøksadresse
    HIB - Thormøhlensgt. 55
  • Postadresse
    Postboks 7803
    5020 Bergen
Lærebok
  • 2019. Kernelization. Theory of Parameterized Preprocessing. Cambridge University Press.
Vitenskapelig artikkel
  • 2020. Eth-tight algorithms for long path and cycle on unit disk graphs. Leibniz International Proceedings in Informatics.
  • 2019. Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems. ACM Transactions on Algorithms (TALG). 44 sider.
  • 2019. Split contraction: The untold story. ACM Transactions on Computation Theory.
  • 2019. Spanning circuits in regular matroids. ACM Transactions on Algorithms (TALG).
  • 2019. Path Contraction Faster Than 2n. Leibniz International Proceedings in Informatics. 11:1-11:13.
  • 2019. Packing cycles faster than Erdos-Posa. SIAM Journal on Discrete Mathematics. 1194-1215.
  • 2019. Minimum Bisection Is Fixed-Parameter Tractable. SIAM journal on computing (Print). 417-450.
  • 2019. Going Far From Degeneracy. Leibniz International Proceedings in Informatics. 47:1-47:14.
  • 2019. Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs. Discrete & Computational Geometry. 879-911.
  • 2019. Exact algorithms via monotone local search. Journal of the ACM. 8:1-8:23.
  • 2019. Decomposition of map graphs with applications. Leibniz International Proceedings in Informatics. 60:1-60:15.
  • 2019. Balanced judicious bipartition is fixed-parameter tractable. SIAM Journal on Discrete Mathematics. 1878-1911.
  • 2018. The complexity of independent set reconfiguration on bipartite graphs. ACM Transactions on Algorithms (TALG). 1-19.
  • 2018. Subexponential-Time Algorithms for Maximum Independent Set in Pt-Free and Broom-Free Graphs. Algorithmica. 421-438.
  • 2018. Slightly superexponential parameterized problems. SIAM journal on computing (Print). 675-702.
  • 2018. Simultaneous feedback vertex set: A parameterized perspective. ACM Transactions on Computation Theory.
  • 2018. Reducing CMSO model checking to highly connected graphs. Leibniz International Proceedings in Informatics. 135:1-135:14.
  • 2018. Reconfiguration on sparse graphs. Journal of computer and system sciences (Print). 122-131.
  • 2018. Quasipolynomial representation of transversal matroids with applications in parameterized complexity. Leibniz International Proceedings in Informatics. 1-13.
  • 2018. Polylogarithmic approximation algorithms for weighted-F-Deletion problems. Leibniz International Proceedings in Informatics. 1:1-1:15.
  • 2018. On the parameterized complexity of simultaneous deletion problems. Leibniz International Proceedings in Informatics. 9:1-9:14.
  • 2018. Matrix rigidity from the viewpoint of parameterized complexity . SIAM Journal on Discrete Mathematics. 966-985.
  • 2018. Long directed (s,t)-path: FPT algorithm. Information Processing Letters. 8-12.
  • 2018. Linear time parameterized algorithms for subset feedback vertex set. ACM Transactions on Algorithms (TALG). 37 sider.
  • 2018. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Transactions on Algorithms (TALG). 1-30.
  • 2018. Kernels for (Connected) dominating set on graphs with excluded topological minors. ACM Transactions on Algorithms (TALG).
  • 2018. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Transactions on Algorithms (TALG).
  • 2018. Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion. ACM Transactions on Algorithms (TALG). 28 sider.
  • 2018. Excluded grid minors and efficient polynomial-time approximation schemes. Journal of the ACM. 1-44.
  • 2018. Erdos-Posa property of obstructions to interval graphs. Leibniz International Proceedings in Informatics. 1-15.
  • 2018. Covering Vectors by Spaces: Regular Matroids. SIAM Journal on Discrete Mathematics. 2512-2565.
  • 2018. Conflict Free Feedback Vertex Set: A Parameterized Dichotomy. Leibniz International Proceedings in Informatics. 53:1-53:15.
  • 2018. Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 262-273.
  • 2018. Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring. ACM Transactions on Algorithms (TALG). 27 sider.
  • 2018. Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS. Leibniz International Proceedings in Informatics. 110:1-110:4.
  • 2018. Below all subsets for minimal connected dominating set. SIAM Journal on Discrete Mathematics. 2332-2345.
  • 2018. Balanced judicious bipartition is fixed-paramater tractable. Leibniz International Proceedings in Informatics. 40:1-40:15.
  • 2018. Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces. Leibniz International Proceedings in Informatics. 21:1-21:14.
  • 2018. A polynomial sized kernel for tracking paths problem. Lecture Notes in Computer Science (LNCS). 94-107.
  • 2017. Uniform kernelization complexity of hitting forbidden minors. ACM Transactions on Algorithms (TALG). 1-35.
  • 2017. Split contraction: The untold story. Leibniz International Proceedings in Informatics. 1-14.
  • 2017. Spanning Circuits in Regular Matroids. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 1433-1441.
  • 2017. Representative families of product families. ACM Transactions on Algorithms (TALG). 1-29.
  • 2017. Quick but Odd Growth of Cacti. Algorithmica. 271-290.
  • 2017. Parameterized complexity of directed Steiner tree on sparse graphs. SIAM Journal on Discrete Mathematics. 1294-1327.
  • 2017. Packing cycles faster than Erdös-Pósa. Leibniz International Proceedings in Informatics. 1-15.
  • 2017. Matrix rigidity from the viewpoint of parameterized complexity. Leibniz International Proceedings in Informatics.
  • 2017. Lossy kernelization. Proceedings of the Annual ACM Symposium on Theory of Computing. 224-237.
  • 2017. Irrelevant vertices for the planar Disjoint Paths Problem. Journal of combinatorial theory. Series B (Print). 815-843.
  • 2017. Independence and efficient domination on P6-free graphs. ACM Transactions on Algorithms (TALG).
  • 2017. Hitting selected (ODD) Cycles. SIAM Journal on Discrete Mathematics. 1581-1615.
  • 2017. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. SIAM journal on computing (Print). 161-189.
  • 2017. Finding, hitting and packing cycles in subexponential time on unit disk graphs. Leibniz International Proceedings in Informatics. 1-15.
  • 2017. Faster exact algorithms for some terminal set problems. Journal of computer and system sciences (Print). 195-207.
  • 2017. Faster and enhanced inclusion-minimal cograph completion. Lecture Notes in Computer Science (LNCS). 210-224.
  • 2017. Critical node cut parameterized by treewidth and solution size is W[1]-Hard. Lecture Notes in Computer Science (LNCS). 32-44.
  • 2017. Covering vectors by spaces: Regular matroids. Leibniz International Proceedings in Informatics. 1-15.
  • 2017. A linear-Time parameterized algorithm for node unique label cover. Leibniz International Proceedings in Informatics.
  • 2017. A 2lk kernel for l-component order connectivity. Leibniz International Proceedings in Informatics. 1-14.
  • 2016. Tree deletion set has a polynomial kernel (but No OPTο(1) Approximation). SIAM Journal on Discrete Mathematics. 1371-1384.
  • 2016. Subexponential algorithms for rectilinear Steiner tree and arborescence problems. Leibniz International Proceedings in Informatics. 39.1-39.15.
  • 2016. Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). 515-524.
  • 2016. SIMULTANEOUS Feedback Vertex set: A parameterized perspective. Leibniz International Proceedings in Informatics. 7:1-7:15.
  • 2016. On the ordered list subgraph embedding problems. Algorithmica. 992-1018.
  • 2016. On problems as hard as CNF-SAT. ACM Transactions on Algorithms (TALG).
  • 2016. Lower bounds for approximation schemes for closest string. Leibniz International Proceedings in Informatics. 12.1-12.10.
  • 2016. Kernelization of cycle packing with relaxed disjointness constraints. Leibniz International Proceedings in Informatics. 1-14.
  • 2016. Kernelization and sparseness: The case of dominating set. Leibniz International Proceedings in Informatics. 14 sider.
  • 2016. Hitting forbidden minors: Approximation and kernelization. SIAM Journal on Discrete Mathematics. 383-410.
  • 2016. Faster exact and parameterized algorithm for feedback vertex set in tournaments. Leibniz International Proceedings in Informatics. 24.1-24.15.
  • 2016. Exact algorithms via monotone local search. Proceedings of the Annual ACM Symposium on Theory of Computing. 764-775.
  • 2016. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM.
  • 2016. A new perspective on FO model checking of dense graph classes. Logic in Computer Science. 176-184.
  • 2016. A faster FPT algorithm and a smaller kernel for block graph vertex deletion. Lecture Notes in Computer Science (LNCS). 1-13.
  • 2016. A $c^k n$ 5-approximation algorithm for treewidth. SIAM journal on computing (Print). 317-378.
  • 2016. (Meta) Kernelization. Journal of the ACM.
  • 2015. Uniform kernelization complexity of hitting forbidden minors. Lecture Notes in Computer Science (LNCS). 629-641.
  • 2015. Reconfiguration on sparse graphs. Lecture Notes in Computer Science (LNCS). 506-517.
  • 2015. Quick but odd growth of cacti. Leibniz International Proceedings in Informatics. 258-269.
  • 2015. Parameterized single-exponential time polynomial space algorithm for steiner tree. Lecture Notes in Computer Science (LNCS). 494-505.
  • 2015. On the threshold of intractability. Lecture Notes in Computer Science (LNCS). 411-423.
  • 2015. Linear time parameterized algorithms for subset feedback vertex set. Lecture Notes in Computer Science (LNCS). 935-946.
  • 2015. Fast algorithms for parameterized problems with relaxed disjointness constraints. Lecture Notes in Computer Science (LNCS). 545-556.
  • 2015. Deterministic truncation of linear matroids. Lecture Notes in Computer Science (LNCS). 922-934.
  • 2015. Consensus patterns (Probably) has no EPTAS. Lecture Notes in Computer Science (LNCS). 239-250.
  • 2014. Tree deletion set has a polynomial kernel (but no OPTO(1) approximation). Leibniz International Proceedings in Informatics. 85-96.
  • 2014. Solving Multicut faster than 2n. Lecture Notes in Computer Science (LNCS). 666-676.
  • 2014. Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems. Tsinghua Science and Technology. 374-386.
  • 2014. Representative sets of product families. Lecture Notes in Computer Science (LNCS). 443-454.
  • 2014. On cutwidth parameterized by vertex cover. Algorithmica. 940-953.
  • 2014. Kernelization lower bounds through colors and IDs. ACM Transactions on Algorithms (TALG).
  • 2014. Faster parameterized algorithms using linear programming. ACM Transactions on Algorithms (TALG).
  • 2014. Contracting graphs to paths and trees. Algorithmica. 109-132.
  • 2014. Almost optimal lower bounds for problems parameterized by clique-width. SIAM journal on computing (Print). 1541-1563.
  • 2013. Quadratic upper bounds on the Erdős–Pósa property for a generalization of packing and covering cycles. Journal of Graph Theory. 417-424.
  • 2013. Obtaining a bipartite graph by contracting few edges. SIAM Journal on Discrete Mathematics. 2143-2156.
  • 2013. Imbalance is fixed parameter tractable. Information Processing Letters.
  • 2013. Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization. Information and Computation. 109-116.
  • 2013. Computing optimal Steiner trees in polynomial space. Algorithmica. 584-604.
  • 2013. Clustering with local restrictions. Information and Computation. 278-292.
  • 2013. Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs. Information and Computation. 60-70.
  • 2013. An O(c^k n) 5-approximation algorithm for treewidth. Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). 499-508.
  • 2012. Sharp separation and applications to exact and parameterized algorithms. Algorithmica. 692-706.
  • 2012. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms (extended abstract). Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). 470-479.
  • 2012. On Cutwidth Parameterized by Vertex Cover. Algorithmica.
  • 2012. Kernel(s) for Problems with no Kernel: On Out-Trees with Many Leaves. ACM Transactions on Algorithms (TALG). 19 sider.
  • 2012. Faster algorithms for finding and counting subgraphs. Journal of computer and system sciences (Print). 698-706.
  • 2012. Cops and robber game without recharging. Theory of Computing Systems. 611-620.
  • 2012. Contracting graphs to paths and trees. Lecture Notes in Computer Science (LNCS). 55-66.
  • 2012. Computing the cutwidth of bipartite permutation graphs in linear time. SIAM Journal on Discrete Mathematics. 1008-1021.
  • 2011. Treewidth governs the complexity of target set selection. Discrete Optimization. 87-96.
  • 2011. Subexponential algorithms for partial cover problems. Information Processing Letters. 814-818.
  • 2011. On the directed Full Degree Spanning Tree problem. Discrete Optimization. 97-109.
  • 2011. On the complexity of some colorful problems parameterized by treewidth. Information and Computation. 143-153.
  • 2011. On the Complexity of Reconstructing H-Free Graphs from Their Star Systems. Journal of Graph Theory. 113-124.
  • 2011. Guard games on graphs: Keep the intruder out! Theoretical Computer Science. 6484-6497.
  • 2011. Cutwidth of Split Graphs and Threshold Graphs. SIAM Journal on Discrete Mathematics. 1418-1437.
  • 2011. Bandwidth on AT-free graphs. Theoretical Computer Science. 7001-7008.
  • 2011. An exact algorithm for minimum distortion embedding. Theoretical Computer Science. 3530-3536.
  • 2011. A linear kernel for a planar connected dominating set. Theoretical Computer Science. 2536-2543.
  • 2010. On the complexity of computing treelength. Discrete Applied Mathematics. 820-827.
  • 2010. Intractability of clique-width parameterizations. SIAM journal on computing (Print). 1941-1956.
  • 2010. Imbalance is fixed parameter tractable. Lecture Notes in Computer Science (LNCS). 199-208.
  • 2010. Generalized graph clustering: recognizing (p,q)-cluster graphs. Lecture Notes in Computer Science (LNCS). 171-183.
  • 2010. Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing. Lecture Notes in Computer Science (LNCS). 334-345.
  • 2010. Computing the cutwidth of bipartite permutation graphs in linear time. Lecture Notes in Computer Science (LNCS). 75-87.
  • 2010. Characterizing and computing minimal cograph completions. Discrete Applied Mathematics. 755-764.
  • 2010. Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. Leibniz International Proceedings in Informatics. 251-262.
  • 2010. Algorithmic Lower Bounds for Problems on Decomposable Graphs. Lecture Notes in Computer Science (LNCS). 37.
  • 2009. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems. 822-848.
  • 2009. Subexponential Algorithms for Partial Cover Problems. Leibniz International Proceedings in Informatics. 193-201.
  • 2009. Simpler Parameterized Algorithm for OCT. Lecture Notes in Computer Science (LNCS). 380-384.
  • 2009. On the Directed Degree-Preserving Spanning Tree Problem. Lecture Notes in Computer Science (LNCS). 276-287.
  • 2009. Linear Kernel for Planar Connected Dominating Set. Lecture Notes in Computer Science (LNCS). 281-290.
  • 2009. Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. Leibniz International Proceedings in Informatics. 421-432.
  • 2009. Incompressibility through Colors and IDs. Lecture Notes in Computer Science (LNCS). 378-389.
  • 2009. Finding the longest isometric cycle in a graph. Discrete Applied Mathematics. 2670-2674.
  • 2009. Fast FAST. Lecture Notes in Computer Science (LNCS). 49-58.
  • 2009. Even Faster Algorithm for Set Splitting! Lecture Notes in Computer Science (LNCS). 288-299.
  • 2009. Distortion Is Fixed Parameter Tractable. Lecture Notes in Computer Science (LNCS). 463-474.
  • 2009. Bandwidth on AT-Free Graphs. Lecture Notes in Computer Science (LNCS). 573-582.
  • 2009. An Exact Algorithm for Minimum Distortion Embedding. Lecture Notes in Computer Science (LNCS). 112-121.
  • 2008. Wheel-free deletion is W[2]-Hard. Lecture Notes in Computer Science (LNCS). 141-147.
  • 2008. On the complexity of reconstructing H-free graphs from their Star Systems. Lecture Notes in Computer Science (LNCS). 194-205.
  • 2008. Graph Layout problems Parameterized by Vertex Cover. Lecture Notes in Computer Science (LNCS). 294-305.
  • 2008. Cutwidth of split graphs, threshold graphs, and proper interval graphs. Lecture Notes in Computer Science (LNCS). 218-229.
  • 2008. Characterizing and Computing Minimal Cograph Completions. Lecture Notes in Computer Science (LNCS). 147-158.
  • 2008. Capacitated Domination and Covering: A Parameterized Perspective. Lecture Notes in Computer Science (LNCS). 78-90.
  • 2007. On the Complexity of Computing Treelength. Lecture Notes in Computer Science (LNCS). 276-287.
  • 2006. Optimal broadcast domination in polynomial time. Discrete Mathematics. 3267-3280.
Leder
  • 2018. Preface. Leibniz International Proceedings in Informatics.
Vitenskapelig monografi
  • 2015. Parameterized Algorithms.
Doktorgradsavhandling
  • 2017. Multivariate Algorithmic Analysis of Hitting Small Sets.
  • 2017. Beyond the question of fixed-parameter tractability.
  • 2009. New methods in parameterized algorithms and complexity.
Vitenskapelig Kapittel/Artikkel/Konferanseartikkel
  • 2011. Obtaining a bipartite graph by contracting few edges. 12 sider.
  • 2010. Saving Space by Algebraization. 10 sider.
  • 2009. Local Search: Is Brute-Force Avoidable? 6 sider.

Se fullstendig oversikt over publikasjoner i CRIStin.