Magnus Wahlström

CoRR, 2024

Representative set statements for delta-matroids and the Mader delta-matroid.

[BibT_eX]

[DOI]

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

Determinantal Sieving.

[BibT_eX]

[DOI]

Eduard Eiben

Tomohiro Koana

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

Parameterized Complexity of MinCSP over the Point Algebra.

[BibT_eX]

[DOI]

George Osipov

Marcin Pilipczuk

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

2023

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

[BibT_eX]

[DOI]

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

Preference swaps for the stable matching problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2023

Almost Consistent Systems of Linear Equations.

[BibT_eX]

[DOI]

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

Parameterized Complexity of Equality MinCSP.

[BibT_eX]

[DOI]

George Osipov

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

2022

The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2022

Quasipolynomial Multicut-mimicking Networks and Kernels for Multiway Cut Problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2022

Many-visits TSP revisited.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2022

On weighted graph separation problems and flow-augmentation.

[BibT_eX]

[DOI]

CoRR, 2022

Component Order Connectivity in Directed Graphs.

[BibT_eX]

[DOI]

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

On the Parameterized Complexity of Symmetric Directed Multicut.

[BibT_eX]

[DOI]

Eduard Eiben

Clément Rambaud

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

2021

r-Simple k-Path and Related Problems Parameterized by k/r.

[BibT_eX]

[DOI]

Meirav Zehavi

ACM Trans. Algorithms, 2021

Randomized Contractions Meet Lean Decompositions.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

Parameterized Pre-Coloring Extension and List Coloring Problems.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2021

Solving hard cut problems via flow-augmentation.

[BibT_eX]

[DOI]

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

Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs.

[BibT_eX]

[DOI]

Zhiyang He

Jason Li

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

2020

Sparsification of SAT and CSP Problems via Tractable Extensions.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2020

Alternative parameterizations of Metric Dimension.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Representative Sets and Irrelevant Vertices: New Tools for Kernelization.

[BibT_eX]

[DOI]

J. ACM, 2020

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

[BibT_eX]

[DOI]

CoRR, 2020

Multi-budgeted Directed Cuts.

[BibT_eX]

[DOI]

Algorithmica, 2020

On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems.

[BibT_eX]

[DOI]

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

2019

Path-contractions, edge deletions and connectivity preservation.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2019

On r-Simple k-Path and Related Problems Parameterized by k/r.

[BibT_eX]

[DOI]

Meirav Zehavi

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

2018

Directed Multicut is W[1]-hard, Even for Four Terminal Pairs.

[BibT_eX]

[DOI]

Marcin Pilipczuk

ACM Trans. Comput. Theory, 2018

Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2018

k-distinct in- and out-branchings in digraphs.

[BibT_eX]

[DOI]

Felix Reidl

J. Comput. Syst. Sci., 2018

Which NP-Hard SAT and CSP Problems Admit Exponentially Improved Algorithms?

[BibT_eX]

[DOI]

CoRR, 2018

Parameterized Algorithms for Zero Extension and Metric Labelling Problems.

[BibT_eX]

[DOI]

Felix Reidl

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

Euler Digraphs.

[BibT_eX]

[DOI]

Proceedings of the Classes of Directed Graphs., 2018

2017

The power of primitive positive definitions with polynomially many variables.

[BibT_eX]

[DOI]

J. Log. Comput., 2017

Rural postman parameterized by the number of components of required edges.

[BibT_eX]

[DOI]

Anders Yeo

J. Comput. Syst. Sci., 2017

Odd properly colored cycles in edge-colored graphs.

[BibT_eX]

[DOI]

Bin Sheng

Discret. Math., 2017

Acyclicity in edge-colored graphs.

[BibT_eX]

[DOI]

Discret. Math., 2017

Chinese Postman Problem on edge-colored multigraphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2017

Randomization in Parameterized Complexity (Dagstuhl Seminar 17041).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2017

Kirchoff Matrices and Pfaffians to Design Deterministic Polynomial-Space Parameterized Algorithms.

[BibT_eX]

[DOI]

CoRR, 2017

LP-branching algorithms based on biased graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

k-Distinct In- and Out-Branchings in Digraphs.

[BibT_eX]

[DOI]

Felix Reidl

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

Kernelization of Constraint Satisfaction Problems: A Study Through Universal Algebra.

[BibT_eX]

[DOI]

Proceedings of the Principles and Practice of Constraint Programming, 2017

2016

How to Generate Randomized Roundings with Dependencies and How to Derandomize Them.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Engineering - Selected Results and Surveys, 2016

Kernelization, Matroid Methods.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems.

[BibT_eX]

[DOI]

Dániel Marx

ACM Trans. Comput. Theory, 2016

On the Workflow Satisfiability Problem with Class-Independent Constraints for Hierarchical Organizations.

[BibT_eX]

[DOI]

ACM Trans. Priv. Secur., 2016

On Problems as Hard as CNF-SAT.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth.

[BibT_eX]

[DOI]

Mark Jones

SIAM J. Discret. Math., 2016

Half-integrality, LP-branching, and FPT Algorithms.

