Marcin Wrochna

According to our database1, Marcin Wrochna authored at least 35 papers between 2014 and 2023.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Pliability and Approximating Max-CSPs.
J. ACM, December, 2023

PTAS for Sparse General-valued CSPs.
ACM Trans. Algorithms, April, 2023

2022
A note on hardness of promise hypergraph colouring.
CoRR, 2022

2021
The Complexity of Promise SAT on Non-Boolean Domains.
ACM Trans. Comput. Theory, 2021

Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes.
SIAM J. Discret. Math., 2021

Treewidth-Pliability and PTAS for Max-CSPs.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020
Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints.
ACM Trans. Comput. Theory, 2020

Homomorphism Reconfiguration via Homotopy.
SIAM J. Discret. Math., 2020

The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems.
SIAM J. Comput., 2020

Topology and adjunction in promise constraint satisfaction.
Electron. Colloquium Comput. Complex., 2020

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs.
Electron. Colloquium Comput. Complex., 2020

Sallow: a heuristic algorithm for treedepth decompositions.
CoRR, 2020

Improved hardness for <i>H</i>-colourings of <i>G</i>-colourable graphs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

PACE Solver Description: Sallow: A Heuristic Algorithm for Treedepth Decompositions.
Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

2019
Tight Lower Bounds for the Complexity of Multicoloring.
ACM Trans. Comput. Theory, 2019

Hedetniemi's Conjecture and Strongly Multiplicative Graphs.
SIAM J. Discret. Math., 2019

On inverse powers of graphs and topological implications of Hedetniemi's conjecture.
J. Comb. Theory, Ser. B, 2019

The step Sidorenko property and non-norming edge-transitive graphs.
J. Comb. Theory, Ser. A, 2019

Improved hardness for H-colourings of G-colourable graphs.
CoRR, 2019

Edge Bipartization Faster than $$2^k$$ 2 k.
Algorithmica, 2019

Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor.
Algorithmica, 2019

Cutwidth: Obstructions and Algorithmic Aspects.
Algorithmica, 2019

Integer Programming and Incidence Treedepth.
Proceedings of the Integer Programming and Combinatorial Optimization, 2019

2018
On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs.
ACM Trans. Comput. Theory, 2018

Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth.
ACM Trans. Algorithms, 2018

Reconfiguration in bounded bandwidth and tree-depth.
J. Comput. Syst. Sci., 2018

On Directed Feedback Vertex Set Parameterized by Treewidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

2017
Polynomial Kernelization for Removing Induced Claws and Diamonds.
Theory Comput. Syst., 2017

Square-free graphs are multiplicative.
J. Comb. Theory, Ser. B, 2017

Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor.
Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

2016
Edge Bipartization Faster Than 2^k.
Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

2015
Edge Bipartization faster than 2<sup>k</sup>.
CoRR, 2015

2014
Reconfiguration in bounded bandwidth and treedepth.
CoRR, 2014

Reconfiguring Independent Sets in Claw-Free Graphs.
Proceedings of the Algorithm Theory - SWAT 2014, 2014

Reconfiguration over Tree Decompositions.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014


  Loading...