Cristina Bazgan

Henning Fernau

Algorithmica, March, 2024

Destroying Densest Subgraphs Is Hard.

[BibT_eX]

[DOI]

André Nichterlein

Sofia Vazquez Alferez

Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory, 2024

2023

Exact and approximate determination of the Pareto front using Minimal Correction Subsets.

[BibT_eX]

[DOI]

Comput. Oper. Res., May, 2023

Warm-Starting Nested Rollout Policy Adaptation with Optimal Stopping.

[BibT_eX]

[DOI]

Pierre-Henri Wuillemin

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

The Power of the Weighted Sum Scalarization for Approximating Multiobjective Optimization Problems.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2022

An approximation algorithm for a general class of parametric optimization problems.

[BibT_eX]

[DOI]

J. Comb. Optim., 2022

An approximation algorithm for the maximum spectral subgraph problem.

[BibT_eX]

[DOI]

Paul Beaujean

Éric Gourdin

J. Comb. Optim., 2022

Exact and approximate determination of the Pareto set using minimal correction subsets.

[BibT_eX]

[DOI]

CoRR, 2022

Dense Graph Partitioning on Sparse and Dense Graphs.

[BibT_eX]

[DOI]

Katrin Casel

Pierre Cazals

Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

2021

Degree-anonymization using edge rotations.

[BibT_eX]

[DOI]

Pierre Cazals

Theor. Comput. Sci., 2021

One-exact approximate Pareto sets.

[BibT_eX]

[DOI]

J. Glob. Optim., 2021

Monte Carlo Search Algorithms for Network Traffic Engineering.

[BibT_eX]

[DOI]

Pierre-Henri Wuillemin

Proceedings of the Machine Learning and Knowledge Discovery in Databases. Applied Data Science Track, 2021

2020

Graphs without a partition into two proportionally dense subgraphs.

[BibT_eX]

[DOI]

Clément Dallard

Inf. Process. Lett., 2020

Domination chain: Characterisation, classical complexity, parameterised complexity and approximability.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2020

Parameterized Dynamic Variants of Red-Blue Dominating Set.

[BibT_eX]

[DOI]

Faisal N. Abu-Khzam

Henning Fernau

Proceedings of the SOFSEM 2020: Theory and Practice of Computer Science, 2020

How to Get a Degree-Anonymous Graph Using Minimum Number of Edge Rotations.

[BibT_eX]

[DOI]

Pierre Cazals

Proceedings of the Combinatorial Optimization and Applications, 2020

2019

Finding a potential community in networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

Parameterized and approximation complexity of Partial VC Dimension.

[BibT_eX]

[DOI]

Florent Foucaud

Florian Sikora

Theor. Comput. Sci., 2019

A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths.

[BibT_eX]

[DOI]

Networks, 2019

Aspects of upper defensive alliances.

[BibT_eX]

[DOI]

Henning Fernau

Discret. Appl. Math., 2019

Proportionally dense subgraph of maximum size: Complexity and approximation.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2019

An FPTAS for a General Class of Parametric Optimization Problems.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 25th International Conference, 2019

2018

The many facets of upper domination.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Structural and Algorithmic Properties of 2-Community Structures.

[BibT_eX]

[DOI]

Algorithmica, 2018

Clustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework.

[BibT_eX]

[DOI]

Algorithmica, 2018

Relaxation and Matrix Randomized Rounding for the Maximum Spectral Subgraph Problem.

[BibT_eX]

[DOI]

Paul Beaujean

Éric Gourdin

Proceedings of the Combinatorial Optimization and Applications, 2018

2017

Discrete representation of the non-dominated set for multi-objective optimization problems using kernels.

[BibT_eX]

[DOI]

Florian Jamain

Eur. J. Oper. Res., 2017

On the Complexity of Finding a Potential Community.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

2016

Finding large degree-anonymous subgraphs is hard.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Data reductions and combinatorial bounds for improved approximation algorithms.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2016

Upper Domination: Complexity and Approximation.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 27th International Workshop, 2016

Building Clusters with Lower-Bounded Sizes.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

On the Approximability of Partial VC Dimension.

[BibT_eX]

[DOI]

Florent Foucaud

Florian Sikora

Proceedings of the Combinatorial Optimization and Applications, 2016

On the Complexity Landscape of the Domination Chain.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Discrete Applied Mathematics, 2016

