Publications

International journals

  • Structural and algorithmic properties of 2-community structures
    C. Bazgan, J. Chlebikova et T. Pontoizeau,
    Algorithmica, to appear
  • Discrete representation of the non-dominated set for multiobjective optimization problems using kernels
    C. Bazgan, F. Jamain et D. Vanderpooten,
    European Journal of Operation Research, to appear
  • Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms
    F. Abu-Khzam, C. Bazgan, M. Chopin et H. Fernau,
    Journal of Computer and System Sciences, 82(3), pp. 503-520, 2016
  • Finding large degree-anonymous subgraphs is hard
    C. Bazgan, R. Bredereck, S. Hartung, A. Nichterlein et G. Woeginger,
    Theoretical Computer Science, 622, pp. 90-110, 2016
  • Blockers for the stability number and the chromatic number
    C. Bazgan, C. Bentz, Ch. Picouleau et B. Ries,
    Graphs and Combinatorics, 31(1), pp. 73-90, 2015
  • Approximate Pareto sets of minimal size for multi-objective optimization problems
    C. Bazgan, F. Jamain et D. Vanderpooten,
    Operations Research Letters, 43(1), pp. 1-6, 2015
  • The Complexity of Finding Harmless Individuals in Social Networks
    C. Bazgan et M. Chopin,
    Discrete Optimization, 14, pp. 170-182, 2014
  • Parameterized Complexity of Firefighting
    C. Bazgan, M. Chopin, M. Cygan, M. Fellows, F. Fomin, E. Jan van Leeuwen
    Journal of Computer and System Sciences, 80(7), pp. 1285-1297, 2014
  • Parameterized Inapproximability of Target Set Selection and Generalizations
    C. Bazgan, M. Chopin, A. Nichterlein et F. Sikora,
    Computability, 3(2), pp. 135--145, 2014
  • Complexity and approximation for Traveling Salesman Problems with profits
    E. Angelelli, C. Bazgan, M. G. Speranza, Z. Tuza,
    Theoretical Computer Science, 531, pp. 54-65, 2014
  • Parameterized approximability of maximizing the spread of influence in networks
    C. Bazgan, M. Chopin, A. Nichterlein et F. Sikora,
    Journal of Discrete Algorithms, 27, pp. 54-65, 2014
  • On the number of non-dominated points of a multicriteria optimization problem
    C. Bazgan, F. Jamain et D. Vanderpooten,
    Discrete Applied Mathematics, 161(18), pp. 2841-2850, 2013
  • Approximation with a fixed number of solutions of some multiobjective maximization problems
    C. Bazgan, L. Gourvès et J. Monnot,
    Journal of Discrete Algorithms, 22, pp. 19-29, 2013
  • The firefighter problem with more than one firefighter on trees
    C. Bazgan, M. Chopin et B. Ries,
    Discrete Applied Mathematics, 161(7-8), pp. 899-908, 2013
  • Critical edges for the assignment problem: Complexity and exact resolution
    C. Bazgan, S. Toubaline et D. Vanderpooten,
    Operations Research Letters, 41(6), pp. 685-689, 2013
  • Single approximation for the biobjective Max TSP
    C. Bazgan, L. Gourvès, J. Monnot et F. Pascual,
    Theoretical Computer Science , 478, pp. 41-50, 2013
  • Complexity of determining the most vital elements for the p-median and p-center location problems
    C. Bazgan, S. Toubaline et D. Vanderpooten,
    Journal of Combinatorial Optimization , 25(2), pp. 191-207, 2013
  • Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
    C. Bazgan, S. Toubaline et D. Vanderpooten,
    Journal of Combinatorial Optimization , 26(1), pp. 178-189, 2013
  • Efficient determination of the k most vital edges for the minimum spanning tree problem
    C. Bazgan, S. Toubaline et D. Vanderpooten,
    Computers and Operations Research , 39(11), pp. 2888-2898, 2012
  • The most vital nodes with respect to independent set and vertex cover
    C. Bazgan, S. Toubaline et Zs. Tuza,
    Discrete Applied Mathematics, 159(17), pp. 1933-1946, 2011
  • Complexity and approximation of the constrained forest problem
    C. Bazgan, B. Couëtoux et Zs. Tuza,
    Theoretical Computer Science, 412(32), pp. 4081-4091, 2011
  • General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems
    H. Aissi, C. Bazgan et D. Vanderpooten
    Discrete Optimization, 7(3), pp. 136-148, 2010
  • Satisfactory graph partition, variants, and generalizations
    C. Bazgan, Zs. Tuza et D. Vanderpooten
    European Journal of Operation Research, 206(2), pp. 271-280, 2010
  • Min-max and min-max regret versions of combinatorial optimization problems: a survey
    H. Aissi, C. Bazgan et D. Vanderpooten
    European Journal of Operation Research, 197(2), pp. 427-438, 2009
  • Implementing an efficient fptas for the 0-1 multi-objective knapsack problem
    C. Bazgan, H.Hugot et D. Vanderpooten
    European Journal of Operation Research , 198(1), pp. 47-56, 2009
  • Solving efficiently the 0-1 multi-objective knapsack problem
    C. Bazgan, H.Hugot et D. Vanderpooten
    Computers and Operations Research, 36(1), pp. 260-279, 2009
  • Approximation of satisfactory bisection problems
    C. Bazgan, Zs. Tuza et D. Vanderpooten
    Journal of Computer and System Sciences, 74(5), pp. 875-883, 2008
  • Complexity of the min-max (regret) versions of min cut problems
    H. Aissi, C. Bazgan et D. Vanderpooten
    Discrete Optimization, 5(1), pp. 66-73, 2008
  • Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
    C. Bazgan et Zs. Tuza
    Journal of Discrete Algorithms, 6(3), pp. 510-519, 2008
  • Efficient algorithms for decomposing graphs under degree constraints
    C. Bazgan, Zs. Tuza et D. Vanderpooten
    Discrete Applied Mathematics, 155(8), pp. 979-988, 2007
  • Approximation of min-max and min-max regret versions of some combinatorial optimization problems
    H. Aissi, C. Bazgan and D. Vanderpooten
    European Journal of Operation Research, 179(2), pp. 281-290, 2007
  • Degree-constrained decompositions of graphs: bounded treewidth and planarity
    C. Bazgan, Zs. Tuza and D. Vanderpooten
    Theoretical Computer Science , 355(3), pp. 389-395, 2006
  • The satisfactory partition problem
    C. Bazgan, Zs. Tuza and D. Vanderpooten
    Discrete Applied Mathematics, 154(8), pp. 1236-1245, 2006
  • Completeness in differential approximation classes
    G. Ausiello, C. Bazgan, M. Demange and V. Paschos
    International Journal of Foundations of Computer Science, 16(6), pp. 1267-1295, 2005
  • Complexity of the min-max and min-max regret assignment problems
    H. Aissi, C. Bazgan and D. Vanderpooten
    Operations Research Letters, 33(6), pp. 634-640, 2005
  • Completeness in standard and differential approximation classes: Poly-(D)APX and (D)PTAS-completeness
    C. Bazgan, B. Escoffier and V. Paschos
    Theoretical Computer Science , 339(2-3), pp. 272-292, 2005
  • On the differential approximation of Min Set Cover
    C. Bazgan, J. Monnot, V. Paschos and F. Serrière
    Theoretical Computer Science , 332(1-3), pp. 497-513, 2005
  • Approximation algorithms for some vehicle routing problems
    C. Bazgan, J. Monnot and R. Hassin
    Discrete Applied Mathematics , 146(1), pp. 27-42, 2005
  • A note on the approximability of the toughness of graphs
    C. Bazgan
    Discrete Mathematics , 280(1-3), pp. 215-218, 2004
  • Polynomial time approximation schemes for dense instances of the minimum constraint satisfaction
    C. Bazgan, W. Fernandez de la Vega and M. Karpinski
    Random Structures and Algorithms , 23(1), pp. 73-91, 2003
  • Differential approximation for satisfiability and related problems
    C. Bazgan and V. Paschos
    European Journal of Operational Research , 147(2), pp. 397-404, 2003
  • Efficient approximation algorithms for the Subset-Sums Equality problem
    C. Bazgan, M. Santha and Zs. Tuza
    Journal of Computer and System Sciences, 64(2), pp. 160-170, 2002
  • Partitionning vertices of 1-tough graphs into paths
    C. Bazgan, A. Harkat-Benhamdine, H. Li and M. Wozniak
    Theoretical Computer Science , 263(1-2), pp. 255-261, 2001
  • A note on the vertex-distinguishing proper edge-colorings of graphs with large minimum degree
    C. Bazgan, A. Harkat-Benhamdine, H. Li and M. Wozniak
    Discrete Mathematics, 236(1-3), pp. 37-42, 2001
  • On the Loebl-Komlos-Sos conjecture
    C. Bazgan, H. Li and M. Wozniak
    Journal of Graph Theory, 34(4), pp. 269-276, 2000
  • On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs
    C. Bazgan, M. Santha and Zs. Tuza,
    Journal of Algorithms , 31(1), pp. 249-268, 1999
  • On the vertex-distinguishing proper edge-colorings of graphs
    C. Bazgan, A. Harkat-Benhamdine, H. Li and M. Wozniak
    Journal of Combinatorial Theory B , 75(2), pp. 288-301, 1999
  • International conferences

  • On the complexity of finding a potential community
    C. Bazgan, T. Pontoizeau et Zs. Tuza,
    Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017), to appear
  • Building Clusters with Lower-bounded Sizes
    F. Abu-Khzam, C. Bazgan, K. Casel et H. Fernau
    Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016), LIPIcs 64, pp. 4:1-4:13.
  • On the Approximability of Partial VC Dimension
    C. Bazgan, F. Foucaud, F. Sikora
    Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016), LNCS 10043, pp. 92-106
  • Upper Domination: Complexity and Approximation
    C. Bazgan, L.Brankovic, K.Casel, H. Fernau, K. Jansen, K-M. Klein, M. Lampis, M. Liedloff, J. Monnot, V.Paschos
    Proceedings of the 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), LNCS 9843, pp. 241-252
  • Algorithmic Aspects of Upper Domination: A Parameterised Perspective
    C. Bazgan, L.Brankovic, K.Casel, H. Fernau, K. Jansen, K-M. Klein, M. Lampis, M. Liedloff, J. Monnot, V.Paschos
    Proceedings of the 11th International Conference on Algorithmic Aspects in Information and Management (AAIM 2016), LNCS 9778, pp. 113-124
  • On the Complexity Landscape of the Domination Chain
    C. Bazgan, L. Brankovic, K. Casel et H. Fernau,
    Proceedings of the 2nd International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2016), LNCS 9602, pp. 61-72
  • New Insight into 2-Community Structures in Graphs with Applications in Social Networks
    C. Bazgan, J. Chlebíková et T. Pontoizeau,
    Proceedings of the 9th International Conference Combinatorial Optimization and Applications (COCOA 2015), LNCS 9486, pp. 236-250
  • On the Complexity of QoS-Aware Service Selection Problem
    F. Abu-Khzam, C. Bazgan, J. El Haddad et F. Sikora
    Proceedings of the 13th International Conference Service-Oriented Computing (ICSOC 2015), LNCS 9435, pp. 345-352
  • A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
    C. Bazgan, A. Nichterlein et R. Niedermeier
    Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC 2015), LNCS 9486, pp. 47-60
  • Parameterized Inapproximability of Degree Anonymization
    C. Bazgan et A. Nichterlein
    Proceedings of the 9th International Symposium on Parameterized and Exact Computation (IPEC 2014), LNCS 8894, pp. 75--84
  • Approximation Algorithms Inspired by Kernelization Methods
    F. N. Abu-Khzam, C. Bazgan, M. Chopin, H. Fernau
    Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014), LNCS 8889, pp. 479--490
  • Parameterized Inapproximability of Target Set Selection and Generalizations
    C. Bazgan, M. Chopin, A. Nichterlein et F. Sikora
    Proceedings of the 10th International Conference on Computability in Europe (CIE 2014), LNCS 8493, pp. 11--20
  • Parameterized Approximability of Maximizing the Spread of Influence in Networks
    C. Bazgan, M. Chopin, A. Nichterlein et F. Sikora
    Proceedings of the 19th International Conference on Computing and Combinatorics (COCOON 2013), LNCS 7936, pp. 543--554
  • The robust set problem: parameterized complexity and approximation
    C. Bazgan et M. Chopin
    Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012), LNCS 7464, pp. 136--147
  • Parameterized complexity of the firefighter problem
    C. Bazgan, M. Chopin et M. Fellows
    Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011), LNCS 7074, pp. 643--652
  • Approximation with a fixed number of solutions of some biobjective maximization problems
    C. Bazgan, L. Gourves et J. Monnot
    Proceedings of the 9th Workshop on Approximation and Online Algorithms (WAOA 2011), LNCS 7164, pp. 233--246
  • Single approximation for Multiobjective Max TSP
    C. Bazgan, L. Gourves, J. Monnot et F. Pascual
    Proceedings of the 9th Workshop on Approximation and Online Algorithms (WAOA 2011), LNCS 7164, pp. 49--62
  • Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem
    C. Bazgan, S. Toubaline et D. Vanderpooten
    Proceedings of the 5th International Conference on Combinatorial Optimization and Applications (COCOA 2011), LNCS 6831, pp. 126-140
  • Complexity of most vital nodes for independent set on tree structures
    C. Bazgan, S. Toubaline et Zs. Tuza
    Proceedings of the 21st International Workshop on Combinatorial Algorithms (IWOCA 2010), LNCS 6460, pp. 154-166
  • Complexity of determining the most vital elements for the 1-median and 1-center location problems
    C. Bazgan, S. Toubaline et D. Vanderpooten
    Proceedings of the 4th International Conference on Combinatorial Optimization and Applications (COCOA 2010), LNCS 6508, part I, pp. 237-251
  • Covering a graph with a constrained forest
    C. Bazgan, B. Couëtoux et Zs. Tuza
    Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC 2009), LNCS 5878, pp. 892-901
  • A practical efficient fptas for the 0-1 multi-objective knapsack problem
    C. Bazgan, H.Hugot et D. Vanderpooten
    Proceedings of the 15th Annual European Symposium on Algorithms (ESA 2007), LNCS 4698, pp. 717-728
  • An efficient implementation for the 0-1 multi-objective knapsack problem
    C. Bazgan, H.Hugot et D. Vanderpooten
    Proceedings of the 6th Workshop on Experimental Algorithms (WEA 2007), LNCS 4525, pp. 406-419
  • Approximating min-max (regret) versions of some polynomial problems
    H. Aissi, C. Bazgan and D. Vanderpooten
    Proceedings of the 12th International Computing and Combinatorics Conference (COCOON 2006), LNCS 4112, pp. 428-438
  • On the Complexity of Global Constraint Satisfaction
    C. Bazgan and M. Karpinski
    Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), LNCS 3827, pp. 624-633
  • Complexity of the min-max (regret) versions of cut problems
    H. Aissi, C. Bazgan and D. Vanderpooten
    Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), LNCS 3827, pp. 789-798
  • Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack
    H. Aissi, C. Bazgan and D. Vanderpooten
    Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005), LNCS 3669, pp. 862-873
  • Complexity and approximation of satisfactory partition problems
    C. Bazgan, Zs. Tuza and D. Vanderpooten
    Proceedings of the 11th International Computing and Combinatorics Conference (COCOON 2005), LNCS 3595, pp. 829-838
  • Pseudo-polynomial time algorithms for min-max and min-max regret problems
    H. Aissi, C. Bazgan and D. Vanderpooten
    The 5th International Symposium on Operations Research and Its Applications (ISORA 2005), LNOR 5, pp. 171-178
  • Greedy differential approximations for Min Set Cover
    C. Bazgan, J. Monnot, V. Paschos and F. Serrière
    Proceedings of the 31st Annual Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2005), LNCS 3381, pp. 62-71
  • PolyAPX and PTAS-completeness in standard and differential approximation
    C. Bazgan, B. Escoffier and V. Paschos
    Proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004), LNCS 3341, pp. 124-136
  • On the existence and determination of satisfactory partitions in a graph
    C. Bazgan, Zs. Tuza and D. Vanderpooten
    Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), LNCS 2906, pp. 444-453
  • Completeness in differential approximation classes
    G. Ausiello, C. Bazgan, M. Demange and V. Paschos
    Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), LNCS 2747, pp. 179-188
  • Differential Approximation for some vehicle routing problems
    C. Bazgan, R. Hassin and J. Monnot
    Proceedings of the 5th Conference on Algorithms and Complexity (CIAC 2003), LNCS 2653, pp. 277-288
  • Approximability of Dense Instances of Nearest Codeword Problem
    C. Bazgan, W. Fernandez de la Vega and M. Karpinski
    Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT 2002), LNCS 2368, pp. 298-307
  • Differential approximation for satisfiability and related problem
    C. Bazgan and V. Paschos
    6th Balkan Conference on Operations Research 2002, 6 pages
  • A polynomial time approximation scheme for dense Min 2Sat
    C. Bazgan and W. Fernandez de la Vega
    Proceedings of the 12th International Symposium on the Fundamentals of Computation Theory (FCT 1999), LNCS 1684, pp. 91-99
  • On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs
    C. Bazgan, M. Santha and Zs. Tuza
    Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998) , LNCS 1373, pp. 276-286
  • Efficient approximation algorithms for the Subset-Sums Equality problem
    C. Bazgan, M. Santha and Zs. Tuza
    Proceedings of the 25th International Colloquium on Automata, Languages, and Programming (ICALP 1998) , LNCS 1443, pp. 387-396
  • A genetic algorithm for the maximal clique problem
    C. Bazgan and H. Luchian
    International Conference on Artificial Neural Networks and Genetic Algorithms (ICANNGA 1995) , pp. 499-502
  • Book chapter

  • Satisfaisabilité optimale
    C. Bazgan
    Optimisation Combinatoire : problèmes paradigmatiques et nouvelles problématiques, Hermes, ed. Vangelis Paschos, pp. 21-50, 2007
  • Other publications

  • Etude et approximation de problèmes d'optimisation combinatoire
    Habilitation à Diriger des Recherches, Université Paris Dauphine, 2003
  • Approximation de problèmes d'optimisation et de fonctions totales de NP
    Thèse de doctorat, Université Paris Sud, 1998
  • Schémas d'approximation et complexité paramétrée
    Mémoire de DEA, Université Paris Sud, 1995