Eun Jung Kim

Tomás Masarík

CoRR, March, 2025

Flow-augmentation I: Directed graphs.

[BibT_eX]

[DOI]

J. ACM, February, 2025

CMSO-Transducing Tree-Like Graph Decompositions.

[BibT_eX]

[DOI]

Rutger Campbell

Bruno Guillon

Noleen Köhler

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

A tight meta-theorem for LOCAL certification of MSO2 properties within bounded treewidth graphs.

[BibT_eX]

[DOI]

Linda Cook

Tomás Masarík

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2025

Recognisability Equals Definability for Finitely Representable Matroids of Bounded Path-Width.

[BibT_eX]

[DOI]

Rutger Campbell

Bruno Guillon

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

Approximating Maximum Cut on Interval Graphs and Split Graphs Beyond Goemans-Williamson.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2025

2024

Flow-augmentation II: Undirected Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, April, 2024

On Weighted Graph Separation Problems and Flow Augmentation.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., March, 2024

Representing Matroids over the Reals is ∃ℝ-complete.

[BibT_eX]

[DOI]

Arnaud de Mesmay

Tillmann Miltzow

Discret. Math. Theor. Comput. Sci., 2024

2023

Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k.

[BibT_eX]

[DOI]

J. Comb. Theory B, May, 2023

Grundy Coloring and Friends, Half-Graphs, Bicliques.

[BibT_eX]

[DOI]

Algorithmica, 2023

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints.

[BibT_eX]

[DOI]

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

Bandwidth Parameterized by Cluster Vertex Deletion Number.

[BibT_eX]

[DOI]

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

2022

Complexity and algorithms for constant diameter augmentation problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

On weighted graph separation problems and flow-augmentation.

[BibT_eX]

[DOI]

CoRR, 2022

Directed flow-augmentation.

[BibT_eX]

[DOI]

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

Obstructions for Matroids of Path-Width at most k and Graphs of Linear Rank-Width at most k.

[BibT_eX]

[DOI]

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

Twin-width VI: the lens of contraction sequences.

[BibT_eX]

[DOI]

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

Twin-Width VIII: Delineation and Win-Wins.

[BibT_eX]

[DOI]

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

2021

EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs.

[BibT_eX]

[DOI]

J. ACM, 2021

On the tree-width of even-hole-free graphs.

[BibT_eX]

[DOI]

Eur. J. Comb., 2021

Solving hard cut problems via flow-augmentation.

[BibT_eX]

[DOI]

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

Twin-width II: small classes.

[BibT_eX]

[DOI]

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

Twin-Width and Polynomial Kernels.

[BibT_eX]

[DOI]

Proceedings of the 16th International Symposium on Parameterized and Exact Computation, 2021

Twin-width III: Max Independent Set, Min Dominating Set, and Coloring.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

A Constant-Factor Approximation for Weighted Bond Cover.

[BibT_eX]

[DOI]

Euiwoong Lee

Proceedings of the Approximation, 2021

2020

Twin-width III: Max Independent Set and Coloring.

[BibT_eX]

[DOI]

CoRR, 2020

Grundy Coloring & Friends, Half-Graphs, Bicliques.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

Towards Constant-Factor Approximation for Chordal / Distance-Hereditary Vertex Deletion.

[BibT_eX]

[DOI]

Jungho Ahn

Euiwoong Lee

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

Twin-width I: tractable FO model checking.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Grundy Distinguishes Treewidth from Pathwidth.

[BibT_eX]

[DOI]

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

2019

Token Sliding on Split Graphs.

[BibT_eX]

[DOI]

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

2018

Erdős-Pósa property of chordless cycles and its applications.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

New Results on Directed Edge Dominating Set.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Data-Compression for Parametrized Counting Problems on Sparse Graphs.

[BibT_eX]

[DOI]

Maria J. Serna

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

Sum-of-Products with Default Values: Algorithms and Complexity Results.

[BibT_eX]

[DOI]

Proceedings of the IEEE 30th International Conference on Tools with Artificial Intelligence, 2018

Finding Branch-Decompositions of Matroids, Hypergraphs, and More.

[BibT_eX]

[DOI]

Jisu Jeong

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017

The "Art of Trellis Decoding" Is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

Jisu Jeong

IEEE Trans. Inf. Theory, 2017

A Polynomial Kernel for Distance-Hereditary Vertex Deletion.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

2016

Constructive algorithm for path-width of matroids.

[BibT_eX]

[DOI]

Jisu Jeong

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

2015

A single-exponential FPT algorithm for the K4-minor cover problem.

[BibT_eX]

[DOI]

Geevarghese Philip

J. Comput. Syst. Sci., 2015

FPT Algorithm and Polynomial Kernel for Linear Rank-width One Vertex Deletion.

[BibT_eX]

[DOI]

CoRR, 2015

A polynomial kernel for Block Graph Vertex Deletion.

[BibT_eX]

[DOI]

CoRR, 2015

Recognizing k-equistable Graphs in FPT Time.

[BibT_eX]

[DOI]

Martin Milanic

