Michal Pilipczuk

Eur. J. Comb., 2025

Preface.

[BibT_eX]

[DOI]

Eur. J. Comb., 2025

2024

On Polynomial Recursive Sequences.

[BibT_eX]

[DOI]

Theory Comput. Syst., August, 2024

Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\boldsymbol{H}$-Free Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., February, 2024

Erdös-Pósa property of tripods in directed graphs.

[BibT_eX]

[DOI]

CoRR, 2024

Half-integral Erdös-Pósa property for non-null S-T paths.

[BibT_eX]

[DOI]

CoRR, 2024

Minor Containment and Disjoint Paths in almost-linear time.

[BibT_eX]

[DOI]

Tuukka Korhonen

Giannos Stamoulis

CoRR, 2024

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Parameterized and Approximation Algorithms for Coverings Points with Segments in the Plane.

[BibT_eX]

[DOI]

Katarzyna Anna Kowalska

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard.

[BibT_eX]

[DOI]

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Simple and tight complexity lower bounds for solving Rabin games.

[BibT_eX]

[DOI]

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Shortest Disjoint Paths on a Grid.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Fully dynamic approximation schemes on planar and apex-minor-free graphs.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Cliquewidth and Dimension.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

A polynomial-time OPTɛ-approximation algorithm for maximum independent set of connected subgraphs in a planar graph.

[BibT_eX]

[DOI]

Jana Cslovjecsek

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Parameterized algorithms for block-structured integer programs with large entries.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Sparse induced subgraphs in P6-free graphs.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Elementary first-order model checking for sparse graphs.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

Parameterized Dynamic Data Structure for Split Completion.

[BibT_eX]

[DOI]

Konrad Majewski

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments.

[BibT_eX]

[DOI]

Jana Cslovjecsek

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

Partitioning edges of a planar graph into linear forests and a matching.

[BibT_eX]

[DOI]

J. Graph Theory, November, 2023

Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space.

[BibT_eX]

[DOI]

Jesper Nederlof

Céline M. F. Swennenhuis

SIAM J. Discret. Math., September, 2023

Graphs of bounded twin-width are quasi-polynomially χ-bounded.

[BibT_eX]

[DOI]

J. Comb. Theory B, July, 2023

On the Effect of Symmetry Requirement for Rendezvous on the Complete Graph.

[BibT_eX]

[DOI]

Jean-Sébastien Sereni

Richard Weber

Math. Oper. Res., May, 2023

First-Order Model Checking on Monadically Stable Graph Classes.

[BibT_eX]

[DOI]

Jan Dreier

Ioannis Eleftheriadis

CoRR, 2023

A polynomial-time OPTε-approximation algorithm for maximum independent set of connected subgraphs in a planar graph.

[BibT_eX]

[DOI]

Jana Cslovjecsek

CoRR, 2023

A parameterized approximation scheme for the 2D-Knapsack problem with wide items.

[BibT_eX]

[DOI]

Mathieu Mari

Timothé Picavet

CoRR, 2023

Sparse induced subgraphs in P_6-free graphs.

[BibT_eX]

[DOI]

CoRR, 2023

Bounding Generalized Coloring Numbers of Planar Graphs Using Coin Models.

[BibT_eX]

[DOI]

Jesper Nederlof

Electron. J. Comb., 2023

Dynamic Data Structures for Parameterized String Problems.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex Number.

[BibT_eX]

[DOI]

Konrad Majewski

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

On Rational Recursive Sequences.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Simpler and faster algorithms for detours in planar digraphs.

[BibT_eX]

[DOI]

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items.

[BibT_eX]

[DOI]

Mathieu Mari

Timothé Picavet

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

Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes.

[BibT_eX]

[DOI]

Pierre Ohlmann

Wojciech Przybyszewski

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Flipper Games for Monadically Stable Graph Classes.

[BibT_eX]

[DOI]

Wojciech Przybyszewski

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters.

[BibT_eX]

[DOI]

Hans L. Bodlaender

Carla Groenland

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Dynamic treewidth.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth.

[BibT_eX]

