Cristina Bazgan

Affiliations:
  • Université Paris Dauphine, France


According to our database1, Cristina Bazgan authored at least 100 papers between 1995 and 2022.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2022
The Power of the Weighted Sum Scalarization for Approximating Multiobjective Optimization Problems.
Theory Comput. Syst., 2022

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

2021
Degree-anonymization using edge rotations.
Theor. Comput. Sci., 2021

One-exact approximate Pareto sets.
J. Glob. Optim., 2021

Dense Graph Partitioning on sparse and dense graphs.
CoRR, 2021

Monte Carlo Search Algorithms for Network Traffic Engineering.
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.
Inf. Process. Lett., 2020

Domination chain: Characterisation, classical complexity, parameterised complexity and approximability.
Discret. Appl. Math., 2020

Parameterized Dynamic Variants of Red-Blue Dominating Set.
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.
Proceedings of the Combinatorial Optimization and Applications, 2020

2019
Finding a potential community in networks.
Theor. Comput. Sci., 2019

Parameterized and approximation complexity of Partial VC Dimension.
Theor. Comput. Sci., 2019

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

Aspects of upper defensive alliances.
Discret. Appl. Math., 2019

Proportionally dense subgraph of maximum size: Complexity and approximation.
Discret. Appl. Math., 2019

An FPTAS for a General Class of Parametric Optimization Problems.
Proceedings of the Computing and Combinatorics - 25th International Conference, 2019

2018
The many facets of upper domination.
Theor. Comput. Sci., 2018

Structural and Algorithmic Properties of 2-Community Structures.
Algorithmica, 2018

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

Relaxation and Matrix Randomized Rounding for the Maximum Spectral Subgraph Problem.
Proceedings of the Combinatorial Optimization and Applications, 2018

2017
Discrete representation of the non-dominated set for multi-objective optimization problems using kernels.
Eur. J. Oper. Res., 2017

On the Complexity of Finding a Potential Community.
Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

2016
Finding large degree-anonymous subgraphs is hard.
Theor. Comput. Sci., 2016

Data reductions and combinatorial bounds for improved approximation algorithms.
J. Comput. Syst. Sci., 2016

Upper Domination: Complexity and Approximation.
Proceedings of the Combinatorial Algorithms - 27th International Workshop, 2016

Building Clusters with Lower-Bounded Sizes.
Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

On the Approximability of Partial VC Dimension.
Proceedings of the Combinatorial Optimization and Applications, 2016

On the Complexity Landscape of the Domination Chain.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2016

Algorithmic Aspects of Upper Domination: A Parameterised Perspective.
Proceedings of the Algorithmic Aspects in Information and Management, 2016

2015
Approximate Pareto sets of minimal size for multi-objective optimization problems.
Oper. Res. Lett., 2015

Blockers for the Stability Number and the Chromatic Number.
Graphs Comb., 2015

Algorithmic Aspects of Upper Domination.
CoRR, 2015

On the Complexity of QoS-Aware Service Selection Problem.
Proceedings of the Service-Oriented Computing - 13th International Conference, 2015

New Insight into 2-Community Structures in Graphs with Applications in Social Networks.
Proceedings of the Combinatorial Optimization and Applications, 2015

A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths.
Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

2014
Complexity and approximation for Traveling Salesman Problems with profits.
Theor. Comput. Sci., 2014

Parameterized approximability of maximizing the spread of influence in networks.
J. Discrete Algorithms, 2014

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

The complexity of finding harmless individuals in social networks.
Discret. Optim., 2014

Parameterized Inapproximability of Target Set Selection and Generalizations.
Comput., 2014

Parameterized Inapproximability of Degree Anonymization.
Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

Approximation Algorithms Inspired by Kernelization Methods.
Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

2013
Single approximation for the biobjective Max TSP.
Theor. Comput. Sci., 2013

Critical edges for the assignment problem: Complexity and exact resolution.
Oper. Res. Lett., 2013

Approximation with a fixed number of solutions of some multiobjective maximization problems.
J. Discrete Algorithms, 2013

Critical edges/nodes for the minimum spanning tree problem: complexity and approximation.
J. Comb. Optim., 2013

Complexity of determining the most vital elements for the p-median and p-center location problems.
J. Comb. Optim., 2013

On the number of non-dominated points of a multicriteria optimization problem.
Discret. Appl. Math., 2013

The firefighter problem with more than one firefighter on trees.
Discret. Appl. Math., 2013

