List of research outcomes
This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!
DEBUG first row: length=10 | [1]=https://portal.mardi4nfdi.de/wiki/Public | [2]=Solving Connectivity Problems Parameteri | [3]=https://portal.mardi4nfdi.de/entity/Q605 | [4]=2023-10-31 | [5]=Q6058244 | [6]=https://portal.mardi4nfdi.de/entity/Q597 | [7]=Paper | [8]=7758411 | [9]=ACM Transactions on Algorithms | [10]=
| Publication | Date of Publication | Type |
|---|---|---|
| Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time ACM Transactions on Algorithms row10= | journal=ACM Transactions on Algorithms | arxivId= | 2023-10-31 | Paper |
| scientific article; zbMATH DE number 7740890 (Why is no real title available?) row10= | journal= | arxivId= | 2023-09-20 | Paper |
| Tight bounds on subexponential time approximation of set cover and related problems row10= | journal= | arxivId= | 2022-03-22 | Paper |
| Randomized Contractions Meet Lean Decompositions ACM Transactions on Algorithms row10= | journal=ACM Transactions on Algorithms | arxivId= | 2022-02-08 | Paper |
| Online facility location with deletions row10= | journal= | arxivId= | 2021-08-04 | Paper |
| Lower bounds for the parameterized complexity of minimum fill-in and other completion problems ACM Transactions on Algorithms row10= | journal=ACM Transactions on Algorithms | arxivId= | 2021-05-03 | Paper |
| From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more SIAM Journal on Computing row10= | journal=SIAM Journal on Computing | arxivId= | 2020-08-18 | Paper |
| Improving TSP tours using dynamic programming over tree decompositions row10= | journal= | arxivId= | 2020-05-27 | Paper |
| On Problems Equivalent to (min,+)-Convolution row10= | journal= | arxivId= | 2020-05-27 | Paper |
| Hardness of approximation for \(H\)-free edge modification problems ACM Transactions on Computation Theory row10= | journal=ACM Transactions on Computation Theory | arxivId= | 2019-12-06 | Paper |
| Improving TSP Tours Using Dynamic Programming over Tree Decompositions ACM Transactions on Algorithms row10= | journal=ACM Transactions on Algorithms | arxivId= | 2019-12-02 | Paper |
| Known algorithms for edge clique cover are probably optimal Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms row10= | journal=Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | arxivId= | 2019-05-15 | Paper |
| How to sell hyperedges: the hypermatching assignment problem Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms row10= | journal=Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | arxivId= | 2019-05-15 | Paper |
| Minimum Bisection Is Fixed-Parameter Tractable SIAM Journal on Computing row10= | journal=SIAM Journal on Computing | arxivId= | 2019-05-07 | Paper |
| On problems equivalent to \((\min,+)\)-convolution ACM Transactions on Algorithms row10= | journal=ACM Transactions on Algorithms | arxivId= | 2019-03-28 | Paper |
| Fast Hamiltonicity checking via bases of perfect matchings Journal of the ACM row10= | journal=Journal of the ACM | arxivId= | 2018-12-06 | Paper |
| Approximation and parameterized complexity of minimax approval voting Journal of Artificial Intelligence Research row10= | journal=Journal of Artificial Intelligence Research | arxivId= | 2018-11-30 | Paper |
| Tight kernel bounds for problems on graphs with small degeneracy ACM Transactions on Algorithms row10= | journal=ACM Transactions on Algorithms | arxivId= | 2018-11-12 | Paper |
| On problems as hard as CNF-SAT ACM Transactions on Algorithms row10= | journal=ACM Transactions on Algorithms | arxivId= | 2018-11-05 | Paper |
| Directed subset feedback vertex set is fixed-parameter tractable ACM Transactions on Algorithms row10= | journal=ACM Transactions on Algorithms | arxivId= | 2018-10-30 | Paper |
| Algorithmic applications of Baur-Strassen's theorem, shortest cycles, diameter, and matchings Journal of the ACM row10= | journal=Journal of the ACM | arxivId= | 2018-08-02 | Paper |
| 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 row10= | journal=Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | arxivId= | 2018-07-16 | Paper |
| Tight Bounds for Graph Homomorphism and Subgraph Isomorphism Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms row10= | journal=Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | arxivId= | 2018-07-16 | Paper |
| Algorithmic complexity of power law networks Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms row10= | journal=Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | arxivId= | 2018-07-16 | Paper |
| Online pricing with impatient bidders Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms row10= | journal=Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | arxivId= | 2018-07-16 | Paper |
| Tight lower bounds on graph embedding problems Journal of the ACM row10= | journal=Journal of the ACM | arxivId= | 2018-05-17 | Paper |
| Hardness of approximation for \(H\)-free edge modification problems row10= | journal= | arxivId= | 2018-04-19 | Paper |
| Lower bounds for approximation schemes for Closest String row10= | journal= | arxivId= | 2017-10-17 | Paper |
| The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn List partition problem row10= | journal= | arxivId= | 2017-09-29 | Paper |
| Hitting forbidden subgraphs in graphs of bounded treewidth Information and Computation row10= | journal=Information and Computation | arxivId= | 2017-09-28 | Paper |
| Approximating upper degree-constrained partial orientations row10= | journal= | arxivId= | 2017-08-31 | Paper |
| Polynomial kernelization for removing induced claws and diamonds Theory of Computing Systems row10= | journal=Theory of Computing Systems | arxivId= | 2017-08-15 | Paper |
| Scheduling partially ordered jobs faster than \(2^n\) Algorithmica row10= | journal=Algorithmica | arxivId= | 2017-05-17 | Paper |
| Catch them if you can Proceedings of the 4th conference on Innovations in Theoretical Computer Science row10= | journal=Proceedings of the 4th conference on Innovations in Theoretical Computer Science | arxivId= | 2017-05-16 | Paper |
| Constant Factor Approximation for Capacitated k-Center with Outliers row10= | journal= | arxivId= | 2017-03-03 | Paper |
| On Pairwise Spanners row10= | journal= | arxivId= | 2017-01-30 | Paper |
| Polynomial kernelization for removing induced claws and diamonds Graph-Theoretic Concepts in Computer Science row10= | journal=Graph-Theoretic Concepts in Computer Science | arxivId= | 2016-10-21 | Paper |
| Designing FPT algorithms for cut problems using randomized contractions SIAM Journal on Computing row10= | journal=SIAM Journal on Computing | arxivId= | 2016-08-16 | Paper |
| Polynomial-time approximation algorithms for weighted LCS problem Discrete Applied Mathematics row10= | journal=Discrete Applied Mathematics | arxivId= | 2016-04-07 | Paper |
| On group feedback vertex set parameterized by the size of the cutset Algorithmica row10= | journal=Algorithmica | arxivId= | 2016-03-29 | Paper |
| Online knapsack revisited Theory of Computing Systems row10= | journal=Theory of Computing Systems | arxivId= | 2016-03-21 | Paper |
| A fast branching algorithm for cluster vertex deletion Theory of Computing Systems row10= | journal=Theory of Computing Systems | arxivId= | 2016-03-09 | Paper |
| Known algorithms for edge clique cover are probably optimal SIAM Journal on Computing row10= | journal=SIAM Journal on Computing | arxivId= | 2016-01-20 | Paper |
| On multiway cut parameterized above lower bounds ACM Transactions on Computation Theory row10= | journal=ACM Transactions on Computation Theory | arxivId= | 2015-09-24 | Paper |
| Clique Cover and Graph Separation ACM Transactions on Computation Theory row10= | journal=ACM Transactions on Computation Theory | arxivId= | 2015-09-03 | Paper |
| Parameterized algorithms row10= | journal= | arxivId= | 2015-08-17 | Paper |
| Minimum bisection is fixed parameter tractable Proceedings of the forty-sixth annual ACM symposium on Theory of computing row10= | journal=Proceedings of the forty-sixth annual ACM symposium on Theory of computing | arxivId= | 2015-06-26 | Paper |
| Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth Information and Computation row10= | journal=Information and Computation | arxivId= | 2015-06-09 | Paper |
| Faster exponential-time algorithms in graphs of bounded average degree Information and Computation row10= | journal=Information and Computation | arxivId= | 2015-06-09 | Paper |
| Sitting closer to friends than enemies, revisited Theory of Computing Systems row10= | journal=Theory of Computing Systems | arxivId= | 2015-05-29 | Paper |
| Kernelization lower bound for permutation pattern matching Information Processing Letters row10= | journal=Information Processing Letters | arxivId= | 2015-04-02 | Paper |
| Solving the 2-disjoint connected subgraphs problem faster than \(2^n\) Algorithmica row10= | journal=Algorithmica | arxivId= | 2015-01-19 | Paper |
| On cutwidth parameterized by vertex cover Algorithmica row10= | journal=Algorithmica | arxivId= | 2014-12-02 | Paper |
| Hitting forbidden subgraphs in graphs of bounded treewidth Mathematical Foundations of Computer Science 2014 row10= | journal=Mathematical Foundations of Computer Science 2014 | arxivId= | 2014-10-14 | Paper |
| Even faster exact bandwidth ACM Transactions on Algorithms row10= | journal=ACM Transactions on Algorithms | arxivId= | 2014-09-09 | Paper |
| Online knapsack revisited Approximation and Online Algorithms row10= | journal=Approximation and Online Algorithms | arxivId= | 2014-09-02 | Paper |
| Fast Hamiltonicity checking via bases of perfect matchings Proceedings of the forty-fifth annual ACM symposium on Theory of Computing row10= | journal=Proceedings of the forty-fifth annual ACM symposium on Theory of Computing | arxivId= | 2014-08-07 | Paper |
| Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science row10= | journal=2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | arxivId= | 2014-07-30 | Paper |
| A fast branching algorithm for cluster vertex deletion Computer Science - Theory and Applications row10= | journal=Computer Science - Theory and Applications | arxivId= | 2014-06-24 | Paper |
| Parameterized complexity of firefighting Journal of Computer and System Sciences row10= | journal=Journal of Computer and System Sciences | arxivId= | 2014-06-10 | Paper |
| On the hardness of losing width Theory of Computing Systems row10= | journal=Theory of Computing Systems | arxivId= | 2014-03-25 | Paper |
| Parameterized complexity of Eulerian deletion problems Algorithmica row10= | journal=Algorithmica | arxivId= | 2014-03-25 | Paper |
| A bound on the number of perfect matchings in Klee-graphs row10= | journal= | arxivId= | 2014-02-14 | Paper |
| Steiner forest orientation problems SIAM Journal on Discrete Mathematics row10= | journal=SIAM Journal on Discrete Mathematics | arxivId= | 2014-01-21 | Paper |
| On the inequality between radius and Randić index for graphs MATCH - Communications in Mathematical and in Computer Chemistry row10= | journal=MATCH - Communications in Mathematical and in Computer Chemistry | arxivId= | 2013-10-30 | Paper |
| Tight Kernel Bounds for Problems on Graphs with Small Degeneracy Lecture Notes in Computer Science row10= | journal=Lecture Notes in Computer Science | arxivId= | 2013-09-17 | Paper |
| Directed Subset Feedback Vertex Set is fixed-parameter tractable Automata, Languages, and Programming row10= | journal=Automata, Languages, and Programming | arxivId= | 2013-08-12 | Paper |
| Clique cover and graph separation: new incompressibility results Automata, Languages, and Programming row10= | journal=Automata, Languages, and Programming | arxivId= | 2013-08-12 | Paper |
| Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth Automata, Languages, and Programming row10= | journal=Automata, Languages, and Programming | arxivId= | 2013-08-06 | Paper |
| Faster exponential-time algorithms in graphs of bounded average degree Automata, Languages, and Programming row10= | journal=Automata, Languages, and Programming | arxivId= | 2013-08-06 | Paper |
| Subset feedback vertex set is fixed-parameter tractable SIAM Journal on Discrete Mathematics row10= | journal=SIAM Journal on Discrete Mathematics | arxivId= | 2013-06-27 | Paper |
| The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable row10= | journal= | arxivId= | 2013-04-15 | Paper |
| Channel assignment via fast zeta transform Information Processing Letters row10= | journal=Information Processing Letters | arxivId= | 2013-04-04 | Paper |
| Capacitated domination faster than \(O(2^n)\) Information Processing Letters row10= | journal=Information Processing Letters | arxivId= | 2013-04-04 | Paper |
| \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms Information Processing Letters row10= | journal=Information Processing Letters | arxivId= | 2013-03-21 | Paper |
| Relation between Randić index and average distance of trees row10= | journal= | arxivId= | 2013-01-21 | Paper |
| A polynomial algorithm for 3-compatible coloring and the stubborn list partition problem (the stubborn problem is stubborn no more) SIAM Journal on Computing row10= | journal=SIAM Journal on Computing | arxivId= | 2012-11-29 | Paper |
| An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion Algorithmica row10= | journal=Algorithmica | arxivId= | 2012-11-21 | Paper |
| On group feedback vertex set parameterized by the size of the cutset Lecture Notes in Computer Science row10= | journal=Lecture Notes in Computer Science | arxivId= | 2012-11-06 | Paper |
| Kernelization hardness of connectivity problems in \(d\)-degenerate graphs Discrete Applied Mathematics row10= | journal=Discrete Applied Mathematics | arxivId= | 2012-10-26 | Paper |
| Steiner forest orientation problems Lecture Notes in Computer Science row10= | journal=Lecture Notes in Computer Science | arxivId= | 2012-09-25 | Paper |
| A path-decomposition theorem with applications to pricing and covering on trees Algorithms – ESA 2012 row10= | journal=Algorithms – ESA 2012 | arxivId= | 2012-09-25 | Paper |
| Sitting closer to friends than enemies, revisited Mathematical Foundations of Computer Science 2012 row10= | journal=Mathematical Foundations of Computer Science 2012 | arxivId= | 2012-09-25 | Paper |
| Approximation algorithms for union and intersection covering problems row10= | journal= | arxivId= | 2012-08-31 | Paper |
| Deterministic parameterized connected vertex cover Algorithm Theory – SWAT 2012 row10= | journal=Algorithm Theory – SWAT 2012 | arxivId= | 2012-08-14 | Paper |
| Solving the 2-disjoint connected subgraphs problem faster than \(2^{n }\) LATIN 2012: Theoretical Informatics row10= | journal=LATIN 2012: Theoretical Informatics | arxivId= | 2012-06-29 | Paper |
| Parameterized Complexity of Firefighting Revisited Parameterized and Exact Computation row10= | journal=Parameterized and Exact Computation | arxivId= | 2012-06-15 | Paper |
| On cutwidth parameterized by vertex cover Parameterized and Exact Computation row10= | journal=Parameterized and Exact Computation | arxivId= | 2012-06-15 | Paper |
| On the hardness of losing width Parameterized and Exact Computation row10= | journal=Parameterized and Exact Computation | arxivId= | 2012-06-15 | Paper |
| On multiway cut parameterized above lower bounds Lecture Notes in Computer Science row10= | journal=Lecture Notes in Computer Science | arxivId= | 2012-06-15 | Paper |
| A planar linear arboricity conjecture Journal of Graph Theory row10= | journal=Journal of Graph Theory | arxivId= | 2012-06-13 | Paper |
| Bandwidth and distortion revisited Discrete Applied Mathematics row10= | journal=Discrete Applied Mathematics | arxivId= | 2012-05-04 | Paper |
| Parameterized complexity of Eulerian deletion problems Graph-Theoretic Concepts in Computer Science row10= | journal=Graph-Theoretic Concepts in Computer Science | arxivId= | 2011-12-16 | Paper |
| Dominating set is fixed parameter tractable in claw-free graphs Theoretical Computer Science row10= | journal=Theoretical Computer Science | arxivId= | 2011-12-07 | Paper |
| Scheduling partially ordered jobs faster than \(2^{n }\) Algorithms – ESA 2011 row10= | journal=Algorithms – ESA 2011 | arxivId= | 2011-09-16 | Paper |
| Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack Journal of Discrete Algorithms row10= | journal=Journal of Discrete Algorithms | arxivId= | 2011-08-23 | Paper |
| Subset feedback vertex set is fixed-parameter tractable Lecture Notes in Computer Science row10= | journal=Lecture Notes in Computer Science | arxivId= | 2011-07-06 | Paper |
| Polynomial-time approximation algorithms for weighted LCS problem Combinatorial Pattern Matching row10= | journal=Combinatorial Pattern Matching | arxivId= | 2011-06-29 | Paper |
| An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion Parameterized and Exact Computation row10= | journal=Parameterized and Exact Computation | arxivId= | 2010-12-07 | Paper |
| Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs Graph Theoretic Concepts in Computer Science row10= | journal=Graph Theoretic Concepts in Computer Science | arxivId= | 2010-11-16 | Paper |
| Exact and approximate bandwidth Theoretical Computer Science row10= | journal=Theoretical Computer Science | arxivId= | 2010-10-11 | Paper |
| Fast approximation in subspaces by doubling metric decomposition Algorithms – ESA 2010 row10= | journal=Algorithms – ESA 2010 | arxivId= | 2010-09-06 | Paper |
| Exponential-time approximation of weighted set cover Information Processing Letters row10= | journal=Information Processing Letters | arxivId= | 2010-08-20 | Paper |
| Algorithms for Three Versions of the Shortest Common Superstring Problem Combinatorial Pattern Matching row10= | journal=Combinatorial Pattern Matching | arxivId= | 2010-07-26 | Paper |
| Capacitated domination faster than \(O(2^{n })\) Lecture Notes in Computer Science row10= | journal=Lecture Notes in Computer Science | arxivId= | 2010-06-22 | Paper |
| Irredundant Set Faster Than O(2 n ) Lecture Notes in Computer Science row10= | journal=Lecture Notes in Computer Science | arxivId= | 2010-05-28 | Paper |
| A planar linear arboricity conjecture Lecture Notes in Computer Science row10= | journal=Lecture Notes in Computer Science | arxivId= | 2010-05-28 | Paper |
| Exact and Approximate Bandwidth Automata, Languages and Programming row10= | journal=Automata, Languages and Programming | arxivId= | 2009-07-14 | Paper |
| Faster Exact Bandwidth Graph-Theoretic Concepts in Computer Science row10= | journal=Graph-Theoretic Concepts in Computer Science | arxivId= | 2009-01-20 | Paper |
Research outcomes over time
This page was built for person: Marek Cygan