[DOI]

Benjamin Bergougnoux

Vera Chekan

Robert Ganian

Mamadou Moustapha Kanté

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

2022

Shorter Labeling Schemes for Planar Graphs.

[BibT_eX]

[DOI]

Cyril Gavoille

SIAM J. Discret. Math., September, 2022

Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2022

Polynomial-time Algorithm for Maximum Weight Independent Set on P6-free Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2022

Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time.

[BibT_eX]

[DOI]

Johan M. M. van Rooij

ACM Trans. Algorithms, 2022

A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

Optimizing tree decompositions in MSO.

[BibT_eX]

[DOI]

Mikolaj Bojanczyk

Log. Methods Comput. Sci., 2022

On objects dual to tree-cut decompositions.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2022

Degeneracy of Pt-free and C⩾t-free graphs with no large complete bipartite subgraphs.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2022

On the Erdős-Pósa property for immersions and topological minors in tournaments.

[BibT_eX]

[DOI]

Lukasz Bozyk

Discret. Math. Theor. Comput. Sci., 2022

On digraphs without onion star immersions.

[BibT_eX]

[DOI]

CoRR, 2022

Highly unbreakable graph with a fixed excluded minor are almost rigid.

[BibT_eX]

[DOI]

CoRR, 2022

Independence number of intersection graphs of axis-parallel segments.

[BibT_eX]

[DOI]

CoRR, 2022

Graphs of bounded twin-width are quasi-polynomially χ-bounded.

[BibT_eX]

[DOI]

CoRR, 2022

Dynamic Data Structures for Timed Automata Acceptance.

[BibT_eX]

[DOI]

Algorithmica, 2022

Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor.

[BibT_eX]

[DOI]

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

Compact Representation for Matrices of Bounded Twin-Width.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Isolation Schemes for Problems on Decomposable Graphs.

[BibT_eX]

[DOI]

Jesper Nederlof

Céline M. F. Swennenhuis

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Stable graphs of bounded twin-width.

[BibT_eX]

[DOI]

Jakub Gajarský

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

Treelike Decompositions for Transductions of Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

On the Complexity of Problems on Tree-Structured Graphs.

[BibT_eX]

[DOI]

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

Algorithms and Data Structures for First-Order Logic with Connectivity Under Vertex Failures.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Twin-Width and Types.

[BibT_eX]

[DOI]

Jakub Gajarský

Wojciech Przybyszewski

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Computing Treedepth in Polynomial Space and Linear FPT Time.

[BibT_eX]

[DOI]

Wojciech Nadara

Marcin Smulewicz

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

Polynomial Kernel for Immersion Hitting in Tournaments.

[BibT_eX]

[DOI]

Lukasz Bozyk

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

2021

Randomized Contractions Meet Lean Decompositions.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes.

[BibT_eX]

[DOI]

Jean-Florent Raymond

Dimitrios M. Thilikos

SIAM J. Discret. Math., 2021

Finding Large H-Colorable Subgraphs in Hereditary Graph Classes.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2021

Erdös-Hajnal Properties for Powers of Sparse Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2021

Definable decompositions for graphs of bounded linear cliquewidth.

[BibT_eX]

[DOI]

Mikolaj Bojanczyk

Martin Grohe

Log. Methods Comput. Sci., 2021

Polynomial bounds for centered colorings on proper minor-closed graph classes.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2021

Kernelization and approximation of distance-r independent sets on nowhere dense graphs.

[BibT_eX]

[DOI]

Eur. J. Comb., 2021

Sparsity in Algorithms, Combinatorics and Logic (Dagstuhl Seminar 21391).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2021

Maintaining CMSO2 properties on dynamic structures with bounded feedback vertex number.

[BibT_eX]

[DOI]

Konrad Majewski

CoRR, 2021

Covering Minimal Separators and Potential Maximal Cliques in $P_t$-Free Graphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2021

Jones' Conjecture in Subcubic Graphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2021

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.

[BibT_eX]

[DOI]

Algorithmica, 2021

Finding large induced sparse subgraphs in c>t -free graphs in quasipolynomial time.