2012
Efficient determination of the k most vital edges for the minimum spanning tree problem.
Comput. Oper. Res., 2012

The Robust Set Problem: Parameterized Complexity and Approximation.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2011
Complexity and approximation of the Constrained Forest problem.
Theor. Comput. Sci., 2011

The most vital nodes with respect to independent set and vertex cover.
Discret. Appl. Math., 2011

Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems.
Proceedings of the Approximation and Online Algorithms - 9th International Workshop, 2011

Parameterized Complexity of the Firefighter Problem.
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.
Proceedings of the Combinatorial Optimization and Applications, 2011

2010
Satisfactory graph partition, variants, and generalizations.
Eur. J. Oper. Res., 2010

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

Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures.
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.
Proceedings of the Combinatorial Optimization and Applications, 2010

2009
Implementing an efficient fptas for the 0-1 multi-objective knapsack problem.
Eur. J. Oper. Res., 2009

Min-max and min-max regret versions of combinatorial optimization problems: A survey.
Eur. J. Oper. Res., 2009

Solving efficiently the 0-1 multi-objective knapsack problem.
Comput. Oper. Res., 2009

Covering a Graph with a Constrained Forest (Extended Abstract).
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008
Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3.
J. Discrete Algorithms, 2008

Approximation of satisfactory bisection problems.
J. Comput. Syst. Sci., 2008

Complexity of the min-max (regret) versions of min cut problems.
Discret. Optim., 2008

2007
Approximation of min-max and min-max regret versions of some combinatorial optimization problems.
Eur. J. Oper. Res., 2007

Efficient algorithms for decomposing graphs under degree constraints.
Discret. Appl. Math., 2007

An Efficient Implementation for the 0-1 Multi-objective Knapsack Problem.
Proceedings of the Experimental Algorithms, 6th International Workshop, 2007

A Practical Efficient Fptas for the 0-1 Multi-objective Knapsack Problem.
Proceedings of the Algorithms, 2007

2006
Degree-constrained decompositions of graphs: Bounded treewidth and planarity.
Theor. Comput. Sci., 2006

The satisfactory partition problem.
Discret. Appl. Math., 2006

Approximating Min-Max (Regret) Versions of Some Polynomial Problems.
Proceedings of the Computing and Combinatorics, 12th Annual International Conference, 2006

2005
On the differential approximation of MIN SET COVER.
Theor. Comput. Sci., 2005

Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness.
Theor. Comput. Sci., 2005

Complexity of the min-max and min-max regret assignment problems.
Oper. Res. Lett., 2005

Completeness in differential approximation classes.
Int. J. Found. Comput. Sci., 2005

Approximation algorithms for some vehicle routing problems.
Discret. Appl. Math., 2005

Greedy Differential Approximations for Min Set Cover.
Proceedings of the SOFSEM 2005: Theory and Practice of Computer Science, 2005

On the Complexity of Global Constraint Satisfaction.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Complexity of the Min-Max (Regret) Versions of Cut Problems.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

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

Complexity and Approximation of Satisfactory Partition Problems.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004
A note on the approximability of the toughness of graphs.
Discret. Math., 2004

Poly-APX- and PTAS-Completeness in Standard and Differential Approximation.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

2003
Differential approximation for optimal satisfiability and related problems.
Eur. J. Oper. Res., 2003

On the Existence and Determination of Satisfactory Partitions in a Graph.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

Differential Approximation for Some Routing Problems.
Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

2002
Efficient Approximation Algorithms for the SUBSET-SUMS EQUALITY Problem.
J. Comput. Syst. Sci., 2002

2001
Partitioning vertices of 1-tough graphs into paths.
Theor. Comput. Sci., 2001

Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction
Electron. Colloquium Comput. Complex., 2001

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

2000
On the Loebl-Komlós-Sós conjecture.
J. Graph Theory, 2000

Approximability of Dense Instances of NEAREST CODEWORD Problem
Electron. Colloquium Comput. Complex., 2000

1999
On the Vertex-Distinguishing Proper Edge-Colorings of Graphs.
J. Comb. Theory, Ser. B, 1999

On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs.
J. Algorithms, 1999

A Polynomial Time Approximation Scheme for Dense MIN 2SAT.
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).
Proceedings of the STACS 98, 1998

1995
A Genetic Algorithm for the Maximal Clique Problem.
Proceedings of the Artificial Neural Nets and Genetic Algorithms, 1995


  Loading...