Michal Pilipczuk

ACM Trans. Comput. Theory, June, 2025

First-order transducibility among classes of sparse graphs.

[BibT_eX]

[DOI]

CoRR, May, 2025

Strong odd colorings in graph classes of bounded expansion.

[BibT_eX]

[DOI]

CoRR, May, 2025

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

Giannos Stamoulis

Michal Wlodarczyk

CoRR, May, 2025

On graphs coverable by chubby shortest paths.

[BibT_eX]

[DOI]

Meike Hatzel

CoRR, March, 2025

On coarse tree decompositions and coarse balanced separators.

[BibT_eX]

[DOI]

CoRR, February, 2025

Low rank MSO.

[BibT_eX]

[DOI]

Giannos Stamoulis

CoRR, February, 2025

Obstructions and dualities for matroid depth parameters.

[BibT_eX]

[DOI]

Kristýna Pekárková

CoRR, January, 2025

Graph classes through the lens of logic.

[BibT_eX]

[DOI]

CoRR, January, 2025

Polynomial-Time Approximation Schemes for Facility Location on Planar Graphs.

[BibT_eX]

[DOI]

Vincent Cohen-Addad

SIAM J. Comput., 2025

Transducing paths in graph classes with unbounded shrubdepth.

[BibT_eX]

[DOI]

Eur. J. Comb., 2025

Preface.

[BibT_eX]

[DOI]

Eur. J. Comb., 2025

Embedding Planar Graphs into Graphs of Treewidth O (log3 n ).

[BibT_eX]

[DOI]

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

Box-Reachability in Vector Addition Systems.

[BibT_eX]

[DOI]

Proceedings of the Reachability Problems - 19th International Conference, 2025

3D-grids are not transducible from planar graphs.

[BibT_eX]

[DOI]

Filip Pokrývka

Proceedings of the 40th Annual ACM/IEEE Symposium on Logic in Computer Science, 2025

Faster Diameter Computation in Graphs of Bounded Euler Genus.

[BibT_eX]

[DOI]

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

Separability Properties of Monadically Dependent Graph Classes.

[BibT_eX]

[DOI]

Édouard Bonnet

Samuel Braunfeld

Ioannis Eleftheriadis

Colin Geniet

Nikolas Mählmann

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

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

Embedding Planar Graphs into Graphs of Treewidth O(log3 n).

[BibT_eX]

[DOI]

CoRR, 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

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

Minor Containment and Disjoint Paths in Almost-Linear Time.

[BibT_eX]

[DOI]

Tuukka Korhonen

Giannos Stamoulis

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

First-Order Model Checking on Monadically Stable Graph Classes.

[BibT_eX]

[DOI]

Jan Dreier

Ioannis Eleftheriadis

Proceedings of the 65th IEEE Annual Symposium on Foundations of 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

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

On the independence number of intersection graphs of axis-parallel segments.

[BibT_eX]

[DOI]

J. Comput. Geom., 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

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

Flipper Games for Monadically Stable Graph Classes.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2022

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

[BibT_eX]

[DOI]

SIAM J. Comput., 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

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

[BibT_eX]

[DOI]

CoRR, 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]

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]

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

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

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 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

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

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

Dynamic Data Structures for Timed Automata Acceptance.

[BibT_eX]

[DOI]

Proceedings of the 16th International Symposium on Parameterized and Exact Computation, 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

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

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

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

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

[BibT_eX]

[DOI]

Algorithmica, 2020

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

[BibT_eX]

[DOI]

Jesper Nederlof

Céline M. F. Swennenhuis

Proceedings of the Graph-Theoretic Concepts in Computer Science, 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

Shorter Labeling Schemes for Planar Graphs.

[BibT_eX]

[DOI]

Cyril Gavoille

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

On Polynomial Recursive Sequences.

[BibT_eX]

[DOI]

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

Finding Large H-Colorable Subgraphs in Hereditary Graph Classes.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Computing Tree Decompositions.

[BibT_eX]

[DOI]

Proceedings of the Treewidth, Kernels, and Algorithms, 2020

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

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

[BibT_eX]

[DOI]

Dusan Knop

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

Progressive Algorithms for Domination and Independence.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.