[BibT_eX]

[DOI]

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

Quasi-polynomial-time algorithm for Independent Set in Pt-free graphs via shrinking the space of induced paths.

[BibT_eX]

[DOI]

Pawel Rzazewski

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Rankwidth meets stability.

[BibT_eX]

[DOI]

Jaroslav Nesetril

Roman Rabinovich

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles.

[BibT_eX]

[DOI]

Jiehua Chen

Wojciech Czerwinski

Yann Disser

Andreas Emil Feldmann

Bartlomiej Wróblewski

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints.

[BibT_eX]

[DOI]

Dusan Knop

ACM Trans. Comput. Theory, 2020

First-Order Interpretations of Bounded Expansion Classes.

[BibT_eX]

[DOI]

Jakub Gajarský

Stephan Kreutzer

Jaroslav Nesetril

ACM Trans. Comput. Log., 2020

Model-Checking on Ordered Structures.

[BibT_eX]

[DOI]

Kord Eickmeyer

Jan van den Heuvel

Ken-ichi Kawarabayashi

Stephan Kreutzer

ACM Trans. Comput. Log., 2020

Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

On low rank-width colorings.

[BibT_eX]

[DOI]

O-joung Kwon

Eur. J. Comb., 2020

Quasi-polynomial-time algorithm for Independent Set in Pt-free and C>t-free graphs via shrinking the space of connecting subgraphs.

[BibT_eX]

[DOI]

Pawel Rzazewski

CoRR, 2020

On Dynamic Parameterized k-Path.

[BibT_eX]

[DOI]

Jiehua Chen

Wojciech Czerwinski

Yann Disser

Andreas Emil Feldmann

Bartlomiej Wróblewski

CoRR, 2020

VC density of set systems defnable in tree-like graphs.

[BibT_eX]

[DOI]

Adam Paszke

CoRR, 2020

Covering minimal separators and potential maximal cliques in Pt-free graphs.

[BibT_eX]

[DOI]

CoRR, 2020

The monitoring problem for timed automata.

[BibT_eX]

[DOI]

CoRR, 2020

On the effect of symmetry requirement for rendezvous on the complete graph.

[BibT_eX]

[DOI]

Jean-Sébastien Sereni

CoRR, 2020

Clustering Powers of Sparse Graphs.

[BibT_eX]

[DOI]

Jaroslav Nesetril

Xuding Zhu

Electron. J. Comb., 2020

Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs.

[BibT_eX]

[DOI]

Erik Jan van Leeuwen

Andreas Wiese

Algorithmica, 2020

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

[BibT_eX]

[DOI]

Algorithmica, 2020

An exponential time parameterized algorithm for planar disjoint paths.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

VC Density of Set Systems Definable in Tree-Like Graphs.

[BibT_eX]

[DOI]

Adam Paszke

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

Computing Tree Decompositions.

[BibT_eX]

[DOI]

Proceedings of the Treewidth, Kernels, and Algorithms, 2020

2019

Tight Lower Bounds for the Complexity of Multicoloring.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2019

Minimum Bisection Is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Shortest paths in one-counter systems.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2019

Strong immersion is a well-quasi-ordering for semicomplete digraphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2019

On width measures and topological problems on semi-complete digraphs.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2019

Jones' Conjecture in subcubic graphs.

[BibT_eX]

[DOI]

CoRR, 2019

Graphs of bounded cliquewidth are polynomially χ-bounded.

[BibT_eX]

[DOI]

CoRR, 2019

Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs.

[BibT_eX]

[DOI]

CoRR, 2019

Edge Bipartization Faster than $$2^k$$ 2 k.

[BibT_eX]

[DOI]

Algorithmica, 2019

Cutwidth: Obstructions and Algorithmic Aspects.

[BibT_eX]

[DOI]

Jean-Florent Raymond

Dimitrios M. Thilikos

Algorithmica, 2019

Progressive Algorithms for Domination and Independence.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Integer Programming and Incidence Treedepth.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2019

A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs.

[BibT_eX]

[DOI]