[BibT_eX]

[DOI]

Yoichi Iwata

Yuichi Yoshida

SIAM J. Comput., 2016

Tight lower bounds for the Workflow Satisfiability Problem based on the Strong Exponential Time Hypothesis.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2016

Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem.

[BibT_eX]

[DOI]

Algorithmica, 2016

Directed multicut is W[1]-hard, even for four terminal pairs.

[BibT_eX]

[DOI]

Marcin Pilipczuk

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

2015

Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2015

A Completeness Theory for Polynomial (Turing) Kernelization.

[BibT_eX]

[DOI]

Algorithmica, 2015

Bounded Bases of Strong Partial Clones.

[BibT_eX]

[DOI]

Bruno Zanuttini

Proceedings of the 2015 IEEE International Symposium on Multiple-Valued Logic, 2015

Structural Parameterizations of the Mixed Chinese Postman Problem.

[BibT_eX]

[DOI]

Mark Jones

Proceedings of the Algorithms - ESA 2015, 2015

2014

Clique Cover and Graph Separation: New Incompressibility Results.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2014

Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2014

Randomized Rounding in the Presence of a Cardinality Constraint.

[BibT_eX]

[DOI]

ACM J. Exp. Algorithmics, 2014

Parameterized Directed k-Chinese Postman Problem and k Arc-Disjoint Cycles Problem on Euler Digraphs.

[BibT_eX]

[DOI]

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

Half-integrality, LP-branching and FPT Algorithms.

[BibT_eX]

[DOI]

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

Polynomially Closed Co-clones.

[BibT_eX]

[DOI]

Proceedings of the IEEE 44th International Symposium on Multiple-Valued Logic, 2014

2013

Two edge modification problems without polynomial kernels.

[BibT_eX]

[DOI]

Discret. Optim., 2013

Parameterized Rural Postman and Conjoining Bipartite Matching Problems.

[BibT_eX]

[DOI]

Anders Yeo

CoRR, 2013

Parameterized Two-Player Nash Equilibrium.

[BibT_eX]

[DOI]

Algorithmica, 2013

Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem.

[BibT_eX]

[DOI]

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

2012

A New Randomized Algorithm to Approximate the Star Discrepancy Based on Threshold Accepting.

[BibT_eX]

[DOI]

Michael Gnewuch

Carola Winzen

SIAM J. Numer. Anal., 2012

Hardness of discrepancy computation and ε-net verification in high dimension.

[BibT_eX]

[DOI]

J. Complex., 2012

Subexponential Parameterized Odd Cycle Transversal on Planar Graphs.

[BibT_eX]

[DOI]

Daniel Lokshtanov

Saket Saurabh

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

New Plain-Exponential Time Classes for Graph Homomorphism.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

On Problems as Hard as CNFSAT

[BibT_eX]

[DOI]

CoRR, 2011

Hierarchies of Inefficient Kernelizability

[BibT_eX]

[DOI]

CoRR, 2011

Hardness of discrepancy computation and epsilon-net verification in high dimension

[BibT_eX]

[DOI]

CoRR, 2011

A Randomized Algorithm Based on Threshold Accepting to Approximate the Star Discrepancy

[BibT_eX]

[DOI]

Michael Gnewuch

Carola Winzen

CoRR, 2011

Dependent Randomized Rounding: The Bipartite Case.

[BibT_eX]

[DOI]

Marvin Künnemann

Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments, 2011

2010

Algorithmic construction of low-discrepancy point sets via dependent randomized rounding.

[BibT_eX]

[DOI]

Michael Gnewuch

J. Complex., 2010

Randomized Rounding for Routing and Covering Problems: Experiments and Improvements.

[BibT_eX]

[DOI]

Marvin Künnemann

Proceedings of the Experimental Algorithms, 9th International Symposium, 2010

Preprocessing of Min Ones Problems: A Dichotomy.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences.

[BibT_eX]

[DOI]

Daniel Johannsen

Igor Razgon

Proceedings of the Theory and Applications of Satisfiability Testing, 2009

A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams.

[BibT_eX]

[DOI]

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

BBOB: Nelder-Mead with resize and halfruns.

[BibT_eX]

[DOI]

Proceedings of the Genetic and Evolutionary Computation Conference, 2009

2008

A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, Third International Workshop, 2008

2007

Algorithms, measures and upper bounds for satisfiability and related problems.

[BibT_eX]

[DOI]

PhD thesis, 2007

2005

Counting models for 2SAT and 3SAT formulae.

[BibT_eX]

[DOI]

Vilhelm Dahllöf

Peter Jonsson

Theor. Comput. Sci., 2005

Faster Exact Solving of SAT Formulae with a Low Number of Occurrences per Variable.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing, 2005

An Algorithm for the SAT Problem for Formulae of Linear Length.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2005

2004

Exact algorithms for finding minimum transversals in rank-3 hypergraphs.

[BibT_eX]

[DOI]

J. Algorithms, 2004

2002

Counting Satisfying Assignments in 2-SAT and 3-SAT.

[BibT_eX]

[DOI]

Vilhelm Dahllöf

Peter Jonsson