Nos tutelles

CNRS Dauphine PSL *

Rechercher





Accueil > PERSONNES

Membres

publié le , mis à jour le

retour a la liste des membres

Cristina Bazgan

Email : Bazgan.Cristina@lamsade.dauphine.fr

Tel : 0144054090
Bureau : P409
Site Personnel: http://lamsade.dauphine.fr/~bazgan/
Pole : Optimisation combinatoire algorithmique
Status : Professeur

  • Expert IUF junior

  • Encadrement de these de doctorat :


    • Thomas Pontoizeau : Problèmes d'optimisation dans les réseaux sociaux ( Début : 2014-10-01)
    • Paul Beaujean : Conception d?architectures de réseaux optimisées et robustes face à la propagation d?instabilités ( Début : 2015-04-01)
    voir toutes les theses

    Publications Dblp


    • Cristina Bazgan, Florian Jamain, Daniel Vanderpooten
      Discrete representation of the non-dominated set for multi-objective optimization problems using kernels.European Journal of Operational Research260(3) 2017:814-827

    • Cristina Bazgan, Thomas Pontoizeau, Zsolt Tuza
      On the Complexity of Finding a Potential Community.CIAC 2017:80-91

    • Faisal N. Abu-Khzam, Cristina Bazgan, Morgan Chopin, Henning Fernau
      Data reductions and combinatorial bounds for improved approximation algorithms.J. Comput. Syst. Sci.82(3) 2016:503-520

    • Cristina Bazgan, Robert Bredereck, Sepp Hartung, André Nichterlein, Gerhard J. Woeginger
      Finding large degree-anonymous subgraphs is hard.Theor. Comput. Sci.622 2016:90-110

    • Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos
      Algorithmic Aspects of Upper Domination: A Parameterised Perspective.AAIM 2016:113-124

    • Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau
      On the Complexity Landscape of the Domination Chain.CALDAM 2016:61-72

    • Cristina Bazgan, Florent Foucaud, Florian Sikora
      On the Approximability of Partial VC Dimension.COCOA 2016:92-106

    • Faisal N. Abu-Khzam, Cristina Bazgan, Katrin Casel, Henning Fernau
      Building Clusters with Lower-Bounded Sizes.ISAAC 2016:4:1-4:13

    • Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos
      Upper Domination: Complexity and Approximation.IWOCA 2016:241-252

    • Cristina Bazgan, Florent Foucaud, Florian Sikora
      On the Approximability of Partial VC Dimension.CoRRabs/1609.05110 2016:

    • Cristina Bazgan, Cédric Bentz, Christophe Picouleau, Bernard Ries
      Blockers for the Stability Number and the Chromatic Number.Graphs and Combinatorics31(1) 2015:73-90

    • Cristina Bazgan, Florian Jamain, Daniel Vanderpooten
      Approximate Pareto sets of minimal size for multi-objective optimization problems.Oper. Res. Lett.43(1) 2015:1-6

    • Cristina Bazgan, André Nichterlein, Rolf Niedermeier
      A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths.CIAC 2015:47-60

    • Cristina Bazgan, Janka Chlebíková, Thomas Pontoizeau
      New Insight into 2-Community Structures in Graphs with Applications in Social Networks.COCOA 2015:236-250

    • Faisal N. Abu-Khzam, Cristina Bazgan, Joyce El Haddad, Florian Sikora
      On the Complexity of QoS-Aware Service Selection Problem.ICSOC 2015:345-352

    • Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos
      Algorithmic Aspects of Upper Domination.CoRRabs/1506.07260 2015:

    • Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora
      Parameterized Inapproximability of Target Set Selection and Generalizations.Computability3(2) 2014:135-145

    • Cristina Bazgan, Morgan Chopin
      The complexity of finding harmless individuals in social networks.Discrete Optimization14 2014:170-182

    • Cristina Bazgan, Morgan Chopin, Marek Cygan, Michael R. Fellows, Fedor V. Fomin, Erik Jan van Leeuwen
      Parameterized complexity of firefighting.J. Comput. Syst. Sci.80(7) 2014:1285-1297

    • Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora
      Parameterized approximability of maximizing the spread of influence in networks.J. Discrete Algorithms27 2014:54-65

    • Enrico Angelelli, Cristina Bazgan, Maria Grazia Speranza, Zsolt Tuza
      Complexity and approximation for Traveling Salesman Problems with profits.Theor. Comput. Sci.531 2014:54-65

    • Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora
      Parameterized Inapproximability of Target Set Selection and Generalizations.CiE 2014:11-20

    • Faisal N. Abu-Khzam, Cristina Bazgan, Morgan Chopin, Henning Fernau
      Approximation Algorithms Inspired by Kernelization Methods.ISAAC 2014:479-490

    • Cristina Bazgan, André Nichterlein
      Parameterized Inapproximability of Degree Anonymization.IPEC 2014:75-84

    • Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora
      Parameterized Inapproximability of Target Set Selection and Generalizations.CoRRabs/1403.3565 2014:

    • Faisal N. Abu-Khzam, Cristina Bazgan, Morgan Chopin, Henning Fernau
      Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms.CoRRabs/1409.3742 2014:

    • Cristina Bazgan, Morgan Chopin, Bernard Ries
      The firefighter problem with more than one firefighter on trees.Discrete Applied Mathematics161(7-8) 2013:899-908

    • Cristina Bazgan, Florian Jamain, Daniel Vanderpooten
      On the number of non-dominated points of a multicriteria optimization problem.Discrete Applied Mathematics161(18) 2013:2841-2850

    • Cristina Bazgan, Sonia Toubaline, Daniel Vanderpooten
      Complexity of determining the most vital elements for the p-median and p-center location problems.J. Comb. Optim.25(2) 2013:191-207

    • Cristina Bazgan, Sonia Toubaline, Daniel Vanderpooten
      Critical edges/nodes for the minimum spanning tree problem: complexity and approximation.J. Comb. Optim.26(1) 2013:178-189

    • Cristina Bazgan, Laurent Gourvès, Jérôme Monnot
      Approximation with a fixed number of solutions of some multiobjective maximization problems.J. Discrete Algorithms22 2013:19-29

    • Cristina Bazgan, Sonia Toubaline, Daniel Vanderpooten
      Critical edges for the assignment problem: Complexity and exact resolution.Oper. Res. Lett.41(6) 2013:685-689

    • Cristina Bazgan, Laurent Gourvès, Jérôme Monnot, Fanny Pascual
      Single approximation for the biobjective Max TSP.Theor. Comput. Sci.478 2013:41-50

    • Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora
      Parameterized Approximability of Maximizing the Spread of Influence in Networks.COCOON 2013:543-554

    • Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora
      Parameterized Approximability of Maximizing the Spread of Influence in NetworksCoRRabs/1303.6907 2013:

    • Cristina Bazgan, Sonia Toubaline, Daniel Vanderpooten
      Efficient determination of the k most vital edges for the minimum spanning tree problem.Computers & OR39(11) 2012:2888-2898

    • Cristina Bazgan, Morgan Chopin
      The Robust Set Problem: Parameterized Complexity and Approximation.MFCS 2012:136-147

    • Cristina Bazgan, Sonia Toubaline, Zsolt Tuza
      The most vital nodes with respect to independent set and vertex cover.Discrete Applied Mathematics159(17) 2011:1933-1946

    • Cristina Bazgan, Basile Couëtoux, Zsolt Tuza
      Complexity and approximation of the Constrained Forest problem.Theor. Comput. Sci.412(32) 2011:4081-4091

    • Cristina Bazgan, Sonia Toubaline, Daniel Vanderpooten
      Efficient Algorithms for Finding the Most Vital Edges for the Minimum Spanning Tree Problem.COCOA 2011:126-140

    • Cristina Bazgan, Morgan Chopin, Michael R. Fellows
      Parameterized Complexity of the Firefighter Problem.ISAAC 2011:643-652

    • Cristina Bazgan, Laurent Gourvès, Jérôme Monnot, Fanny Pascual
      Single Approximation for Biobjective Max TSP.WAOA 2011:49-62

    • Cristina Bazgan, Laurent Gourvès, Jérôme Monnot
      Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems.WAOA 2011:233-246

    • Cristina Bazgan, Morgan Chopin, Bernard Ries
      The firefighter problem with more than one firefighter on treesCoRRabs/1110.0341 2011:

    • Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten
      General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems.Discrete Optimization7(3) 2010:136-148

    • Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten
      Satisfactory graph partition, variants, and generalizations.European Journal of Operational Research206(2) 2010:271-280

    • Cristina Bazgan, Sonia Toubaline, Daniel Vanderpooten
      Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems.COCOA (1) 2010:237-251

    • Cristina Bazgan, Sonia Toubaline, Zsolt Tuza
      Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures.IWOCA 2010:154-166

    • Cristina Bazgan, Hadrien Hugot, Daniel Vanderpooten
      Solving efficiently the 0-1 multi-objective knapsack problem.Computers & OR36(1) 2009:260-279

    • Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten
      Min-max and min-max regret versions of combinatorial optimization problems: A survey.European Journal of Operational Research197(2) 2009:427-438

    • Cristina Bazgan, Hadrien Hugot, Daniel Vanderpooten
      Implementing an efficient fptas for the 0-1 multi-objective knapsack problem.European Journal of Operational Research198(1) 2009:47-56

    • Cristina Bazgan, Basile Couëtoux, Zsolt Tuza
      Covering a Graph with a Constrained Forest (Extended Abstract).ISAAC 2009:892-901

    • Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten
      Complexity of the min-max (regret) versions of min cut problems.Discrete Optimization5(1) 2008:66-73

    • Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten
      Approximation of satisfactory bisection problems.J. Comput. Syst. Sci.74(5) 2008:875-883

    • Cristina Bazgan, Zsolt Tuza
      Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3.J. Discrete Algorithms6(3) 2008:510-519

    • Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten
      Efficient algorithms for decomposing graphs under degree constraints.Discrete Applied Mathematics155(8) 2007:979-988

    • Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten
      Approximation of min-max and min-max regret versions of some combinatorial optimization problems.European Journal of Operational Research179(2) 2007:281-290

    • Cristina Bazgan, Hadrien Hugot, Daniel Vanderpooten
      A Practical Efficient Fptas for the 0-1 Multi-objective Knapsack Problem.ESA 2007:717-728

    • Cristina Bazgan, Hadrien Hugot, Daniel Vanderpooten
      An Efficient Implementation for the 0-1 Multi-objective Knapsack Problem.WEA 2007:406-419

    • Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten
      The satisfactory partition problem.Discrete Applied Mathematics154(8) 2006:1236-1245

    • Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten
      Degree-constrained decompositions of graphs: Bounded treewidth and planarity.Theor. Comput. Sci.355(3) 2006:389-395

    • Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten
      Approximating Min-Max (Regret) Versions of Some Polynomial Problems.COCOON 2006:428-438

    • Cristina Bazgan, Refael Hassin, Jérôme Monnot
      Approximation algorithms for some vehicle routing problems.Discrete Applied Mathematics146(1) 2005:27-42

    • Giorgio Ausiello, Cristina Bazgan, Marc Demange, Vangelis Th. Paschos
      Completeness in differential approximation classes.Int. J. Found. Comput. Sci.16(6) 2005:1267-1295

    • Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten
      Complexity of the min-max and min-max regret assignment problems.Oper. Res. Lett.33(6) 2005:634-640

    • Cristina Bazgan, Jérôme Monnot, Vangelis Th. Paschos, Fabrice Serrière
      On the differential approximation of MIN SET COVER.Theor. Comput. Sci.332(1-3) 2005:497-513

    • Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos
      Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness.Theor. Comput. Sci.339(2-3) 2005:272-292

    • Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten
      Complexity and Approximation of Satisfactory Partition Problems.COCOON 2005:829-838

    • Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten
      Approximation Complexity of min-max (Regret) Versions of Shortest Path, Spanning Tree, and Knapsack.ESA 2005:862-873

    • Cristina Bazgan, Marek Karpinski
      On the Complexity of Global Constraint Satisfaction.ISAAC 2005:624-633

    • Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten
      Complexity of the Min-Max (Regret) Versions of Cut Problems.ISAAC 2005:789-798

    • Cristina Bazgan, Jérôme Monnot, Vangelis Th. Paschos, Fabrice Serrière
      Greedy Differential Approximations for Min Set Cover.SOFSEM 2005:62-71

    • Cristina Bazgan
      A note on the approximability of the toughness of graphs.Discrete Mathematics280(1-3) 2004:215-218

    • Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos
      Poly-APX- and PTAS-Completeness in Standard and Differential Approximation.ISAAC 2004:124-136

    • Cristina Bazgan, Vangelis Th. Paschos
      Differential approximation for optimal satisfiability and related problems.European Journal of Operational Research147(2) 2003:397-404

    • Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski
      Polynomial time approximation schemes for dense instances of minimum constraint satisfaction.Random Struct. Algorithms23(1) 2003:73-91

    • Cristina Bazgan, Refael Hassin, Jérôme Monnot
      Differential Approximation for Some Routing Problems.CIAC 2003:277-288

    • Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten
      On the Existence and Determination of Satisfactory Partitions in a Graph.ISAAC 2003:444-453

    • Giorgio Ausiello, Cristina Bazgan, Marc Demange, Vangelis Th. Paschos
      Completeness in Differential Approximation Classes.MFCS 2003:179-188

    • Cristina Bazgan, Miklos Santha, Zsolt Tuza
      Efficient Approximation Algorithms for the SUBSET-SUMS EQUALITY Problem.J. Comput. Syst. Sci.64(2) 2002:160-170

    • Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski
      Approximability of Dense Instances of NEAREST CODEWORD Problem.SWAT 2002:298-307

    • Cristina Bazgan, Amel Harkat-Benhamdine, Hao Li, Mariusz Wozniak
      A note on the vertex-distinguishing proper coloring of graphs with large minimum degree.Discrete Mathematics236(1-3) 2001:37-42

    • Cristina Bazgan, Amel Harkat-Benhamdine, Hao Li, Mariusz Wozniak
      Partitioning vertices of 1-tough graphs into paths.Theor. Comput. Sci.263(1-2) 2001:255-261

    • Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski
      Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint SatisfactionElectronic Colloquium on Computational Complexity (ECCC)8(34) 2001:

    • Cristina Bazgan, Hao Li, Mariusz Wozniak
      On the Loebl-Komlós-Sós conjecture.Journal of Graph Theory34(4) 2000:269-276

    • Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski
      Approximability of Dense Instances of NEAREST CODEWORD ProblemElectronic Colloquium on Computational Complexity (ECCC)7(91) 2000:

    • Cristina Bazgan, Miklos Santha, Zsolt Tuza
      On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs.J. Algorithms31(1) 1999:249-268

    • Cristina Bazgan, Amel Harkat-Benhamdine, Hao Li, Mariusz Wozniak
      On the Vertex-Distinguishing Proper Edge-Colorings of Graphs.J. Comb. Theory, Ser. B75(2) 1999:288-301

    • Cristina Bazgan, Wenceslas Fernandez de la Vega
      A Polynomial Time Approximation Scheme for Dense MIN 2SAT.FCT 1999:91-99

    • Cristina Bazgan, Miklos Santha, Zsolt Tuza
      Efficient Approximation Algorithms for the Subset-Sums Equality Problem.ICALP 1998:387-396

    • Cristina Bazgan, Miklos Santha, Zsolt Tuza
      On the Approximation of Finding A(nother) Hamilton Cycle in Cubic Hamilton Graphs (Extended Abstract).STACS 1998:276-286



    Publications DFIS


    Publications HAL