Eun Jung Kim

Euiwoong Lee

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

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2024

Representing Matroids over the Reals is ∃ℝ-complete.

[BibT_eX]

[DOI]

Arnaud de Mesmay

Tillmann Miltzow

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

CMSO-transducing tree-like graph decompositions.

[BibT_eX]

[DOI]

Rutger Campbell

Bruno Guillon

Noleen Köhler

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

New Results on Directed Edge Dominating Set.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 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

Algorithmic Applications of Tree-Cut Width.

[BibT_eX]

[DOI]

Robert Ganian

SIAM J. Discret. Math., December, 2022

Grundy Distinguishes Treewidth from Pathwidth.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., September, 2022

Complexity and algorithms for constant diameter augmentation problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

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

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2022

Twin-width I: Tractable FO Model Checking.

[BibT_eX]

[DOI]

J. ACM, 2022

On weighted graph separation problems and flow-augmentation.

[BibT_eX]

[DOI]

CoRR, 2022

Twin-width II: small classes.

[BibT_eX]

[DOI]

Comb. Theory, 2022

Twin-width and Polynomial Kernels.

[BibT_eX]

[DOI]

Algorithmica, 2022

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

[BibT_eX]

[DOI]

Jungho Ahn

Euiwoong Lee

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

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

[BibT_eX]

[DOI]

Jisu Jeong

SIAM J. Discret. Math., 2021

Token Sliding on Split Graphs.

[BibT_eX]

[DOI]

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

A Polynomial Kernel for Distance-Hereditary Vertex Deletion.

[BibT_eX]

[DOI]

Algorithmica, 2021

Solving hard cut problems via flow-augmentation.

[BibT_eX]

[DOI]

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

2020

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

[BibT_eX]

[DOI]

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

2018

Complexity of Grundy coloring and its variants.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2018

An FPT 2-Approximation for Tree-Cut Decomposition.

[BibT_eX]

[DOI]

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

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

Parameterized algorithms for min-max multiway cut and list digraph homomorphism.

[BibT_eX]

[DOI]

Ignasi Sau

J. Comput. Syst. Sci., 2017

A polynomial-time algorithm for Outerplanar Diameter Improvement.

[BibT_eX]

[DOI]

Mathias Weller

J. Comput. Syst. Sci., 2017

A Polynomial Kernel for Block Graph Deletion.

[BibT_eX]

[DOI]

Algorithmica, 2017

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

[BibT_eX]

[DOI]

Algorithmica, 2017

Complexity and Approximability of Parameterized MAX-CSPs.

[BibT_eX]

[DOI]

Algorithmica, 2017

2016

Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions.

[BibT_eX]

[DOI]

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

On Subexponential and FPT-Time Inapproximability.

[BibT_eX]

[DOI]

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

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

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

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

[BibT_eX]

[DOI]

Arezou Soleimanfallah

Anders Yeo

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

A probabilistic approach to problems parameterized above or below tight bounds.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

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

[BibT_eX]

[DOI]

Algorithmica, 2011

Algorithms and complexity results for persuasive argumentation.

[BibT_eX]

[DOI]

Sebastian Ordyniak

Artif. Intell., 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

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

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]