| Publication | Date of Publication | Type |
|---|
AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)
Algorithmica | 2025-01-24 | Paper |
Optimally repurposing existing algorithms to obtain exponential-time approximations
| 2024-11-28 | Paper |
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
| 2024-07-19 | Paper |
A framework for parameterized subexponential algorithms for generalized cycle hitting problems on planar graphs
| 2024-07-19 | Paper |
Conditional lower bounds for sparse parameterized 2-CSP: a streamlined proof
| 2024-05-29 | Paper |
Computing square colorings on bounded-treewidth and planar graphs
| 2024-05-14 | Paper |
Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs
| 2024-05-14 | Paper |
Dynamic time warping under translation: approximation guided by space-filling curves
| 2024-05-14 | Paper |
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
Algorithmica | 2024-04-24 | Paper |
Computing generalized convolutions faster than brute force
Algorithmica | 2024-01-09 | Paper |
Dynamic time warping under translation: approximation guided by space-filling curves
| 2023-12-20 | Paper |
Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
ACM Transactions on Algorithms | 2023-10-31 | Paper |
Parameterized complexity of multicut in weighted trees
Theoretical Computer Science | 2023-10-12 | Paper |
Parameterized complexity of weighted multicut in trees
Graph-Theoretic Concepts in Computer Science | 2023-05-05 | Paper |
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
SIAM Journal on Computing | 2023-04-04 | Paper |
Parameterized algorithms for generalizations of directed feedback vertex set
Discrete Optimization | 2023-02-16 | Paper |
scientific article; zbMATH DE number 7651211 (Why is no real title available?)
| 2023-02-07 | Paper |
Chordless Cycle Packing Is Fixed-Parameter Tractable
| 2023-02-07 | Paper |
Finding and Counting Permutations via CSPs
| 2023-02-03 | Paper |
scientific article; zbMATH DE number 7650305 (Why is no real title available?)
| 2023-02-03 | Paper |
How Does Object Fatness Impact the Complexity of Packing in d Dimensions
| 2023-02-03 | Paper |
Parameterized Intractability of Even Set and Shortest Vector Problem
Journal of the ACM | 2022-12-08 | Paper |
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
Journal of the ACM | 2022-12-08 | Paper |
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
Treewidth, Kernels, and Algorithms | 2022-10-19 | Paper |
Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
| 2022-07-21 | Paper |
Almost tight lower bounds for hard cutting problems in embedded graphs
| 2022-07-18 | Paper |
A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
SIAM Journal on Computing | 2022-04-20 | Paper |
Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
Journal of Computer and System Sciences | 2022-01-31 | Paper |
Multi-budgeted directed cuts
| 2021-08-04 | Paper |
Finding and counting permutations via CSPs
Algorithmica | 2021-07-26 | Paper |
A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
SIAM Journal on Computing | 2021-01-13 | Paper |
The parameterized hardness of the \(k\)-center problem in transportation networks
| 2020-08-25 | Paper |
Multi-budgeted directed cuts
Algorithmica | 2020-08-12 | Paper |
scientific article; zbMATH DE number 7228418 (Why is no real title available?)
| 2020-08-05 | Paper |
Subexponential parameterized algorithms for graphs of polynomial growth
| 2020-05-27 | Paper |
Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
| 2020-05-27 | Paper |
The parameterized hardness of the \(k\)-center problem in transportation networks
Algorithmica | 2020-05-21 | Paper |
Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
SIAM Journal on Computing | 2020-03-27 | Paper |
Parameterized algorithms for generalizations of directed feedback vertex set
Lecture Notes in Computer Science | 2020-02-06 | Paper |
Routing with congestion in acyclic digraphs
Information Processing Letters | 2019-09-20 | Paper |
Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
Algorithmica | 2019-09-10 | Paper |
A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Finding and counting permutations via CSPs
| 2019-08-13 | Paper |
Finding small patterns in permutations in linear time
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Interval deletion is fixed-parameter tractable
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
A subexponential parameterized algorithm for subset TSP on planar graphs
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Kernelization of packing problems
| 2019-05-10 | Paper |
Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
| 2019-05-10 | Paper |
Approximating fractional hypertree width
| 2019-05-06 | Paper |
Erd\"os-P\'osa property of minor-models with prescribed vertex sets
| 2019-04-01 | Paper |
Fine-grained complexity of coloring unit disks and balls
| 2019-02-27 | Paper |
Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
Algorithmica | 2019-02-14 | Paper |
Known algorithms on graphs of bounded treewidth are probably optimal
ACM Transactions on Algorithms | 2018-11-13 | Paper |
On problems as hard as CNF-SAT
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Interval deletion is fixed-parameter tractable
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Exponential Time Complexity of the Permanent and the Tutte Polynomial
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Directed subset feedback vertex set is fixed-parameter tractable
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Minimizing movement: fixed-parameter tractability
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Constraint solving via fractional edge covers
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Fine-grained complexity of coloring unit disks and balls
| 2018-08-13 | Paper |
Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Slightly superexponential parameterized problems
SIAM Journal on Computing | 2018-06-05 | Paper |
The limited blessing of low dimensionality: when \(1-1/d\) is the best possible exponent for \(d\)-dimensional geometric problems (extended abstract)
Proceedings of the thirtieth annual symposium on Computational geometry | 2018-04-23 | Paper |
Parameterized and approximation results for scheduling with a low rank processing time matrix
| 2018-04-19 | Paper |
Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs
| 2018-04-19 | Paper |
H-free graphs, independent sets, and subexponential-time algorithms
| 2018-04-10 | Paper |
scientific article; zbMATH DE number 6851840 (Why is no real title available?)
| 2018-03-21 | Paper |
Covering a tree with rooted subtrees -- parameterized and approximation algorithms
| 2018-03-15 | Paper |
Fixed-parameter Approximability of Boolean MinCSPs
| 2018-03-02 | Paper |
Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems
| 2018-01-30 | Paper |
The complexity landscape of fixed-parameter directed Steiner network problems
| 2017-12-19 | Paper |
Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth
| 2017-12-19 | Paper |
Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
An exact characterization of tractable demand patterns for maximum disjoint path problems
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
scientific article; zbMATH DE number 6783431 (Why is no real title available?)
| 2017-09-29 | Paper |
scientific article; zbMATH DE number 6783432 (Why is no real title available?)
| 2017-09-29 | Paper |
scientific article; zbMATH DE number 6783450 (Why is no real title available?)
| 2017-09-29 | Paper |
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Hitting forbidden subgraphs in graphs of bounded treewidth
Information and Computation | 2017-09-28 | Paper |
Homomorphisms are a good basis for counting small subgraphs
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Coloring Graphs with Constraints on Connectivity
Journal of Graph Theory | 2017-08-10 | Paper |
List H-coloring a graph by removing few vertices
Algorithmica | 2017-05-11 | Paper |
Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
| 2017-03-03 | Paper |
Chordal editing is fixed-parameter tractable
| 2017-03-03 | Paper |
Parameterized vertex deletion problems for hereditary graph classes with a block property
Graph-Theoretic Concepts in Computer Science | 2016-12-22 | Paper |
Rooted grid minors
Journal of Combinatorial Theory. Series B | 2016-11-25 | Paper |
Parameterized complexity and kernelizability of max ones and exact ones problems
ACM Transactions on Computation Theory | 2016-10-24 | Paper |
Chordal editing is fixed-parameter tractable
Algorithmica | 2016-06-28 | Paper |
Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
Lecture Notes in Computer Science | 2015-11-19 | Paper |
On the parameterized complexity of finding separators with non-hereditary properties
Algorithmica | 2015-09-02 | Paper |
Parameterized algorithms
| 2015-08-17 | Paper |
Structure theorem and isomorphism test for graphs with excluded topological subgraphs
SIAM Journal on Computing | 2015-06-02 | Paper |
Finding small separators in linear time via treewidth reduction
ACM Transactions on Algorithms | 2014-12-05 | Paper |
Approximating fractional hypertree width
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Hitting forbidden subgraphs in graphs of bounded treewidth
Mathematical Foundations of Computer Science 2014 | 2014-10-14 | Paper |
Geometric clustering, fixed-parameter tractability and lower bounds with respect to the dimension
ACM Transactions on Algorithms | 2014-09-09 | Paper |
On the hardness of losing weight
ACM Transactions on Algorithms | 2014-09-09 | Paper |
Tractable hypergraph properties for constraint satisfaction and conjunctive queries
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Constraint satisfaction parameterized by solution size
SIAM Journal on Computing | 2014-07-30 | Paper |
Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
SIAM Journal on Computing | 2014-07-30 | Paper |
Immersions in highly edge connected graphs
SIAM Journal on Discrete Mathematics | 2014-06-19 | Paper |
Fixed-parameter tractability of multicut parameterized by the size of the cutset
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Finding topological subgraphs is fixed-parameter tractable
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Structure theorem and isomorphism test for graphs with excluded topological subgraphs
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
A faster FPT algorithm for bipartite contraction
Information Processing Letters | 2014-04-14 | Paper |
Parameterized complexity of Eulerian deletion problems
Algorithmica | 2014-03-25 | Paper |
Tractable hypergraph properties for constraint satisfaction and conjunctive queries
Journal of the ACM | 2014-02-17 | Paper |
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
Journal of the ACM | 2014-02-17 | Paper |
A faster FPT algorithm for bipartite contraction
Lecture Notes in Computer Science | 2013-12-10 | Paper |
Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
SIAM Journal on Computing | 2013-11-14 | Paper |
Size bounds and query plans for relational joins
SIAM Journal on Computing | 2013-11-14 | Paper |
List H-coloring a graph by removing few vertices
Lecture Notes in Computer Science | 2013-09-17 | Paper |
Directed Subset Feedback Vertex Set is fixed-parameter tractable
Automata, Languages, and Programming | 2013-08-12 | Paper |
A tight lower bound for planar multiway cut with fixed number of terminals
Automata, Languages, and Programming | 2013-08-12 | Paper |
Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
Automata, Languages, and Programming | 2013-08-12 | Paper |
Block-Sorted Quantified Conjunctive Queries
Automata, Languages, and Programming | 2013-08-07 | Paper |
Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
Automata, Languages, and Programming | 2013-08-06 | Paper |
Clustering with local restrictions
Information and Computation | 2013-06-06 | Paper |
The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable
| 2013-04-15 | Paper |
Cleaning interval graphs
Algorithmica | 2013-03-05 | Paper |
Bin packing with fixed number of bins revisited
Journal of Computer and System Sciences | 2013-02-21 | Paper |
Completely inapproximable monotone and antimonotone parameterized problems
Journal of Computer and System Sciences | 2013-02-21 | Paper |
Lower bounds based on the exponential time hypothesis
| 2013-01-28 | Paper |
The tractability of CSP classes defined by forbidden patterns
Journal of Artificial Intelligence Research | 2012-12-03 | Paper |
On the parameterized complexity of finding separators with non-hereditary properties
Graph-Theoretic Concepts in Computer Science | 2012-11-06 | Paper |
Stable assignment with couples: parameterized complexity and local search
Discrete Optimization | 2012-10-16 | Paper |
FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
The Multivariate Algorithmic Revolution and Beyond | 2012-09-05 | Paper |
What's next? Future directions in parameterized complexity
The Multivariate Algorithmic Revolution and Beyond | 2012-09-05 | Paper |
Enumerating homomorphisms
Journal of Computer and System Sciences | 2012-05-11 | Paper |
Obtaining a planar graph by vertex deletion
Algorithmica | 2012-04-26 | Paper |
Tractable structures for constraint satisfaction with truth tables
| 2012-04-24 | Paper |
Enumerating homomorphisms
| 2012-04-24 | Paper |
Treewidth reduction for constrained separation and bipartization problems
| 2012-01-23 | Paper |
Important separators and parameterized algorithms
Graph-Theoretic Concepts in Computer Science | 2011-12-16 | Paper |
Parameterized complexity of Eulerian deletion problems
Graph-Theoretic Concepts in Computer Science | 2011-12-16 | Paper |
Sparse balanced partitions and the complexity of subgraph problems
SIAM Journal on Discrete Mathematics | 2011-10-27 | Paper |
Packing cycles through prescribed vertices
Journal of Combinatorial Theory. Series B | 2011-08-10 | Paper |
Complexity of clique coloring and related problems
Theoretical Computer Science | 2011-07-14 | Paper |
Clustering with Local Restrictions
Automata, Languages and Programming | 2011-07-06 | Paper |
Constraint Satisfaction Parameterized by Solution Size
Automata, Languages and Programming | 2011-07-06 | Paper |
Soft constraints of difference and equality
Journal of Artificial Intelligence Research | 2011-06-16 | Paper |
Can you beat treewidth?
Theory of Computing | 2011-05-24 | Paper |
Tractable structures for constraint satisfaction with truth tables
Theory of Computing Systems | 2011-05-23 | Paper |
The complexity of global cardinality constraints
Logical Methods in Computer Science | 2010-12-20 | Paper |
Parameterized complexity of the arc-preserving subsequence problem
Graph Theoretic Concepts in Computer Science | 2010-11-16 | Paper |
Parameterized complexity and local search approaches for the stable marriage problem with ties
Algorithmica | 2010-10-07 | Paper |
Parameterized complexity and kernelizability of Max Ones and Exact Ones problems
Mathematical Foundations of Computer Science 2010 | 2010-09-03 | Paper |
Constant ratio fixed-parameter approximation of the edge multicut problem
Information Processing Letters | 2010-09-01 | Paper |
Constraint solving via fractional edge covers
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Bin packing with fixed number of bins revisited
Lecture Notes in Computer Science | 2010-06-22 | Paper |
Chordal deletion is fixed-parameter tractable
Algorithmica | 2010-05-28 | Paper |
Computing geometric minimum-dilation graphs is NP-hard
International Journal of Computational Geometry & Applications | 2010-05-28 | Paper |
Parameterized graph cleaning problems
Discrete Applied Mathematics | 2010-04-28 | Paper |
Stable assignment with couples: parameterized complexity and local search
Parameterized and Exact Computation | 2010-01-14 | Paper |
A parameterized view on matroid optimization problems
Theoretical Computer Science | 2009-11-04 | Paper |
Minimizing Movement: Fixed-Parameter Tractability
Lecture Notes in Computer Science | 2009-10-29 | Paper |
Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem
Lecture Notes in Computer Science | 2009-10-29 | Paper |
Closest Substring Problems with Small Distances
SIAM Journal on Computing | 2009-08-20 | Paper |
Approximation and Online Algorithms
Lecture Notes in Computer Science | 2009-08-11 | Paper |
List edge multicoloring in graphs with few cycles
Information Processing Letters | 2009-07-09 | Paper |
Complexity results for minimum sum edge coloring
Discrete Applied Mathematics | 2009-06-30 | Paper |
A Parameterized View on Matroid Optimization Problems
Automata, Languages and Programming | 2009-03-12 | Paper |
The complexity of nonrepetitive coloring
Discrete Applied Mathematics | 2009-03-04 | Paper |
On tree width, bramble size, and expansion
Journal of Combinatorial Theory. Series B | 2009-01-21 | Paper |
Parameterized Graph Cleaning Problems
Graph-Theoretic Concepts in Computer Science | 2009-01-20 | Paper |
Chordal Deletion Is Fixed-Parameter Tractable
Graph-Theoretic Concepts in Computer Science | 2008-09-04 | Paper |
On the Hardness of Losing Weight
Automata, Languages and Programming | 2008-08-28 | Paper |
Complexity of unique list colorability
Theoretical Computer Science | 2008-07-31 | Paper |
Obtaining a Planar Graph by Vertex Deletion
Graph-Theoretic Concepts in Computer Science | 2008-07-01 | Paper |
Parameterized Complexity of Independence and Domination on Geometric Graphs
Parameterized and Exact Computation | 2008-06-03 | Paper |
Searching the \(k\)-change neighborhood for TSP is W[1-hard]
Operations Research Letters | 2008-05-29 | Paper |
Precoloring extension on chordal graphs
| 2007-03-05 | Paper |
The complexity of chromatic strength and chromatic edge strength
Computational Complexity | 2006-11-17 | Paper |
Minimum sum multicoloring on the edges of trees
Theoretical Computer Science | 2006-09-14 | Paper |
Algorithms – ESA 2005
Lecture Notes in Computer Science | 2006-06-27 | Paper |
Precoloring extension on unit interval graphs
Discrete Applied Mathematics | 2006-06-09 | Paper |
Parameterized graph separation problems
Theoretical Computer Science | 2006-04-06 | Paper |
Parameterized coloring problems on chordal graphs
Theoretical Computer Science | 2006-04-06 | Paper |
Parameterized complexity of constraint satisfaction problems
Computational Complexity | 2006-02-07 | Paper |
Approximation and Online Algorithms
Lecture Notes in Computer Science | 2005-12-14 | Paper |
NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
Journal of Graph Theory | 2005-08-29 | Paper |
A short proof of the NP-completeness of minimum sum interval coloring
Operations Research Letters | 2005-08-25 | Paper |
Parameterized and Exact Computation
Lecture Notes in Computer Science | 2005-08-23 | Paper |
Parameterized and Exact Computation
Lecture Notes in Computer Science | 2005-08-23 | Paper |
Eulerian disjoint paths problem in grid graphs is NP-complete
Discrete Applied Mathematics | 2004-11-23 | Paper |
scientific article; zbMATH DE number 1929966 (Why is no real title available?)
| 2003-06-18 | Paper |