Algorithmic Aspects of Upper Domination: A Parameterised Perspective.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects in Information and Management, 2016

2015

Approximate Pareto sets of minimal size for multi-objective optimization problems.

[BibT_eX]

[DOI]

Florian Jamain

Oper. Res. Lett., 2015

Blockers for the Stability Number and the Chromatic Number.

[BibT_eX]

[DOI]

Graphs Comb., 2015

Algorithmic Aspects of Upper Domination.

[BibT_eX]

[DOI]

CoRR, 2015

On the Complexity of QoS-Aware Service Selection Problem.

[BibT_eX]

[DOI]

Proceedings of the Service-Oriented Computing - 13th International Conference, 2015

New Insight into 2-Community Structures in Graphs with Applications in Social Networks.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization and Applications, 2015

A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths.

[BibT_eX]

[DOI]

André Nichterlein

Rolf Niedermeier

Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

2014

Complexity and approximation for Traveling Salesman Problems with profits.

[BibT_eX]

[DOI]

Enrico Angelelli

Maria Grazia Speranza

Theor. Comput. Sci., 2014

Parameterized approximability of maximizing the spread of influence in networks.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2014

Parameterized complexity of firefighting.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2014

The complexity of finding harmless individuals in social networks.

[BibT_eX]

[DOI]

Discret. Optim., 2014

Parameterized Inapproximability of Target Set Selection and Generalizations.

[BibT_eX]

[DOI]

Comput., 2014

Parameterized Inapproximability of Degree Anonymization.

[BibT_eX]

[DOI]

André Nichterlein

Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

Approximation Algorithms Inspired by Kernelization Methods.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

2013

Single approximation for the biobjective Max TSP.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Critical edges for the assignment problem: Complexity and exact resolution.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2013

Approximation with a fixed number of solutions of some multiobjective maximization problems.

[BibT_eX]

[DOI]

Laurent Gourvès

J. Discrete Algorithms, 2013

Critical edges/nodes for the minimum spanning tree problem: complexity and approximation.

[BibT_eX]

[DOI]

J. Comb. Optim., 2013

Complexity of determining the most vital elements for the p-median and p-center location problems.

[BibT_eX]

[DOI]

J. Comb. Optim., 2013

On the number of non-dominated points of a multicriteria optimization problem.

[BibT_eX]

[DOI]

Florian Jamain

Discret. Appl. Math., 2013

The firefighter problem with more than one firefighter on trees.

[BibT_eX]

[DOI]

Bernard Ries

Discret. Appl. Math., 2013

2012

Efficient determination of the k most vital edges for the minimum spanning tree problem.

[BibT_eX]

[DOI]

Comput. Oper. Res., 2012

The Robust Set Problem: Parameterized Complexity and Approximation.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2011

Complexity and approximation of the Constrained Forest problem.

[BibT_eX]

[DOI]

Basile Couëtoux

Theor. Comput. Sci., 2011

The most vital nodes with respect to independent set and vertex cover.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2011

Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems.

[BibT_eX]

[DOI]

Laurent Gourvès

Proceedings of the Approximation and Online Algorithms - 9th International Workshop, 2011

Parameterized Complexity of the Firefighter Problem.

[BibT_eX]

[DOI]

Michael R. Fellows

Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

Efficient Algorithms for Finding the <i>k</i> Most Vital Edges for the Minimum Spanning Tree Problem.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization and Applications, 2011

2010

Satisfactory graph partition, variants, and generalizations.

[BibT_eX]

[DOI]

Eur. J. Oper. Res., 2010

General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems.

[BibT_eX]

[DOI]

Discret. Optim., 2010

Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 21st International Workshop, 2010

Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization and Applications, 2010

2009

Implementing an efficient fptas for the 0-1 multi-objective knapsack problem.

[BibT_eX]

[DOI]

Eur. J. Oper. Res., 2009

Min-max and min-max regret versions of combinatorial optimization problems: A survey.

[BibT_eX]

[DOI]

Eur. J. Oper. Res., 2009

Solving efficiently the 0-1 multi-objective knapsack problem.

[BibT_eX]

[DOI]

Comput. Oper. Res., 2009

Covering a Graph with a Constrained Forest (Extended Abstract).

[BibT_eX]

[DOI]

Basile Couëtoux

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008

Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2008

Approximation of satisfactory bisection problems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

