2013

Articles

• Bazgan, Cristina ; Toubaline, Sonia ; Vanderpooten, Daniel . Complexity of determining the most vital elements for the p-median and p-center location problems. Journal of Combinatorial Optimization. Volume 25. n° 2. 2013. pages 191-207. Springer. DOI http://dx.doi.org/10.1007/s10878-012-9469-8.
• Bazgan, Cristina ; Toubaline, Sonia ; Vanderpooten, Daniel . Critical edges/nodes for the minimum spanning tree problem: complexity and approximation. Journal of Combinatorial Optimization. Volume 26. n° 1. 2013. pages 178-189. Springer. DOI http://dx.doi.org/10.1007/s10878-011-9449-4.

2012

Communications / Conférences

• Pascual, Fanny ; Monnot, Jérôme ; Gourvès, Laurent ; Bazgan, Cristina . Single Approximation for Biobjective Max TSP. WAOA 2011. Saarbrücken. Allemagne. 2011.
• Monnot, Jérôme ; Gourvès, Laurent ; Bazgan, Cristina . Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems. WAOA 2011. Saarbrücken. Allemagne. 2011.

2011

Articles

• Tuza, Zsolt ; Couëtoux, Basile ; Bazgan, Cristina . Complexity and approximation of the constrained forest problem. Theoretical Computer Science. Volume 412. n° 32. 2011. pages 4081-4091. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2010.07.018.
• Tuza, Zsolt ; Toubaline, Sonia ; Bazgan, Cristina . The most vitalnodes with respect to independentset and vertexcover. Discrete Applied Mathematics. Volume 159. n° 17. 2011. pages 1933-1946. Elsevier. DOI http://dx.doi.org/10.1016/j.dam.2011.06.023.

Communications / Conférences

• Bazgan, Cristina ; Toubaline, Sonia ; Tuza, Zsolt . Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures. 21st International Workshop on Combinatorial Algorithms (IWOCA 2010). Berlin. Royaume-Uni. 2010.
• Vanderpooten, Daniel ; Toubaline, Sonia ; Bazgan, Cristina . Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem. COCOA 2011. Zhangjiajie. Chine. 2011.
• Fellows, Michael R. ; Chopin, Morgan ; Bazgan, Cristina . Parameterized Complexity of the Firefighter Problem. ISAAC 2011. Yokohama. Japon. 2011.

2010

Articles

• Vanderpooten, Daniel ; Bazgan, Cristina ; Aissi, Hassene . General approximation schemes for min–max (regret) versions of some (pseudo-)polynomial problems. Discrete Optimization. Volume 7. n° 3. 2010. pages 136-148. Elsevier. DOI http://dx.doi.org/10.1016/j.disopt.2010.03.004.
• Bazgan, Cristina ; Tuza, Zsolt ; Vanderpooten, Daniel . Satisfactory graph partition, variants, and generalizations. European Journal of Operational Research. Volume 206. n° 2. 2010. pages 271-280. Elsevier. DOI http://dx.doi.org/10.1016/j.ejor.2009.10.019.

Chapitres d'ouvrage

• Bazgan, Cristina . Optimal Satisfiability. Paschos, Vangelis Th.. Paradigms of Combinatorial Optimization: Problems and New Approaches. . 2010. pages 3-31.

Communications / Conférences

• Vanderpooten, Daniel ; Toubaline, Sonia ; Bazgan, Cristina . Complexity of determining the most vital elements for the 1-median and 1-center location problems. Combinatorial Optimization and Combinatorial Optimization and Applications 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part I. Kailua-Kona. États-Unis. 2010.

2009

Articles

• Bazgan, Cristina ; Hugot, Hadrien ; Vanderpooten, Daniel . Implementing an efficient fptas for the 0–1 multi-objective knapsack problem. European Journal of Operational Research. Volume 198. n° 1. 2009. pages 47-56. Elsevier. DOI http://dx.doi.org/10.1016/j.ejor.2008.07.047.
• Aissi, Hassene ; Bazgan, Cristina ; Vanderpooten, Daniel . Min–max and min–max regret versions of combinatorial optimization problems: A survey. European Journal of Operational Research. Volume 197. n° 2. 2009. pages 427-438. Elsevier. DOI http://dx.doi.org/10.1016/j.ejor.2008.09.012.
• Vanderpooten, Daniel ; Hugot, Hadrien ; Bazgan, Cristina . Solving efficiently the 0-1 multi-objective knapsack problem. Computers and Operations Research. Volume 36. n° 1. 2009. pages 260-279. Elsevier. DOI http://dx.doi.org/10.1016/j.cor.2007.09.009.

