Marcin Wrochna

Available identifiers

zbMath Open wrochna.marcinDBLP143/7540WikidataQ58656649 ScholiaQ58656649MaRDI QIDQ345099

List of research outcomes

Publication	Date of Publication	Type
Treewidth-pliability and PTAS for Max-CSPs	2024-01-15	Paper
https://portal.mardi4nfdi.de/entity/Q6089685	2023-11-13	Paper
PTAS for Sparse General-valued CSPs	2023-10-23	Paper
Topology and Adjunction in Promise Constraint Satisfaction	2023-04-04	Paper
Tight complexity lower bounds for integer linear programming with few constraints	2022-12-05	Paper
Tight complexity lower bounds for integer linear programming with few constraints	2022-07-18	Paper
The complexity of promise SAT on non-Boolean domains	2022-03-29	Paper
Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes	2021-02-15	Paper
Improved hardness for \(H\)-colourings of \(G\)-colourable graphs	2021-02-02	Paper
Smaller counterexamples to Hedetniemi's conjecture	2020-12-25	Paper
The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems	2020-12-04	Paper
Tight lower bounds for the complexity of multicoloring	2020-05-27	Paper
Linear kernels for edge deletion problems to immersion-closed graph classes	2020-05-27	Paper
Turing kernelization for finding long paths in graphs excluding a topological minor	2020-05-27	Paper
Topology and adjunction in promise constraint satisfaction	2020-03-25	Paper
Integer programming and incidence treedepth	2020-02-06	Paper
Homomorphism reconfiguration via homotopy	2020-01-31	Paper
Tight lower bounds for the complexity of multicoloring	2019-12-16	Paper
On space efficiency of algorithms working on structural decompositions of graphs	2019-12-06	Paper
On inverse powers of graphs and topological implications of Hedetniemi's conjecture	2019-11-21	Paper
Hedetniemi's conjecture and strongly multiplicative graphs	2019-11-20	Paper
Turing kernelization for finding long paths in graph classes excluding a topological minor	2019-09-10	Paper
Edge bipartization faster than \(2^k\)	2019-03-11	Paper
Cutwidth: obstructions and algorithmic aspects	2019-02-14	Paper
The step Sidorenko property and non-norming edge-transitive graphs	2018-12-19	Paper
On directed feedback vertex set parameterized by treewidth	2018-11-22	Paper
Fully polynomial-time parameterized computations for graphs and matrices of low treewidth	2018-11-13	Paper
Fully polynomial-time parameterized computations for graphs and matrices of low treewidth	2018-07-16	Paper
Cutwidth: obstructions and algorithmic aspects	2018-04-10	Paper
Edge Bipartization Faster Than 2^k	2018-04-10	Paper
On space efficiency of algorithms working on structural decompositions of graphs	2018-01-24	Paper
Reconfiguration in bounded bandwidth and tree-depth	2017-12-21	Paper
Polynomial kernelization for removing induced claws and diamonds	2017-08-15	Paper
Homomorphism reconfiguration via homotopy	2017-01-24	Paper
Square-free graphs are multiplicative	2016-11-25	Paper
Polynomial kernelization for removing induced claws and diamonds	2016-10-21	Paper
Reconfiguration over tree decompositions	2015-09-15	Paper
Reconfiguring independent sets in claw-free graphs	2014-09-02	Paper
Pliability and Approximating Max-CSPs	N/A	Paper

Research outcomes over time

This page was built for person: Marcin Wrochna