Vincent Cohen-Addad

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs.

[BibT_eX]

[DOI]

Vincent Cohen-Addad

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

On Geometric Set Cover for Orthants.

[BibT_eX]

[DOI]

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

Reachability for Bounded Branching VASS.

[BibT_eX]

[DOI]

Filip Mazowiecki

Proceedings of the 30th International Conference on Concurrency Theory, 2019

2018

On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2018

Hardness of Approximation for H-free Edge Modification Problems.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2018

Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Subexponential Parameterized Algorithm for Interval Completion.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

Below All Subsets for Minimal Connected Dominating Set.

[BibT_eX]

[DOI]

Daniel Lokshtanov

Saket Saurabh

SIAM J. Discret. Math., 2018

Randomized contractions meet lean decompositions.

[BibT_eX]

[DOI]

CoRR, 2018

Parameterized circuit complexity of model checking first-order logic on sparse structures.

[BibT_eX]

[DOI]

CoRR, 2018

A Polynomial Kernel for Trivially Perfect Editing.

[BibT_eX]

[DOI]

Pål Grønås Drange

Algorithmica, 2018

On Directed Feedback Vertex Set Parameterized by Treewidth.

[BibT_eX]

[DOI]

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

On the number of types in sparse graphs.

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

Parameterized circuit complexity of model-checking on sparse structures.

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Planar Digraphs.

[BibT_eX]

[DOI]

Proceedings of the Classes of Directed Graphs., 2018

2017

Hardness of Approximation for Strip Packing.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2017

Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Polynomial Kernelization for Removing Induced Claws and Diamonds.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

Hitting forbidden subgraphs in graphs of bounded treewidth.

[BibT_eX]

[DOI]

Inf. Comput., 2017

On Wideness and Stability.

[BibT_eX]

[DOI]

CoRR, 2017

Polynomial-time algorithm for Maximum Weight Independent Set on $P_6$-free graphs.

[BibT_eX]

[DOI]

CoRR, 2017

Strong immersion is a well-quasi-ordering for semi-complete digraphs.

[BibT_eX]

[DOI]

CoRR, 2017

Linear Kernels for Outbranching Problems in Sparse Digraphs.

[BibT_eX]

[DOI]

Algorithmica, 2017

Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking.

[BibT_eX]

[DOI]

Erik Jan van Leeuwen

Andreas Wiese

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