Communications / Conférences

• Bazgan, Cristina ; Couëtoux, Basile ; Tuza, Zsolt . Covering a Graph with a Constrained Forest. Algorithms and Computation 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings. Honolulu. États-Unis. 2009.

2008

Articles

• Tuza, Zsolt ; Bazgan, Cristina . Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3. Journal of Discrete Algorithms. Volume 6. n° 3. 2008. pages 510-519. Elsevier. DOI http://dx.doi.org/10.1016/j.jda.2007.02.002.
• Vanderpooten, Daniel ; Bazgan, Cristina ; Aissi, Hassene . Complexity of the min-max (regret) versions of cut problems. Discrete Optimization. Volume 5. n° 1. 2008. pages 66-73. Elsevier Ltd. DOI http://dx.doi.org/10.1016/j.disopt.2007.11.008.
• Bazgan, Cristina ; Tuza, Zsolt ; Vanderpooten, Daniel . Approximation of satisfactory bisection problems. Journal of Computer and System Science. Volume 74. n° 5. 2008. pages 875-883. Elsevier. DOI http://dx.doi.org/10.1016/j.jcss.2007.12.001.

2007

Articles

• Aissi, Hassene ; Bazgan, Cristina ; Vanderpooten, Daniel . Approximation of min-max and min-max regret versions of some combinatorial optimization problems. European Journal of Operational Research. Volume 179. n° 2. 2007. pages 281-290. Elsevier. DOI http://dx.doi.org/10.1016/j.ejor.2006.03.023.
• Bazgan, Cristina ; Tuza, Zsolt ; Vanderpooten, Daniel . Efficient algorithms for decomposing graphs under degree constraints. Discrete Applied Mathematics. Volume 155. n° 8. 2007. pages 979-988. Elsevier. DOI http://dx.doi.org/10.1016/j.dam.2006.10.005.

Chapitres d'ouvrage

• Bazgan, Cristina . Complexité des problèmes de satisfaction de contraintes booléennes. Paschos, Vangelis Th.. Optimisation combinatoire 5 : problèmes paradigmatiques et nouvelles problematiques. Paris. 2007. pages 21-50.

Communications / Conférences