[BibT_eX]

[DOI]

Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 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

Hardness of Approximation for H-free Edge Modification Problems.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 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

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

Definable decompositions for graphs of bounded linear cliquewidth.

[BibT_eX]

[DOI]

Martin Grohe

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

First-Order Interpretations of Bounded Expansion Classes.

[BibT_eX]

[DOI]

Stephan Kreutzer

Jaroslav Nesetril

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 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

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

[BibT_eX]

[DOI]

Erik Jan van Leeuwen

Andreas Wiese

Proceedings of the 26th Annual European Symposium on Algorithms, 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

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

On Low Rank-Width Colorings.

[BibT_eX]

[DOI]

O-joung Kwon

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

Optimizing Tree Decompositions in MSO.

[BibT_eX]

[DOI]

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Fully polynomial-time parameterized computations for graphs and matrices of low treewidth.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

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

[BibT_eX]

[DOI]

Jean-Florent Raymond

Dimitrios M. Thilikos

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 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

Tight Lower Bounds for the Complexity of Multicoloring.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 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

A ck n 5-Approximation Algorithm for Treewidth.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

On Ultralimits of Sparse Graph Classes.

[BibT_eX]

[DOI]

Electron. J. Comb., 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

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

[BibT_eX]

[DOI]

Fernando Sánchez Villaamil

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 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

Subexponential parameterized algorithm for Interval Completion.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 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]

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

Cutwidth: Obstructions and Algorithmic Aspects.

[BibT_eX]

[DOI]

Jean-Florent Raymond

Dimitrios M. Thilikos

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

Shortest Paths in One-Counter Systems.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Science and Computation Structures, 2016

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

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 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

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

Polynomial Kernelization for Removing Induced Claws and Diamonds.

[BibT_eX]

[DOI]

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

Linear Kernels for Outbranching Problems in Sparse Digraphs.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2015, 2015

Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints.

[BibT_eX]

[DOI]

Ariel Gabizon

Daniel Lokshtanov

Proceedings of the Algorithms - ESA 2015, 2015

A Polynomial Kernel for Trivially Perfect Editing.

[BibT_eX]

[DOI]

Pål Grønås Drange

Proceedings of the Algorithms - ESA 2015, 2015

How to Hunt an Invisible Rabbit on a Graph.

[BibT_eX]

Tatjana V. Abramovskaya

Petr A. Golovach

Proceedings of the 13th Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2015

Parameterized Algorithms

[BibT_eX]

[DOI]

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

2014

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

[BibT_eX]

[DOI]

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

Minimum bisection is fixed parameter tractable.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 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, 2014

Exploring Subexponential Parameterized Complexity of Completion Problems.

[BibT_eX]

[DOI]

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

Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Synthesizing transformations from XML schema mappings.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

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

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

A Subexponential Parameterized Algorithm for Proper Interval Completion.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2014, 2014

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

Known algorithms for EDGE CLIQUE COVER are probably optimal.

[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

How to Eliminate a Graph.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

Sitting Closer to Friends Than Enemies, Revisited.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

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

[BibT_eX]

[DOI]

Proceedings of the LATIN 2012: Theoretical Informatics, 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

Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?

[BibT_eX]

[DOI]

Bart M. P. Jansen

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

Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Minimizing Rosenthal Potential in Multicast Games.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Clique Cover and Graph Separation: New Incompressibility Results.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Designing FPT Algorithms for Cut Problems Using Randomized Contractions.

[BibT_eX]

[DOI]

Rajesh Hemant Chitnis

MohammadTaghi Hajiaghayi

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 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

Parameterized Complexity of Eulerian Deletion Problems.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 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

On Multiway Cut Parameterized above Lower Bounds.

[BibT_eX]

[DOI]

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

On Cutwidth Parameterized by Vertex Cover.

[BibT_eX]

[DOI]

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

On the Hardness of Losing Width.

[BibT_eX]

[DOI]

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

Subset Feedback Vertex Set Is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time.

[BibT_eX]

[DOI]

Johan M. M. van Rooij

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Scheduling Partially Ordered Jobs Faster Than 2 n.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2011, 2011

2010

Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

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

[BibT_eX]

[DOI]