Bart M. P. Jansen

ACM Trans. Comput. Theory, March, 2024

2023

Finding <i>k</i>-secluded trees faster.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., December, 2023

<i>p</i>-Edge/vertex-connected vertex cover: Parameterized and approximation algorithms.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., May, 2023

Fine-grained parameterized complexity analysis of graph coloring problems.

[BibT_eX]

[DOI]

Lars Jaffke

Discret. Appl. Math., 2023

5-Approximation for $\mathcal{H}$-Treewidth Essentially as Fast as $\mathcal{H}$-Deletion Parameterized by Solution Size.

[BibT_eX]

[DOI]

CoRR, 2023

Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions.

[BibT_eX]

[DOI]

Bart van der Steenhoven

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Sunflowers Meet Sparsity: A Linear-Vertex Kernel for Weighted Clique-Packing on Sparse Graphs.

[BibT_eX]

[DOI]

Shivesh Kumar Roy

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

On the Parameterized Complexity of Multiway Near-Separator.

[BibT_eX]

[DOI]

Shivesh Kumar Roy

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Single-Exponential FPT Algorithms for Enumerating Secluded ℱ-Free Subgraphs and Deleting to Scattered Graph Classes.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

Upward and Orthogonal Planarity are W[1]-Hard Parameterized by Treewidth.

[BibT_eX]

[DOI]

Fabrizio Montecchiani

Kirill Simonov

Proceedings of the Graph Drawing and Network Visualization - 31st International Symposium, 2023

5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution Size.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel.

[BibT_eX]

[DOI]

Marin Bougeret

Ignasi Sau

SIAM J. Discret. Math., December, 2022

Preprocessing vertex-deletion problems: Characterizing graph properties by low-rank adjacencies.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2022

Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size.

[BibT_eX]

[DOI]

Algorithmica, 2022

Finding k-Secluded Trees Faster.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022

Kernelization for Feedback Vertex Set via Elimination Distance to a Forest.

[BibT_eX]

[DOI]

David Dekker

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022

Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Search-Space Reduction via Essential Vertices.

[BibT_eX]

[DOI]

Benjamin Merlin Bumpus

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Fine-grained Complexity Analysis of Two Classic TSP Variants.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs.

[BibT_eX]

[DOI]

Erik Jan van Leeuwen

SIAM J. Discret. Math., 2021

A Turing kernelization dichotomy for structural parameterizations of F-Minor-Free Deletion.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2021

Special Issue Dedicated to the 14th International Symposium on Parameterized and Exact Computation.

[BibT_eX]

[DOI]

Jan Arne Telle

Algorithmica, 2021

FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2021

Preprocessing to Reduce the Search Space: Antler Structures for Feedback Vertex Set.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2021

Vertex deletion parameterized by elimination distance and even less.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

On the Hardness of Compressing Weights.

[BibT_eX]

[DOI]

Shivesh Kumar Roy

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

2020

Polynomial kernels for hitting forbidden minors under structural parameterizations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth.

[BibT_eX]

[DOI]

Bas A. M. van Geffen

Arnoud A. W. M. de Kroon

Rolf Morel

J. Graph Algorithms Appl., 2020

Lower bounds for protrusion replacement by counting equivalence classes.

[BibT_eX]

[DOI]

Jules J. H. M. Wulms

Discret. Appl. Math., 2020

p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms.

[BibT_eX]

[DOI]

CoRR, 2020

Best-Case and Worst-Case Sparsifiability of Boolean CSPs.

[BibT_eX]

[DOI]

Hubie Chen

Algorithmica, 2020

Sparsification Lower Bounds for List H-Coloring.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel.

[BibT_eX]

[DOI]

Marin Bougeret

Ignasi Sau

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the Treewidth, Kernels, and Algorithms, 2020

2019

Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2019

Computing the chromatic number using graph decompositions via matrix rank.

[BibT_eX]

[DOI]

Jesper Nederlof

Theor. Comput. Sci., 2019

Parameterized Graph Algorithms & Data Reduction: Theory Meets Practice (NII Shonan Meeting 144).

[BibT_eX]

[DOI]

Christian Schulz

Hisao Tamaki

NII Shonan Meet. Rep., 2019

Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor.

[BibT_eX]

[DOI]

Marcin Wrochna

Algorithmica, 2019

Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials.

[BibT_eX]

[DOI]

Algorithmica, 2019

Hamiltonicity Below Dirac's Condition.

[BibT_eX]

[DOI]

László Kozma

Jesper Nederlof

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2019

Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Approximation and Kernelization for Chordal Vertex Deletion.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2018

Independent-set reconfiguration thresholds of hereditary graph classes.

[BibT_eX]

[DOI]

Mark de Berg

Archontia C. Giannopoulou

Debankur Mukherjee

Discret. Appl. Math., 2018

2017

Uniform Kernelization Complexity of Hitting Forbidden Minors.

[BibT_eX]

[DOI]

Daniel Lokshtanov

Saket Saurabh

ACM Trans. Algorithms, 2017

On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2017

Turing kernelization for finding long paths and cycles in restricted graph classes.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT.

[BibT_eX]

[DOI]

Algorithmica, 2017

Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor.

[BibT_eX]

[DOI]

Marcin Wrochna

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

2016

Constrained Bipartite Vertex Cover: The Easy Kernel is Essentially Tight.

[BibT_eX]

[DOI]

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

The First Parameterized Algorithms and Computational Experiments Challenge.

[BibT_eX]

[DOI]

Christian Komusiewicz

Frances A. Rosamond

Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

2015

On Sparsification for Computing Treewidth.

[BibT_eX]

[DOI]

Algorithmica, 2015

Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels.

[BibT_eX]

[DOI]

Dániel Marx

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT.

[BibT_eX]

[DOI]

Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2015, 2015

2014

FPT is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders.

[BibT_eX]

[DOI]

Michael R. Fellows

ACM Trans. Comput. Theory, 2014

Kernelization Lower Bounds by Cross-Composition.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2014

Preprocessing subgraph and minor problems: When does a small vertex cover help?

[BibT_eX]

[DOI]

Fedor V. Fomin

Michal Pilipczuk

J. Comput. Syst. Sci., 2014

A Near-Optimal Planarization Algorithm.

[BibT_eX]

[DOI]

Daniel Lokshtanov

Saket Saurabh

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

Parameterized complexity of vertex deletion into perfect graph classes.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Kernel bounds for path and cycle problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2013

Vertex Cover Kernelization Revisited - Upper and Lower Bounds for a Refined Parameter.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2013

Data reduction for graph coloring problems.

[BibT_eX]

[DOI]

Inf. Comput., 2013

Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity.

[BibT_eX]

[DOI]

Michael R. Fellows

Frances A. Rosamond

Eur. J. Comb., 2013

FPT Is Characterized by Useful Obstruction Sets.

[BibT_eX]

[DOI]

Michael R. Fellows

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2013

2012

Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2012

Kernel Bounds for Structural Parameterizations of Pathwidth.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory - SWAT 2012, 2012

2011

Connect the dot: Computing feed-links for network extension.

[BibT_eX]

[DOI]

J. Spatial Inf. Sci., 2011

Cross-Composition: A New Technique for Kernelization Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011

2010

Polynomial Kernels for Hard Problems on Disk Graphs.

[BibT_eX]

[DOI]