• Bazgan, Cristina ; Hugot, Hadrien ; Vanderpooten, Daniel . A practical efficient fptas for the 0-1 multi-objective knapsack problem. 15th Annual European Symposium on Algorithms (ESA 2007). Berlin. Israël. 2007.
• Bazgan, Cristina ; Hugot, Hadrien ; Vanderpooten, Daniel . An efficient implementation for the 0-1 multi-objective knapsack problem. 6th Workshop on Experimental Algorithms (WEA'07). Berlin. Italie. 2007.

2006

Articles

• Bazgan, Cristina ; Tuza, Zsolt ; Vanderpooten, Daniel . Degree-constrained decompositions of graphs: bounded treewidth and planarity. Theoretical Computer Science. Volume 355. n° 3. 2006. pages 389-395. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2006.01.024.
• Bazgan, Cristina ; Tuza, Zsolt ; Vanderpooten, Daniel . The satisfactory partition problem. Discrete Applied Mathematics. Volume 154. n° 8. 2006. pages 1236-1245. Elsevier. DOI http://dx.doi.org/10.1016/j.dam.2005.10.014.

Communications / Conférences

• Aissi, Hassene ; Bazgan, Cristina ; Vanderpooten, Daniel . Approximating min-max (regret) versions of some polynomial problems. 12th Annual International Conference on Computing and Combinatorics (COCOON 2006). Taipei. Taïwan. 2006.

2005

Articles

• Demange, Marc ; Bazgan, Cristina ; Ausiello, Giorgio ; Paschos, Vangelis . Completeness in differential approximation classes. International Journal of Foundations of Computer Science. Volume 16. n° 6. 2005. pages 1267-1295. World Scientific Publishing Company.
• Monnot, Jérôme ; Hassin, Refael ; Bazgan, Cristina . Approximation algorithms for some vehicle routing problems. Discrete Applied Mathematics. Volume 146. n° 1. 2005. pages 27-42. Elsevier. DOI http://dx.doi.org/10.1016/j.dam.2004.07.003.
• Bazgan, Cristina ; Escoffier, Bruno ; Paschos, Vangelis . Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness. Theoretical Computer Science. Volume 339. n° 2-3. 2005. pages 272-292. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2005.03.007.
• Bazgan, Cristina ; Monnot, Jérôme ; Paschos, Vangelis ; Serrière, Fabrice . On the differential approximation of MIN SET COVER. Theoretical Computer Science. Volume 332. n° 1-3. 2005. pages 497-513. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2004.12.022.
• Aissi, Hassene ; Bazgan, Cristina ; Vanderpooten, Daniel . Complexity of the min-max and min-max regret assignment problems. Operations Research Letters. Volume 33. n° 6. 2005. pages 634-640. Elsevier. DOI http://dx.doi.org/10.1016/j.orl.2004.12.002.

Communications / Conférences

• Bazgan, Cristina ; Tuza, Zsolt ; Vanderpooten, Daniel . Complexity and approximation of satisfactory partition problems. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005). Kunming. Chine. 2005.
• Aissi, Hassene ; Bazgan, Cristina ; Vanderpooten, Daniel . Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack. 13th Annual European Symposium on Algorithms (ESA 2005). Berlin. Espagne. 2005.
• Bazgan, Cristina ; Karpinski, Marek . On the Complexity of Global Constraint Satisfaction. Algorithms and Computation Algorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings. Sanya. Chine. 2005.
• Bazgan, Cristina ; Monnot, Jérôme ; Paschos, Vangelis ; Serrière, Fabrice . Greedy differential approximations for MIN SET COVER. SOFSEM 2005: Theory and Practice of Computer Science 31st Conference on Current Trends in Theory and Practice of Computer Science, Liptovský Ján, Slovakia, January 22-28, 2005, Proceedings. Berlin. Slovaquie. 2005.
• Aissi, Hassene ; Bazgan, Cristina ; Vanderpooten, Daniel . Pseudo-polynomial algorithms for min-max and min-max regret problems. Operations Research and Its Applications. The Fifth International Symposium, ISORA’05 Tibet, China, August 8–13, 2005 Proceedings. Beijing. Chine. 2005.
• Aissi, Hassene ; Bazgan, Cristina ; Vanderpooten, Daniel . Complexity of the min-max (regret) versions of cut problems. 16th International Symposium on Algorithms and Computation (ISAAC 2005). Sanya (Hainan). Chine. 2005.

2004

Articles

• Bazgan, Cristina . A note on the approximability of the toughness of graphs. Discrete Mathematics. Volume 280. n° 1-3. 2004. pages 215-218. Elsevier. DOI http://dx.doi.org/10.1016/j.disc.2003.10.013.

Communications / Conférences

• Bazgan, Cristina ; Escoffier, Bruno ; Paschos, Vangelis . Poly-APX- and PTAS-completeness in standard and differential approximation. ISAAC'04 :15th International Symposium. Hong Kong. Chine. 2004.

2003

Articles

• Bazgan, Cristina ; Paschos, Vangelis . Differential approximation for satisfiability and related problems. European Journal of Operational Research. Volume 147. n° 2. 2003. pages 397-404. Elsevier. DOI http://dx.doi.org/10.1016/S0377-2217(02)00299-0.

Communications / Conférences

• Ausiello, Giorgio ; Bazgan, Cristina ; Demange, Marc ; Paschos, Vangelis . Completeness in differential approximation classes. 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'03). Berlin. Slovaquie. 2003.
• Bazgan, Cristina ; Tuza, Zsolt ; Vanderpooten, Daniel . On the existence and determination of satisfactory partitions in a graph. 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003). Kyoto. Japon. 2003.
• Bazgan, Cristina ; Hassin, Refael ; Monnot, Jérôme . Differential approximation for some routing problems. 5th Italian Conference on Algorithms and Complexity (CIAC'03). Rome. Italie. 2003.

Documents de travail

• Bazgan, Cristina ; Tuza, Zsolt ; Vanderpooten, Daniel . Decomposition of graphs: some polynomial cases. . 2003 .
• Bazgan, Cristina ; Tuza, Zsolt ; Vanderpooten, Daniel . Complexity of the satisfactory partition problem. . 2003 .