Complexity of the min-max (regret) versions of min cut problems.

[BibT_eX]

[DOI]

Discret. Optim., 2008

2007

Approximation of min-max and min-max regret versions of some combinatorial optimization problems.

[BibT_eX]

[DOI]

Eur. J. Oper. Res., 2007

Efficient algorithms for decomposing graphs under degree constraints.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2007

An Efficient Implementation for the 0-1 Multi-objective Knapsack Problem.

[BibT_eX]

[DOI]

Proceedings of the Experimental Algorithms, 6th International Workshop, 2007

A Practical Efficient Fptas for the 0-1 Multi-objective Knapsack Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2007

2006

Degree-constrained decompositions of graphs: Bounded treewidth and planarity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

The satisfactory partition problem.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2006

Approximating Min-Max (Regret) Versions of Some Polynomial Problems.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 12th Annual International Conference, 2006

2005

On the differential approximation of MIN SET COVER.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness.

[BibT_eX]

[DOI]

Bruno Escoffier

Vangelis Th. Paschos

Theor. Comput. Sci., 2005

Complexity of the min-max and min-max regret assignment problems.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2005

Completeness in differential approximation classes.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2005

Approximation algorithms for some vehicle routing problems.

[BibT_eX]

[DOI]

Refael Hassin

Discret. Appl. Math., 2005

Greedy Differential Approximations for Min Set Cover.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2005: Theory and Practice of Computer Science, 2005

On the Complexity of Global Constraint Satisfaction.

[BibT_eX]

[DOI]

Marek Karpinski

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Complexity of the Min-Max (Regret) Versions of Cut Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Approximation Complexity of min-max (Regret) Versions of Shortest Path, Spanning Tree, and Knapsack.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2005

Complexity and Approximation of Satisfactory Partition Problems.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004

A note on the approximability of the toughness of graphs.

[BibT_eX]

[DOI]

Discret. Math., 2004

Poly-APX- and PTAS-Completeness in Standard and Differential Approximation.

[BibT_eX]

[DOI]

Bruno Escoffier

Vangelis Th. Paschos

Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

2003

Differential approximation for optimal satisfiability and related problems.

[BibT_eX]

[DOI]

Vangelis Th. Paschos

Eur. J. Oper. Res., 2003

On the Existence and Determination of Satisfactory Partitions in a Graph.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

Differential Approximation for Some Routing Problems.

[BibT_eX]

[DOI]

Refael Hassin

Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

2002

Efficient Approximation Algorithms for the SUBSET-SUMS EQUALITY Problem.

[BibT_eX]

[DOI]

Miklos Santha

J. Comput. Syst. Sci., 2002

2001

Partitioning vertices of 1-tough graphs into paths.

[BibT_eX]

[DOI]

Amel Harkat-Benhamdine

Theor. Comput. Sci., 2001

Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction

[BibT_eX]

[DOI]

Wenceslas Fernandez de la Vega

Marek Karpinski

Electron. Colloquium Comput. Complex., 2001

A note on the vertex-distinguishing proper coloring of graphs with large minimum degree.

[BibT_eX]

[DOI]

Amel Harkat-Benhamdine

Discret. Math., 2001

2000

On the Loebl-Komlós-Sós conjecture.

[BibT_eX]

[DOI]

J. Graph Theory, 2000

Approximability of Dense Instances of NEAREST CODEWORD Problem

[BibT_eX]

[DOI]

Wenceslas Fernandez de la Vega

Marek Karpinski

Electron. Colloquium Comput. Complex., 2000

1999

On the Vertex-Distinguishing Proper Edge-Colorings of Graphs.

[BibT_eX]

[DOI]

Amel Harkat-Benhamdine

J. Comb. Theory B, 1999

On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs.

[BibT_eX]

[DOI]

Miklos Santha

J. Algorithms, 1999

A Polynomial Time Approximation Scheme for Dense MIN 2SAT.

[BibT_eX]

[DOI]

Wenceslas Fernandez de la Vega

Proceedings of the Fundamentals of Computation Theory, 12th International Symposium, 1999

1998

On the Approximation of Finding A(nother) Hamilton Cycle in Cubic Hamilton Graphs (Extended Abstract).

[BibT_eX]

[DOI]

Miklos Santha

Proceedings of the STACS 98, 1998

1995

A Genetic Algorithm for the Maximal Clique Problem.

[BibT_eX]

[DOI]