Publications

International journals

1. 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
   
2. 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
   
3. 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
   
4. Satisfactory graph partition, variants, and generalizations
   C. Bazgan, Zs. Tuza et D. Vanderpooten
   
   European Journal of Operation Research, 206(2), pp. 271-280, 2010
   
5. 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
   
6. 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
   
7. 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
   
8. Approximation of satisfactory bisection problems
   C. Bazgan, Zs. Tuza et D. Vanderpooten
   
   Journal of Computer and System Sciences, 74(5), pp. 875-883, 2008
   
9. 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
   
10. 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
    
11. Efficient algorithms for decomposing graphs under degree constraints
    C. Bazgan, Zs. Tuza et D. Vanderpooten
    
    Discrete Applied Mathematics, 155(8), pp. 979-988, 2007
    
12. 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
    
13. 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
    
14. The satisfactory partition problem
    C. Bazgan, Zs. Tuza and D. Vanderpooten
    
    Discrete Applied Mathematics, 154(8), pp. 1236-1245, 2006
    
15. 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
    
16. 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
    
17. 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
    
18. 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
    
19. Approximation algorithms for some vehicle routing problems
    C. Bazgan, J. Monnot and R. Hassin
    
    Discrete Applied Mathematics , 146(1), pp. 27-42, 2005
    
20. A note on the approximability of the toughness of graphs
    C. Bazgan
    
    Discrete Mathematics , 280(1-3), pp. 215-218, 2004
    
21. 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
    
22. Differential approximation for satisfiability and related problems
    C. Bazgan and V. Paschos
    
    European Journal of Operational Research , 147(2), pp. 397-404, 2003
    
23. 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
    
24. 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
    
25. 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
    
26. On the Loebl-Komlos-Sos conjecture
    C. Bazgan, H. Li and M. Wozniak
    
    Journal of Graph Theory, 34(4), pp. 269-276, 2000
    
27. 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
28. 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

1. 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), to appear
   
2. 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), to appear
   
3. 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), to appear
   
4. 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
   
5. 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
   
6. 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
   
7. 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
   
8. 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
   
9. 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
   
10. 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
    
11. 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
    
12. 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
    
13. 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
    
14. 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
    
15. 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
    
16. 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
    
17. 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
    
18. 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
    
19. 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
    
20. 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
    
21. 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
    
22. Differential approximation for satisfiability and related problem
    C. Bazgan and V. Paschos
    
    6th Balkan Conference on Operations Research 2002, 6 pages
    
23. 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
    
24. 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
    
25. 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
    
26. 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