Marek Cygan

According to our database1, Marek Cygan authored at least 94 papers between 2008 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
On Problems Equivalent to (min, +)-Convolution.
ACM Trans. Algorithms, 2019

Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
ACM Trans. Algorithms, 2019

Minimum Bisection Is Fixed-Parameter Tractable.
SIAM J. Comput., 2019

2018
Hardness of Approximation for H-free Edge Modification Problems.
TOCT, 2018

Approximation and Parameterized Complexity of Minimax Approval Voting.
J. Artif. Intell. Res., 2018

Fast Hamiltonicity Checking Via Bases of Perfect Matchings.
J. ACM, 2018

On subexponential running times for approximating directed Steiner tree and related problems.
CoRR, 2018

Randomized contractions meet lean decompositions.
CoRR, 2018

Improved GQ-CNN: Deep Learning Model for Planning Robust Grasps.
CoRR, 2018

Online Facility Location with Deletions.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy.
ACM Trans. Algorithms, 2017

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

Tight Lower Bounds on Graph Embedding Problems.
J. ACM, 2017

Hitting forbidden subgraphs in graphs of bounded treewidth.
Inf. Comput., 2017

Randomization in Parameterized Complexity (Dagstuhl Seminar 17041).
Dagstuhl Reports, 2017

Improving TSP tours using dynamic programming over tree decomposition.
CoRR, 2017

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Randomized Contraction.
Encyclopedia of Algorithms, 2016

Exact Algorithms for Bandwidth.
Encyclopedia of Algorithms, 2016

On Problems as Hard as CNF-SAT.
ACM Trans. Algorithms, 2016

Known Algorithms for Edge Clique Cover are Probably Optimal.
SIAM J. Comput., 2016

Designing FPT Algorithms for Cut Problems Using Randomized Contractions.
SIAM J. Comput., 2016

Online Knapsack Revisited.
Theory Comput. Syst., 2016

A Fast Branching Algorithm for Cluster Vertex Deletion.
Theory Comput. Syst., 2016

Polynomial-time approximation algorithms for weighted LCS problem.
Discret. Appl. Math., 2016

On Group Feedback Vertex Set Parameterized by the Size of the Cutset.
Algorithmica, 2016

Erratum to: Foreword: Special Issue on IPEC 2014.
Algorithmica, 2016

Foreword: Special Issue on IPEC 2014.
Algorithmica, 2016

Lower Bounds for Approximation Schemes for Closest String.
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Online Pricing with Impatient Bidders.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Tight Bounds for Graph Homomorphism and Subgraph Isomorphism.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Algorithmic Complexity of Power Law Networks.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Hardness of Approximation for H-Free Edge Modification Problems.
Proceedings of the Approximation, 2016

2015
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable.
ACM Trans. Algorithms, 2015

Sitting Closer to Friends than Enemies, Revisited.
Theory Comput. Syst., 2015

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter, and Matchings.
J. ACM, 2015

Kernelization lower bound for Permutation Pattern Matching.
Inf. Process. Lett., 2015

Faster exponential-time algorithms in graphs of bounded average degree.
Inf. Comput., 2015

Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth.
Inf. Comput., 2015

The Hardness of Subgraph Isomorphism.
CoRR, 2015

Approximating Upper Degree-Constrained Partial Orientations.
Proceedings of the Approximation, 2015

Parameterized Algorithms
Springer, ISBN: 978-3-319-21275-3, 2015

2014
Clique Cover and Graph Separation: New Incompressibility Results.
TOCT, 2014

On the Hardness of Losing Width.
Theory Comput. Syst., 2014

Parameterized complexity of firefighting.
J. Comput. Syst. Sci., 2014

Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n.
Algorithmica, 2014

Scheduling Partially Ordered Jobs Faster than 2 n.
Algorithmica, 2014

Parameterized Complexity of Eulerian Deletion Problems.
Algorithmica, 2014

On Cutwidth Parameterized by Vertex Cover.
Algorithmica, 2014

Constant Factor Approximation for Capacitated k-Center with Outliers.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

2013
On multiway cut parameterized above lower bounds.
TOCT, 2013

Subset Feedback Vertex Set Is Fixed-Parameter Tractable.
SIAM J. Discrete Math., 2013

Steiner Forest Orientation Problems.
SIAM J. Discrete Math., 2013

Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms.
Inf. Process. Lett., 2013

A bound on the number of perfect matchings in Klee-graphs.
Discrete Mathematics & Theoretical Computer Science, 2013

Online Knapsack Revisited.
Proceedings of the Approximation and Online Algorithms - 11th International Workshop, 2013

On Pairwise Spanners.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

How to Sell Hyperedges: The Hypermatching Assignment Problem.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Catch them if you can: how to serve impatient users.
Proceedings of the Innovations in Theoretical Computer Science, 2013

The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Tight Kernel Bounds for Problems on Graphs with Small Degeneracy - (Extended Abstract).
Proceedings of the Algorithms - ESA 2013, 2013

2012
Even Faster Exact Bandwidth.
ACM Trans. Algorithms, 2012

A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More).
SIAM J. Comput., 2012

A Planar linear arboricity conjecture.
Journal of Graph Theory, 2012

Kernelization hardness of connectivity problems in d-degenerate graphs.
Discret. Appl. Math., 2012

Bandwidth and distortion revisited.
Discret. Appl. Math., 2012

Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time
CoRR, 2012

On fixed-parameter algorithms for Split Vertex Deletion
CoRR, 2012

An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion.
Algorithmica, 2012

Deterministic Parameterized Connected Vertex Cover.
Proceedings of the Algorithm Theory - SWAT 2012, 2012

LP Rounding for k-Centers with Non-uniform Hard Capacities.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees.
Proceedings of the Algorithms - ESA 2012, 2012

2011
Dominating set is fixed parameter tractable in claw-free graphs.
Theor. Comput. Sci., 2011

Breaking the 2n-barrier for Irredundance: Two lines of attack.
J. Discrete Algorithms, 2011

Capacitated domination faster than O(n2).
Inf. Process. Lett., 2011

Channel assignment via fast zeta transform.
Inf. Process. Lett., 2011

On Problems as Hard as CNFSAT
CoRR, 2011

The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem).
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Parameterized Complexity of Firefighting Revisited.
Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011

Approximation Algorithms for Union and Intersection Covering Problems.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
Exact and approximate bandwidth.
Theor. Comput. Sci., 2010

Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Capacitated Domination Faster Than O(2n).
Proceedings of the Algorithm Theory, 2010

Fast Approximation in Subspaces by Doubling Metric Decomposition.
Proceedings of the Algorithms, 2010

Algorithms for Three Versions of the Shortest Common Superstring Problem.
Proceedings of the Combinatorial Pattern Matching, 21st Annual Symposium, 2010

Irredundant Set Faster Than O(2n).
Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

A Planar Linear Arboricity Conjecture.
Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

2009
Exponential-time approximation of weighted set cover.
Inf. Process. Lett., 2009

Beyond O*(2^n) in domination-type problems
CoRR, 2009

2008
Exponential-Time Approximation of Hard Problems
CoRR, 2008

Faster Exact Bandwidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008


  Loading...