Oliver Schaudt

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

An FPT 2-Approximation for Tree-cut Decomposition.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 13th International Workshop, 2015

Algorithmic Applications of Tree-Cut Width.

[BibT_eX]

[DOI]

Robert Ganian

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion.

[BibT_eX]

[DOI]

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

Complexity and Approximability of Parameterized MAX-CSPs.

[BibT_eX]

[DOI]

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

Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism.

[BibT_eX]

[DOI]

Ignasi Sau

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

A Polynomial Kernel for Block Graph Deletion.

[BibT_eX]

[DOI]

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

A Polynomial-Time Algorithm for Outerplanar Diameter Improvement.

[BibT_eX]

[DOI]

Mathias Weller

Proceedings of the Computer Science - Theory and Applications, 2015

Complexity of Grundy Coloring and Its Variants.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

2014

Satisfying more than half of a system of linear equations over GF(2): A multivariate approach.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2014

2013

On exact algorithms for the permutation CSP.

[BibT_eX]

[DOI]

Daniel Gonçalves

Theor. Comput. Sci., 2013

The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation.

[BibT_eX]

[DOI]

Sebastian Ordyniak

Proceedings of the Theory and Applications of Formal Argumentation, 2013

On Subexponential and FPT-Time Inapproximability.

[BibT_eX]

[DOI]

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

Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Subexponential and FPT-time Inapproximability of Independent Set and Related Problems

[BibT_eX]

[DOI]

Bruno Escoffier

Vangelis Th. Paschos

CoRR, 2012

A single-exponential FPT algorithm for the $K_4$-minor cover problem

[BibT_eX]

[DOI]

Geevarghese Philip

CoRR, 2012

A Single-Exponential FPT Algorithm for the K 4-Minor Cover Problem.

[BibT_eX]

[DOI]

Geevarghese Philip

Proceedings of the Algorithm Theory - SWAT 2012, 2012

Valued-Based Argumentation for Tree-like Value Graphs.

[BibT_eX]

[DOI]

Sebastian Ordyniak

Proceedings of the Computational Models of Argument, 2012

Don't Be Strict in Local Search!

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012

2011

Vertex Cover Problem Parameterized Above and Below Tight Bounds.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Solving MAX-r-SAT Above a Tight Lower Bound.

[BibT_eX]

[DOI]

Algorithmica, 2011

Improved Parameterized Algorithms for above Average Constraint Satisfaction.

[BibT_eX]

[DOI]

Ryan Williams

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

2010

Parameterized algorithms on digraph and constraint satisfaction problems.

[BibT_eX]

[DOI]

PhD thesis, 2010

Betweenness parameterized above tight lower bound.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2010

FPT algorithms and kernels for the Directed k-Leaf problem.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2010

Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2010

The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2010

Improved Parameterized Algorithms for Constraint Satisfaction

[BibT_eX]

[DOI]

Ryan Williams

CoRR, 2010

Minimum cost homomorphisms to locally semicomplete digraphs and quasi-transitive digraphs.

[BibT_eX]

[DOI]

Australas. J Comb., 2010

Systems of Linear Equations over F2 and Problems Parameterized above Average.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2010

Solving MAX-r-SAT Above a Tight Lower Bound.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming.

[BibT_eX]

[DOI]

Arezou Soleimanfallah

Anders Yeo

Proceedings of the Parameterized and Exact Computation - 5th International Symposium, 2010

Algorithms and Complexity Results for Persuasive Argumentation.

[BibT_eX]

[DOI]

Sebastian Ordyniak

Proceedings of the Computational Models of Argument: Proceedings of COMMA 2010, 2010

2009

Minimum leaf out-branching and related problems.

[BibT_eX]

[DOI]

Igor Razgon

Theor. Comput. Sci., 2009

On complexity of Minimum Leaf Out-Branching problem.

[BibT_eX]

[DOI]

Peter Dankelmann

Discret. Appl. Math., 2009

Ordinal Embedding Relaxations Parameterized Above Tight Lower Bound

[BibT_eX]

[DOI]

CoRR, 2009

Solving MAX-2-SAT Above a Tight Lower Bound

[BibT_eX]

[DOI]

CoRR, 2009

A Probabilistic Approach to Problems Parameterized Above Tight Lower Bound

[BibT_eX]

[DOI]

CoRR, 2009

A Probabilistic Approach to Problems Parameterized above or below Tight Bounds.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

Properly Coloured Cycles and Paths: Results and Open Problems.

[BibT_eX]

[DOI]

Proceedings of the Graph Theory, 2009

2008

Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization and Applications, 2008

Minimum Leaf Out-Branching Problems.

[BibT_eX]

[DOI]

Igor Razgon

Proceedings of the Algorithmic Aspects in Information and Management, 2008

2007

Minimum Cost Homomorphisms to Locally Semicomplete and Quasi-Transitive Digraphs

[BibT_eX]

[DOI]

CoRR, 2007

On the Complexity of the Minimum Cost Homomorphism Problem for Reflexive Multipartite Tournaments

[BibT_eX]

[DOI]