| Publication | Date of Publication | Type |
|---|
| Constructive -- non-constructive approximation and maximum independent set problem | 2024-07-05 | Paper |
| Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set} | 2024-01-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6089653 | 2023-11-13 | Paper |
| The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet * | 2023-07-24 | Paper |
| Improved (In-)Approximability Bounds for d-Scattered Set | 2023-07-03 | Paper |
| Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation | 2023-03-22 | Paper |
| New Algorithms for Mixed Dominating Set | 2022-09-30 | Paper |
| Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation | 2022-06-13 | Paper |
| In memory of Jérôme Monnot | 2022-05-23 | Paper |
| Structurally parameterized \(d\)-scattered set | 2022-01-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5136270 | 2020-11-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5116470 | 2020-08-25 | Paper |
| Improved (In-)approximability bounds for \(d\)-scattered set | 2020-08-24 | Paper |
| A polynomial time approximation schema for maximum k-vertex cover in bipartite graphs | 2019-09-18 | Paper |
| Structural parameters, tight bounds, and approximation for \((k, r)\)-center | 2019-06-20 | Paper |
| When polynomial approximation meets exact computation | 2019-03-06 | Paper |
| Structurally parameterized \(d\)-Scattered Set | 2018-11-22 | Paper |
| Parameterized (in)approximability of subset problems | 2018-09-28 | Paper |
| On the approximation of NP-complete problems by using the Boltzmann machine method: the cases of some covering and packing problems | 2018-09-14 | Paper |
| Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs | 2018-08-17 | Paper |
| Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7 | 2018-08-10 | Paper |
| The many facets of upper domination | 2018-03-13 | Paper |
| Sparsification and subexponential approximation | 2018-02-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4601874 | 2018-01-24 | Paper |
| Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse | 2018-01-24 | Paper |
| The probabilistic minimum dominating set problem | 2017-12-20 | Paper |
| Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem | 2017-12-06 | Paper |
| Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation | 2017-11-30 | Paper |
| Time-approximation trade-offs for inapproximable problems | 2017-11-14 | Paper |
| Dual parameterization and parameterized approximability of subset graph problems | 2017-03-24 | Paper |
| Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems | 2017-01-19 | Paper |
| Super-polynomial approximation branching algorithms | 2017-01-12 | Paper |
| Algorithmic Aspects of Upper Domination: A Parameterised Perspective | 2016-11-09 | Paper |
| Upper Domination: Complexity and Approximation | 2016-09-29 | Paper |
| A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs | 2016-05-03 | Paper |
| On the max min vertex cover problem | 2015-09-30 | Paper |
| When polynomial approximation meets exact computation | 2015-09-17 | Paper |
| New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set | 2015-05-29 | Paper |
| On subexponential and FPT-time inapproximability | 2015-05-04 | Paper |
| Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization | 2015-05-04 | Paper |
| Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem | 2015-01-22 | Paper |
| Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} | 2015-01-21 | Paper |
| Approximating MAX SAT by moderately exponential and parameterized algorithms | 2014-12-02 | Paper |
| A survey on the structure of approximation classes | 2014-10-07 | Paper |
| On the max min vertex cover Problem | 2014-09-02 | Paper |
| Exponential approximation schemata for some network design problems | 2014-08-13 | Paper |
| Moderately exponential time and fixed parameter approximation algorithms | 2013-12-19 | Paper |
| Reoptimization of maximum weight induced hereditary subgraph problems | 2013-12-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2865853 | 2013-12-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2867360 | 2013-12-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2867366 | 2013-12-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2867374 | 2013-12-11 | Paper |
| On subexponential and FPT-time inapproximability | 2013-12-10 | Paper |
| Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization | 2013-12-10 | Paper |
| REOPTIMIZATION UNDER VERTEX INSERTION: MAX Pk-FREE SUBGRAPH AND MAX PLANAR SUBGRAPH | 2013-09-05 | Paper |
| The Probabilistic Min Dominating Set Problem | 2013-06-14 | Paper |
| Exact and Approximation Algorithms for Densest k-Subgraph | 2013-04-12 | Paper |
| Weighted completion time minimization on a single-machine with a fixed non-availability interval: differential approximability | 2013-03-13 | Paper |
| Fast algorithms for min independent dominating set | 2013-03-12 | Paper |
| On the probabilistic min spanning tree problem | 2013-02-19 | Paper |
| New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set | 2013-01-07 | Paper |
| Algorithms for dominating clique problems | 2012-11-08 | Paper |
| Efficient Algorithms for the max k -vertex cover Problem | 2012-09-21 | Paper |
| A survey on combinatorial optimization in dynamic environments | 2012-09-04 | Paper |
| Online maximum \(k\)-coverage | 2012-08-10 | Paper |
| Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms | 2012-07-16 | Paper |
| The \textsc{max quasi-independent set} problem | 2012-07-10 | Paper |
| Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems | 2012-06-29 | Paper |
| Reoptimization of the Maximum Weighted P k -Free Subgraph Problem under Vertex Insertion | 2012-06-08 | Paper |
| Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms | 2012-04-30 | Paper |
| Fast algorithms for max independent set | 2012-04-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3109949 | 2012-01-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3109950 | 2012-01-26 | Paper |
| Online Maximum k-Coverage | 2011-08-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3081832 | 2011-03-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3070857 | 2011-01-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3070863 | 2011-01-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3061962 | 2011-01-03 | Paper |
| On the max-weight edge coloring problem | 2010-12-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3059318 | 2010-12-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3059319 | 2010-12-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3059326 | 2010-12-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3059328 | 2010-12-08 | Paper |
| Probabilistic models for the Steiner Tree problem | 2010-11-24 | Paper |
| Approximation of min coloring by moderately exponential algorithms | 2010-08-20 | Paper |
| Fast reoptimization for the minimum spanning tree problem | 2010-08-18 | Paper |
| Approximating the max-edge-coloring problem | 2010-08-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3579308 | 2010-08-06 | Paper |
| The max quasi-independent set Problem | 2010-06-22 | Paper |
| A Bottom-Up Method and Fast Algorithms for max independent set | 2010-06-22 | Paper |
| Maximum Independent Set in Graphs of Average Degree at Most Three in ${\mathcal O}(1.08537^n)$ | 2010-06-17 | Paper |
| Fast Algorithms for min independent dominating set | 2010-06-17 | Paper |
| An overview on polynomial approximation of NP-hard problems | 2010-01-12 | Paper |
| Graph-Theoretic Concepts in Computer Science | 2010-01-12 | Paper |
| Weighted coloring: further complexity and approximability results | 2009-12-18 | Paper |
| Exact Algorithms for Dominating Clique Problems | 2009-12-17 | Paper |
| Approximating the Max Edge-Coloring Problem | 2009-12-11 | Paper |
| Reoptimization of minimum and maximum traveling salesman's tours | 2009-12-10 | Paper |
| Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms | 2009-10-20 | Paper |
| Probabilistic graph-coloring in bipartite and split graphs | 2009-10-09 | Paper |
| Algorithms for the on-line quota traveling salesman problem | 2009-08-27 | Paper |
| Weighted coloring on planar, bipartite and split graphs: Complexity and approximation | 2009-06-30 | Paper |
| Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2 | 2009-06-24 | Paper |
| Efficient approximation of Min Set Cover by moderately exponential algorithms | 2009-05-28 | Paper |
| Steiner Forests on Stochastic Metric Graphs | 2009-03-03 | Paper |
| Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems | 2009-02-17 | Paper |
| On the Maximum Edge Coloring Problem | 2009-02-12 | Paper |
| Vertex-Uncertainty in Graph-Problems | 2009-01-27 | Paper |
| An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs | 2008-06-05 | Paper |
| An exact algorithm for MAX-CUT in sparse graphs | 2008-01-21 | Paper |
| Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem | 2007-12-20 | Paper |
| Mathematical Foundations of Computer Science 2003 | 2007-12-07 | Paper |
| Reoptimization of Minimum and Maximum Traveling Salesman’s Tours | 2007-09-07 | Paper |
| Improved worst-case complexity for the MIN 3-SET COVERING problem | 2007-08-27 | Paper |
| Approximation algorithms for 2-Peripathetic Salesman Problem with edge weights 1 and 2 | 2007-05-29 | Paper |
| Time slot scheduling of compatible jobs | 2007-05-15 | Paper |
| Differential approximation of MIN SAT, MAX SAT and related problems | 2007-04-19 | Paper |
| Probabilistic Combinatorial Optimization on Graphs | 2007-03-07 | Paper |
| On-line models and algorithms for max independent set | 2006-12-11 | Paper |
| Algorithms and Computation | 2006-11-14 | Paper |
| Theoretical Computer Science | 2006-11-01 | Paper |
| Completeness in approximation classes beyond APX | 2006-09-14 | Paper |
| Reductions, completeness and the hardness of approximability | 2006-05-16 | Paper |
| On the probabilistic minimum coloring and minimum \(k\)-coloring | 2006-04-28 | Paper |
| Improved approximations for weighted and unweighted graph problems | 2006-01-10 | Paper |
| Algorithms and Computation | 2005-12-22 | Paper |
| Algorithms and Computation | 2005-12-22 | Paper |
| COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES | 2005-12-15 | Paper |
| Graph-Theoretic Concepts in Computer Science | 2005-12-08 | Paper |
| SOFSEM 2005: Theory and Practice of Computer Science | 2005-12-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5702337 | 2005-11-01 | Paper |
| Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness | 2005-06-30 | Paper |
| Computing and Combinatorics | 2005-06-15 | Paper |
| On-line maximum-order induced hereditary subgraph problems | 2005-04-22 | Paper |
| Polynomial approximation algorithms with performance guarantees: an introduction-by-example | 2005-04-21 | Paper |
| On-line vertex-covering | 2005-04-06 | Paper |
| On the differential approximation of MIN SET COVER | 2005-04-06 | Paper |
| The antennas preassignment problem | 2005-03-08 | Paper |
| Proving completeness by logic | 2005-03-07 | Paper |
| A hypocoloring model for batch scheduling | 2005-02-23 | Paper |
| Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa | 2004-12-29 | Paper |
| Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation | 2004-08-30 | Paper |
| A simulated annealing approach for the circular cutting problem | 2004-08-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4471994 | 2004-08-03 | Paper |
| Differential approximation results for the Steiner tree problem | 2004-06-11 | Paper |
| Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances | 2004-03-17 | Paper |
| Local approximations for maximum partial subgraph problem. | 2004-03-15 | Paper |
| Master-slave strategy and polynomial approximation | 2003-08-26 | Paper |
| Polynomial approximation and graph-coloring | 2003-08-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4414489 | 2003-07-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4414490 | 2003-07-25 | Paper |
| Approximation algorithms for the traveling salesman problem | 2003-06-23 | Paper |
| Differential approximation for optimal satisfiability and related problems | 2003-04-28 | Paper |
| Differential approximation results for the traveling salesman problem with distances 1 and 2 | 2003-04-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4792058 | 2003-02-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4782716 | 2002-12-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4781816 | 2002-11-13 | Paper |
| The Probabilistic Minimum Vertex-covering Problem | 2002-10-10 | Paper |
| A priori optimization for the probabilistic maximum independent set problem | 2002-03-03 | Paper |
| A note on a new greedy-solution representation and a new greedy parallelizable heuristic for the traveling salesman problem | 2002-01-02 | Paper |
| An improved general procedure for lexicographic bottleneck problems | 2001-02-09 | Paper |
| A neural network for the minimum set covering problem | 2000-12-18 | Paper |
| Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems | 2000-08-24 | Paper |
| Bridging gap between standard and differential polynomial approximation: The case of bin-packing | 2000-01-30 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4258251 | 1999-09-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4258252 | 1999-09-01 | Paper |
| Probabilistic combinatorial optimization problems on graphs: A new domain in operational research | 1999-07-05 | Paper |
| The probabilistic longest path problem | 1999-06-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4246715 | 1999-06-16 | Paper |
| A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios | 1999-02-22 | Paper |
| Differential approximation algorithms for some combinatorial optimization problems | 1999-01-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4866843 | 1998-12-10 | Paper |
| A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem | 1998-08-16 | Paper |
| Average-case complexity for the execution of recursive definitions on relational databases (paper no 50-95 accepted for publication in ACTA INFORMATICA) | 1998-08-10 | Paper |
| Improved approximations for maximum independent set via approximation chains | 1998-03-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4359293 | 1997-10-08 | Paper |
| A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts | 1997-08-24 | Paper |
| The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems | 1997-06-04 | Paper |
| Average case analysis of greedy algorithms for optimisation problems on set systems | 1997-02-28 | Paper |
| On an approximation measure founded on the links between optimization and polynomial approximation theory | 1997-02-27 | Paper |
| A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set | 1997-02-20 | Paper |
| Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results | 1997-01-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4889464 | 1996-10-28 | Paper |
| A New Efficient Heuristic for the Minimum Set Covering Problem | 1996-09-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4864343 | 1996-08-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4865402 | 1996-06-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4845153 | 1995-09-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4843442 | 1995-08-13 | Paper |
| Approximation results for the minimum graph coloring problem | 1995-02-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4291269 | 1994-06-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4289901 | 1994-05-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3142706 | 1994-01-09 | Paper |
| A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem | 1993-01-04 | Paper |