On Definable and Recognizable Properties of Graphs of Bounded Treewidth (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Model-checking for successor-invariant first-order formulas on graph classes of bounded expansion.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs.

[BibT_eX]

[DOI]

Kord Eickmeyer

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Exploring the Complexity of Layout Parameters in Tournaments and Semi-Complete Digraphs.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Lower Bounds Based on the Exponential Time Hypothesis: Edge Clique Cover.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Exact Algorithms for Induced Subgraph Problems.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Computing Cutwidth and Pathwidth of Semi-complete Digraphs.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Known Algorithms for Edge Clique Cover are Probably Optimal.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Designing FPT Algorithms for Cut Problems Using Randomized Contractions.

[BibT_eX]

[DOI]

Rajesh Chitnis

MohammadTaghi Hajiaghayi

SIAM J. Comput., 2016

A ck n 5-Approximation Algorithm for Treewidth.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

How to hunt an invisible rabbit on a graph.

[BibT_eX]

[DOI]

Tatjana V. Abramovskaya

Petr A. Golovach

Eur. J. Comb., 2016

On Ultralimits of Sparse Graph Classes.

[BibT_eX]

[DOI]

Electron. J. Comb., 2016

On Group Feedback Vertex Set Parameterized by the Size of the Cutset.

[BibT_eX]

[DOI]

Fernando Sánchez Villaamil

Algorithmica, 2016

Largest Chordal and Interval Subgraphs Faster than $$2^n$$ 2 n.

[BibT_eX]

[DOI]

Algorithmica, 2016

Lower Bounds for Approximation Schemes for Closest String.

[BibT_eX]

[DOI]

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Kernelization and Sparseness: the Case of Dominating Set.

[BibT_eX]

[DOI]

Pål Grønås Drange

Markus Sortland Dregi

Saket Saurabh

Somnath Sikdar

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

Schema Validation via Streaming Circuits.

[BibT_eX]

[DOI]

Filip Murlak

Charles Paperman

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

The Generalised Colouring Numbers on Classes of Bounded Expansion.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Definability equals recognizability for graphs of bounded treewidth.

[BibT_eX]

[DOI]

Mikolaj Bojanczyk

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

Edge Bipartization Faster Than 2^k.

[BibT_eX]

[DOI]

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

Hardness of Approximation for H-Free Edge Modification Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

Exploring the Subexponential Complexity of Completion Problems.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2015

Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2015

A Subexponential Parameterized Algorithm for Proper Interval Completion.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2015

Minimizing Rosenthal Potential in Multicast Games.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2015

Sitting Closer to Friends than Enemies, Revisited.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2015

Edge Bipartization faster than 2k.

[BibT_eX]

[DOI]

CoRR, 2015

Modifying a Graph Using Vertex Elimination.

[BibT_eX]

[DOI]

Algorithmica, 2015

Computing Tree-Depth Faster Than 2n.

[BibT_eX]

[DOI]

Algorithmica, 2015

Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints.

[BibT_eX]

[DOI]

Ariel Gabizon

Daniel Lokshtanov

Proceedings of the Algorithms - ESA 2015, 2015

Parameterized Algorithms

[BibT_eX]

[DOI]

Springer, ISBN: 978-3-319-21275-3, 2015

2014

Clique Cover and Graph Separation: New Incompressibility Results.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2014

On the Hardness of Losing Width.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2014

Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2014

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

[BibT_eX]

[DOI]

Bart M. P. Jansen

J. Comput. Syst. Sci., 2014

Representative sets for multisets.

[BibT_eX]

[DOI]

Ariel Gabizon

Daniel Lokshtanov

Fernando Sánchez Villaamil

CoRR, 2014

Kernelization and Sparseness: the case of Dominating Set.

[BibT_eX]

[DOI]

Somnath Sikdar

CoRR, 2014

Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n.

[BibT_eX]

[DOI]

Algorithmica, 2014

Scheduling Partially Ordered Jobs Faster than 2 n.

[BibT_eX]

[DOI]

Algorithmica, 2014

Parameterized Complexity of Eulerian Deletion Problems.

[BibT_eX]

[DOI]

Algorithmica, 2014

On Cutwidth Parameterized by Vertex Cover.

[BibT_eX]

[DOI]

Algorithmica, 2014

Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Exploring Subexponential Parameterized Complexity of Completion Problems.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Synthesizing transformations from XML schema mappings.

[BibT_eX]

[DOI]

Proceedings of the Proc. 17th International Conference on Database Theory (ICDT), 2014

2013

On multiway cut parameterized above lower bounds.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2013

Subset Feedback Vertex Set Is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2013

A O(c^k n) 5-Approximation Algorithm for Treewidth

[BibT_eX]

[DOI]

CoRR, 2013

Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Tight bounds for Parameterized Complexity of Cluster Editing.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Jungles, bundles, and fixed parameter tractability.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Computing Tree-Depth Faster Than 2 n.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

An O(c^k n) 5-Approximation Algorithm for Treewidth.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2013, 2013

Largest Chordal and Interval Subgraphs Faster Than 2 n.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2013, 2013

2012

A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More).

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Some results on Vizing's conjecture and related problems.

[BibT_eX]

[DOI]

Riste Skrekovski

Discret. Appl. Math., 2012

Kernelization hardness of connectivity problems in d-degenerate graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2012

An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion.

[BibT_eX]

[DOI]

Algorithmica, 2012

How to Eliminate a Graph.

[BibT_eX]

[DOI]

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

Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

2011

Dominating set is fixed parameter tractable in claw-free graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Subexponential fixed-parameter tractability of cluster editing

[BibT_eX]

[DOI]

CoRR, 2011

The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

2010

Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs.

[BibT_eX]

[DOI]