pith. machine review for the scientific record. sign in

Marek Cygan

Identifiers

  • name variant Marek Cygan 0.60 · backfill

Papers (54)

  1. Reward-Conditioned Reinforcement Learning cs.LG · 2026 · author #2
  2. On subexponential running times for approximating directed Steiner tree and related problems cs.DS · 2018 · author #1
  3. Online Facility Location with Deletions cs.DS · 2018 · author #1
  4. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More cs.CC · 2017 · author #2
  5. Improving TSP tours using dynamic programming over tree decomposition cs.DS · 2017 · author #1
  6. On problems equivalent to (min,+)-convolution cs.DS · 2017 · author #1
  7. Approximation and Parameterized Complexity of Minimax Approval Voting cs.DS · 2016 · author #1
  8. Hardness of approximation for H-free edge modification problems cs.DS · 2016 · author #2
  9. Tight Lower Bounds on Graph Embedding Problems cs.DS · 2016 · author #1
  10. Lower bounds for approximation schemes for Closest String cs.DS · 2015 · author #1
  11. Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems cs.CC · 2015 · author #2
  12. Algorithmic Complexity of Power Law Networks cs.DS · 2015 · author #2
  13. The Hardness of Subgraph Isomorphism cs.DS · 2015 · author #1
  14. Polynomial kernelization for removing induced claws and diamonds cs.DS · 2015 · author #1
  15. Hitting forbidden subgraphs in graphs of bounded treewidth cs.DS · 2014 · author #1
  16. Approximating Upper Degree-Constrained Partial Orientations cs.DS · 2014 · author #1
  17. Kernelization lower bound for Permutation Pattern Matching cs.DS · 2014 · author #2
  18. Constant Factor Approximation for Capacitated k-Center with Outliers cs.DS · 2014 · author #2
  19. Minimum Bisection is fixed parameter tractable cs.DS · 2013 · author #1
  20. Fast branching algorithm for Cluster Vertex Deletion cs.DS · 2013 · author #2
  21. Tight Kernel Bounds for Problems on Graphs with Small Degeneracy cs.DS · 2013 · author #1
  22. The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable cs.DM · 2013 · author #1
  23. Improved approximation for 3-dimensional matching via bounded pathwidth local search cs.DS · 2013 · author #1
  24. Faster exponential-time algorithms in graphs of bounded average degree cs.DS · 2013 · author #1
  25. On Pairwise Spanners cs.DS · 2013 · author #1
  26. Fast Hamiltonicity checking via bases of perfect matchings cs.DS · 2012 · author #1
  27. Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time cs.DS · 2012 · author #2
  28. LP Rounding for k-Centers with Non-uniform Hard Capacities cs.DS · 2012 · author #1
  29. On fixed-parameter algorithms for Split Vertex Deletion cs.DS · 2012 · author #1
  30. Designing FPT algorithms for cut problems using randomized contractions cs.DS · 2012 · author #2
  31. Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable cs.DS · 2012 · author #2
  32. Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings cs.DS · 2012 · author #1
  33. Known algorithms for EDGE CLIQUE COVER are probably optimal cs.DS · 2012 · author #1
  34. Deterministic parameterized connected vertex cover cs.DS · 2012 · author #1
  35. Sitting closer to friends than enemies, revisited cs.DS · 2012 · author #1
  36. On group feedback vertex set parameterized by the size of the cutset cs.DS · 2011 · author #1
  37. On Problems as Hard as CNFSAT cs.DS · 2011 · author #1
  38. Steiner Forest Orientation Problems cs.DS · 2011 · author #1
  39. Clique cover and graph separation: New incompressibility results cs.DS · 2011 · author #1
  40. Parameterized Complexity of Firefighting Revisited cs.DM · 2011 · author #1
  41. Scheduling partially ordered jobs faster than 2^n cs.DS · 2011 · author #1
  42. On Multiway Cut parameterized above lower bounds cs.DS · 2011 · author #1
  43. Channel Assignment via Fast Zeta Transform cs.DS · 2011 · author #1
  44. Solving connectivity problems parameterized by treewidth in single exponential time cs.DS · 2011 · author #1
  45. Approximation Algorithms for Union and Intersection Covering Problems cs.DS · 2011 · author #1
  46. Dominating Set is Fixed Parameter Tractable in Claw-free Graphs cs.DS · 2010 · author #1
  47. Bandwidth and Distortion Revisited cs.DS · 2010 · author #1
  48. The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem) cs.DS · 2010 · author #1
  49. Subset feedback vertex set is fixed parameter tractable cs.DS · 2010 · author #1
  50. A Planar Linear Arboricity Conjecture math.CO · 2009 · author #1
  51. Fast Approximation in Subspaces by Doubling Metric Decomposition cs.DS · 2009 · author #1
  52. Beyond O*(2^n) in domination-type problems cs.DS · 2009 · author #1
  53. Even Faster Exact Bandwidth cs.CC · 2009 · author #1
  54. Exponential-Time Approximation of Hard Problems cs.DS · 2008 · author #1

Mentions

  • 1004.5012 #1 · backfill · confidence 0.70 Marek Cygan
  • 1004.5010 #1 · backfill · confidence 0.70 Marek Cygan
  • 1004.2972 #1 · backfill · confidence 0.70 Marek Cygan
  • 0912.5528 #1 · backfill · confidence 0.70 Marek Cygan
  • 0911.1626 #1 · backfill · confidence 0.70 Marek Cygan
  • 0909.4021 #1 · backfill · confidence 0.70 Marek Cygan
  • 0902.1661 #1 · backfill · confidence 0.70 Marek Cygan
  • 0810.4934 #1 · backfill · confidence 0.70 Marek Cygan

Frequent Coauthors