Curriculum vitae

Bazgan Cristina

Professeur des universités
LAMSADE

cristina.bazganping@lamsade.dauphinepong.fr
Tel : 01 44 05 40 90
Bureau : P 409

Dernières publications

Articles

Bazgan C., Foucaud F., Sikora F. (2019), Parameterized and approximation complexity of Partial VC Dimension, Theoretical Computer Science, vol. 766, p. 1-15

Bazgan C., Brankovic L., Casel K., Fernau H., Jansen K., Klein K-M., Lampis M., Liedloff M., Monnot J., Paschos V. (2018), The many facets of upper domination, Theoretical Computer Science, vol. 717, p. 2-25

Bazgan C., Chlebikova J., Pontoizeau T. (2017), Structural and algorithmic properties of 2-community structures, Algorithmica

Bazgan C., Jamain F., Vanderpooten D. (2017), Discrete representation of the non-dominated set for multi-objective optimization problems using kernels, European Journal of Operational Research, vol. 260, n°3, p. 814-827

Bazgan C., Bredereck R., Hartung S., Nichterlein A., Woeginger G. (2016), Finding large degree-anonymous subgraphs is hard, Theoretical Computer Science, vol. 622, p. 90-110

Abu-Khzam F., Bazgan C., Chopin M., Fernau H. (2016), Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms, Journal of Computer and System Sciences, vol. 82, n°3, p. 503-520

Bazgan C., Bentz C., Picouleau C., Ries B. (2015), Blockers for the stability number and the chromatic number, Graphs and Combinatorics, vol. 31, n°1, p. 73-90

Bazgan C., Jamain F., Vanderpooten D. (2015), Approximate Pareto sets of minimal size for multi-objective optimization problems, Operations Research Letters, vol. 43, n°1, p. 1-6

Chopin M., Nichterlein A., Bazgan C., Sikora F. (2014), Parameterized approximability of maximizing the spread of influence in networks, Journal of Discrete Algorithms, vol. 27, p. 54-65

Angelelli E., Bazgan C., Speranza M., Tuza Z. (2014), Complexity and approximation for Traveling Salesman Problems with profits, Theoretical Computer Science, vol. 531, p. 54-65

Bazgan C., Chopin M. (2014), The Complexity of Finding Harmless Individuals in Social Networks, Discrete Optimization, vol. 14, p. 170-182

Bazgan C., Chopin M., Nichterlein A., Sikora F. (2014), Parameterized Inapproximability of Target Set Selection and Generalizations, Computability, vol. 3, n°2, p. 135-145

Bazgan C., Chopin M., Cygan M., Fellows M., Fomin F., van Leeuwen E. (2014), Parameterized Complexity of Firefighting, Journal of Computer and System Sciences, vol. 80, n°7, p. 1285-1297

Bazgan C., Toubaline S., Vanderpooten D. (2013), Critical edges for the assignment problem : complexity and exact resolution, Operations Research Letters, vol. 41, n°6, p. 685-689

Bazgan C., Chopin M., Ries B. (2013), The firefighter problem with more than one firefighter on trees, Discrete Applied Mathematics, vol. 161, n°7-8, p. 899-908

Bazgan C., Gourvès L., Monnot J. (2013), Approximation with a fixed number of solutions of some multiobjective maximization problems, Journal of Discrete Algorithms, vol. 22, p. 19-29

Bazgan C., Toubaline S., Vanderpooten D. (2013), Critical edges/nodes for the minimum spanning tree problem: complexity and approximation, Journal of Combinatorial Optimization, vol. 26, n°1, p. 178-189

Bazgan C., Jamain F., Vanderpooten D. (2013), On the number of non-dominated points of a multicriteria optimization problem, Discrete Applied Mathematics, vol. 161, n°18, p. 2841-2850

Bazgan C., Toubaline S., Vanderpooten D. (2013), Complexity of determining the most vital elements for the p-median and p-center location problems, Journal of Combinatorial Optimization, vol. 25, n°2, p. 191-207

Bazgan C., Gourvès L., Monnot J., Pascual F. (2013), Single approximation for biobjective Max TSP, Theoretical Computer Science, vol. 478, p. 41-50

Bazgan C., Toubaline S., Vanderpooten D. (2012), Efficient determination of the k most vital edges for the minimum spanning tree problem, Computers and Operations Research, vol. 39, n°11, p. 2888-2898

Bazgan C., Toubaline S., Tuza Z. (2011), The most vital nodes with respect to independent set and vertex cover, Discrete Applied Mathematics, vol. 159, n°17, p. 1933-1946

Bazgan C., Couëtoux B., Tuza Z. (2011), Complexity and approximation of the constrained forest problem, Theoretical Computer Science, vol. 412, n°32, p. 4081-4091

Aissi H., Bazgan C., Vanderpooten D. (2010), General approximation schemes for min–max (regret) versions of some (pseudo-)polynomial problems, Discrete Optimization, vol. 7, n°3, p. 136-148

Bazgan C., Tuza Z., Vanderpooten D. (2010), Satisfactory graph partition, variants, and generalizations, European Journal of Operational Research, vol. 206, n°2, p. 271-280

Bazgan C., Hugot H., Vanderpooten D. (2009), Solving efficiently the 0-1 multi-objective knapsack problem, Computers and Operations Research, vol. 36, n°1, p. 260-279

Bazgan C., Hugot H., Vanderpooten D. (2009), Implementing an efficient fptas for the 0–1 multi-objective knapsack problem, European Journal of Operational Research, vol. 198, n°1, p. 47-56

Aissi H., Bazgan C., Vanderpooten D. (2009), Min–max and min–max regret versions of combinatorial optimization problems: A survey, European Journal of Operational Research, vol. 197, n°2, p. 427-438

Bazgan C., Tuza Z., Vanderpooten D. (2008), Approximation of satisfactory bisection problems, Journal of Computer and System Sciences, vol. 74, n°5, p. 875-883

Aissi H., Bazgan C., Vanderpooten D. (2008), Complexity of the min-max (regret) versions of cut problems, Discrete Optimization, vol. 5, n°1, p. 66-73

Bazgan C., Tuza Z. (2008), Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3, Journal of Discrete Algorithms, vol. 6, n°3, p. 510-519

Aissi H., Bazgan C., Vanderpooten D. (2007), Approximation of min-max and min-max regret versions of some combinatorial optimization problems, European Journal of Operational Research, vol. 179, n°2, p. 281-290

Bazgan C., Tuza Z., Vanderpooten D. (2007), Efficient algorithms for decomposing graphs under degree constraints, Discrete Applied Mathematics, vol. 155, n°8, p. 979-988

Bazgan C., Tuza Z., Vanderpooten D. (2006), Degree-constrained decompositions of graphs: bounded treewidth and planarity, Theoretical Computer Science, vol. 355, n°3, p. 389-395

Bazgan C., Tuza Z., Vanderpooten D. (2006), The satisfactory partition problem, Discrete Applied Mathematics, vol. 154, n°8, p. 1236-1245

Bazgan C., Monnot J., Hassin R. (2005), Approximation algorithms for some vehicle routing problems, Discrete Applied Mathematics, vol. 146, n°1, p. 27-42

Aissi H., Bazgan C., Vanderpooten D. (2005), Complexity of the min-max and min-max regret assignment problems, Operations Research Letters, vol. 33, n°6, p. 634-640

Bazgan C., Escoffier B., Paschos V. (2005), Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness, Theoretical Computer Science, vol. 339, n°2-3, p. 272-292

Ausiello G., Bazgan C., Demange M., Paschos V. (2005), Completeness in differential approximation classes, International Journal of Foundations of Computer Science, vol. 16, n°6, p. 1267-1295

Bazgan C., Monnot J., Paschos V., Serrière F. (2005), On the differential approximation of MIN SET COVER, Theoretical Computer Science, vol. 332, n°1-3, p. 497-513

Bazgan C. (2004), A note on the approximability of the toughness of graphs, Discrete Mathematics, vol. 280, n°1-3, p. 215-218

Bazgan C., Fernandez de la Vega W., Karpinski M. (2003), Polynomial time approximation schemes for dense instances of minimum constraint satisfaction, Random Structures and Algorithms, vol. 23, n°1, p. 73-91

Bazgan C., Paschos V. (2003), Differential approximation for satisfiability and related problems, European Journal of Operational Research, vol. 147, n°2, p. 397-404

Chapitres d'ouvrage

Bazgan C. (2010), Optimal Satisfiability, in Paschos, Vangelis Th., Paradigms of Combinatorial Optimization: Problems and New Approaches Wiley, p. 704

Bazgan C. (2007), Complexité des problèmes de satisfaction de contraintes booléennes, in Paschos, Vangelis Th., Optimisation combinatoire 5 : problèmes paradigmatiques et nouvelles problematiques, Paris: Lavoisier, p. 21-50

Communications avec actes

Bazgan C., Herzel A., Ruzika S., Thielen C., Vanderpooten D. (2019), An FPTAS for a General Class of Parametric Optimization Problems, in Ding-Zhu Du, Zhenhua Duan, Cong Tian, 25th International Conference, COCOON 2019, Springer, 25-37 p.

Bazgan C., Pontoizeau T., Tuza Z. (2017), On the complexity of finding a potential community, in Fotakis Dimitris, Pagourtzis Aris, Paschos Vangelis Th., Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017), Springer, 80-91 p.

Abu-Khzam F., Bazgan C., Casel K., Fernau H. (2016), Building Clusters with Lower-Bounded Sizes, in Seok-Hee Hong, 27th International Symposium on Algorithms and Computation, ISAAC 2016, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 148:1–148:12 p.

Bazgan C., Brankovic L., Casel K., Fernau H. (2016), On the Complexity Landscape of the Domination Chain, in Sathish Govindarajan, Anil Maheshwari, Algorithms and Discrete Applied Mathematics - Second International Conference, CALDAM 2016, Berlin Heidelberg, Springer, 61-72 p.

Bazgan C., Foucaud F., Sikora F. (2016), On the Approximability of Partial VC Dimension, in T-H. Hubert Chan, Minming Li, Lusheng Wang, Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Berlin Heidelberg, Springer, 92-106 p.

Bazgan C., Brankovic L., Casel K., Fernau H., Jansen K., Klein K-M., Lampis M., Liedloff M., Monnot J., Paschos V. (2016), Upper Domination : Complexity and Approximation, in Veli Mäkinen, Simon J. Puglisi, Leena Salmela, Combinatorial Algorithms. 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings, Berlin Heidelberg, Springer, 241-252 p.

Bazgan C., Brankovic L., Casel K., Fernau H., Jansen K., Klein K-M., Lampis M., Liedloff M., Monnot J., Paschos V. (2016), Algorithmic Aspects of Upper Domination: A Parameterized Perspective, in Riccardo Dondi, Guillaume Fertin, Giancarlo Mauri, Algorithmic Aspects in Information and Management. 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings, Berlin Heidelberg, Springer, 113-124 p.

Bazgan C., Nichterlein A., Niedermeier R. (2015), A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths, in Vangelis Th. Paschos, Peter Widmayer, Algorithms and Complexity - 9th International Conference, CIAC 2015, Berlin Heidelberg, Springer, 47-60 p.

Bazgan C., Chlebikova J., Pontoizeau T. (2015), New Insight into 2-Community Structures in Graphs with Applications in Social Networks, in Zaixin Lu, Donghyun Kim, Weili Wu, Wei Li, Ding-Zhu Du, Combinatorial Optimization and Applications - 9th International Conference, COCOA 2015, Berlin Heidelberg, Springer, 236-250 p.

Abu-Khzam F., Bazgan C., El Haddad J., Sikora F. (2015), On the Complexity of QoS-Aware Service Selection Problem, in Alistair Barros, Daniela Grigori, Nanjangud C. Narendra, Hoa Khanh Dam, Service-Oriented Computing. 13th International Conference, ICSOC 2015, Goa, India, November 16-19, 2015, Proceedings, Springer, 345-352 p.

Bazgan C., Chopin M., Nichterlein A., Sikora F. (2014), Parameterized Inapproximability of Target Set Selection and Generalizations, in Arnold Beckmann, Erzsébet Csuhaj-Varjú, Klaus Meer, Language, Life, Limits.10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, June 23-27, 2014. Proceedings, Berlin Heidelberg, Springer, 11-20 p.

Bazgan C., Nichterlein A. (2014), Parameterized Inapproximability of Degree Anonymization, in Marek Cygan, Pinar Heggernes, Parameterized and Exact Computation - 9th International Symposium, IPEC 2014, Berlin Heidelberg, Springer, 75-84 p.

Abu-Khzam F., Bazgan C., Chopin M., Fernau H. (2014), Approximation Algorithms Inspired by Kernelization Methods, in Hee-Kap Ahn, Chan-Su Shin, Algorithms and Computation - 25th International Symposium, ISAAC 2014, Springer, 479-490 p.

Bazgan C., Chopin M., Nichterlein A., Sikora F. (2013), Parameterized Approximability of Maximizing the Spread of Influence in Networks, in Ding-Zhu Du, Guochuan Zhang, Computing and Combinatorics. 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. Proceedings, Berlin Heidelberg, Springer, 543-554 p.

Bazgan C., Gourvès L., Monnot J. (2012), Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems, in Solis-Oba, Roberto, WAOA 2011, Saarbrücken, Springer, 233-246 p.

Bazgan C., Gourvès L., Monnot J., Pascual F. (2012), Single Approximation for Biobjective Max TSP, in Solis-Oba, Roberto, WAOA 2011, Saarbrücken, Springer, 49-62 p.

Bazgan C., Chopin M. (2012), The Robust Set Problem: Parameterized Complexity and Approximation, in Widmayer, Peter, Mathematical Foundations of Computer Science 2012 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012, Proceedings, Bratislava, Springer, 136-147 p.

Bazgan C., Chopin M., Fellows M. (2011), Parameterized Complexity of the Firefighter Problem, in Watanabe, Osamu, ISAAC 2011, Yokohama, Springer, 643-652 p.

Bazgan C., Toubaline S., Vanderpooten D. (2011), Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem, in Zhu, Xuding, Combinatorial Optimization and Applications 5th International Conference, COCOA 2011, Zhangjiajie, Springer, 126-140 p.

Bazgan C., Toubaline S., Tuza Z. (2011), Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures, in Smyth, William F., Combinatorial Algorithms 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers, Londres, Springer, 154-166 p.

Bazgan C., Couëtoux B., Tuza Z. (2009), Covering a Graph with a Constrained Forest, in Yingfei Dong, Ding-Zhu Du, Oscar Ibarra, Algorithms and Computation 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, Honolulu, Springer, 892-901 p.

Bazgan C., Hugot H., Vanderpooten D. (2007), A practical efficient fptas for the 0-1 multi-objective knapsack problem, in Welzl, Emo, Algorithms - ESA 2007 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings, Eilat, Springer, 717-728 p.

Bazgan C., Hugot H., Vanderpooten D. (2007), An efficient implementation for the 0-1 multi-objective knapsack problem, in Demetrescu, Camil, Experimental Algorithms 6th International Workshop, WEA 2007, Rome, Italy, June 6-8, 2007, Proceedings, Rome, Springer, 406-419 p.

Aissi H., Bazgan C., Vanderpooten D. (2006), Approximating min-max (regret) versions of some polynomial problems, in Lee, D.T., Computing and Combinatorics 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings, Taipei, Springer, 428-438 p.

Aissi H., Bazgan C., Vanderpooten D. (2005), Complexity of the min-max (regret) versions of cut problems, in Du, Ding-Zhu, Algorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings, Sanya (Hainan), Springer, 789-798 p.

Bazgan C., Tuza Z., Vanderpooten D. (2005), Complexity and approximation of satisfactory partition problems, in Wang, Lusheng, Computing and Combinatorics 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-19, 2005, Proceedings, Kunming, Springer, 829-838 p.

Bazgan C., Monnot J., Paschos V., Serrière F. (2005), Greedy differential approximations for MIN SET COVER, in Vojtas, Peter, SOFSEM'05 : Theory and Practice of Computer Science, Liptovský Ján, Springer, 62-71 p.

Aissi H., Bazgan C., Vanderpooten D. (2005), Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack, in Leonardi, Stefano, Algorithms – ESA 2005 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings, Palma de Mallorca, Springer, 862-873 p.

Aissi H., Bazgan C., Vanderpooten D. (2005), Pseudo-polynomial algorithms for min-max and min-max regret problems, in Xian-Sun, Zhang, Operations Research and Its Applications. The Fifth International Symposium, ISORA’05 Tibet, China, August 8–13, 2005 Proceedings, Lhassa, World Publishing Corporation, 171-178 p.

Bazgan C., Escoffier B., Paschos V. (2004), Poly-APX- and PTAS-completeness in standard and differential approximation, in Trippen, Gerhard, ISAAC'04 :15th International Symposium, Hong Kong, Springer, 124-136 p.

Bazgan C., Tuza Z., Vanderpooten D. (2003), On the existence and determination of satisfactory partitions in a graph, in Ono, Hirotaka, Algorithms and Computation 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings, Kyoto, Springer, 444-453 p.

Bazgan C., Hassin R., Monnot J. (2003), Differential approximation for some routing problems, in Silvestri, Riccardo, Algorithms and Complexity 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003, Proceedings, Rome, Springer, 277-288 p.

Ausiello G., Bazgan C., Demange M., Paschos V. (2003), Completeness in differential approximation classes, in Vojtas, Peter, Mathematical Foundations of Computer Science 2003 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings, Bratislava, Springer, 179-188 p.

Bazgan C., Fernandez de la Vega W., Karpinski M. (2002), Approximability of Dense Instances of NEAREST CODEWORD Problem, in Martti Penttonen, Erik Meineche Schmidt, Algorithm Theory — SWAT 2002 8th Scandinavian Workshop on Algorithm Theory Turku, Finland, July 3–5, 2002 Proceedings, Berlin Heidelberg, Springer, 298-307 p.

Communications sans actes

Jamain F., Bazgan C., Vanderpooten D. (2014), Approximation in multiobjective optimization using e-kernels, 15ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF'14), Bordeaux, France

Jamain F., Bazgan C., Vanderpooten D. (2013), On Approximate Kernels of Minimal Size for Bicriteria Problems, 22nd International Conference on Multiple Criteria Decision Making (MCDM’13), 2013, Malaga, Espagne

Jamain F., Bazgan C., Vanderpooten D. (2013), Approximation de taille minimale de l'ensemble de Pareto de problèmes multicritères, 14ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF'13), Troyes, France

Jamain F., Bazgan C., Vanderpooten D. (2012), Sur le nombre de points non dominés d'un problème multicritères, 13ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF'12), Angers, France

Bazgan C., Escoffier B., Gourvès L., Monnot J., Pascual F., Vanderpooten D. (2012), Solutions équitables approchées pour divers problèmes d’optimisation combinatoire, 13ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF'12), Angers, France

Prépublications / Cahiers de recherche

Bazgan C., Tuza Z., Vanderpooten D. (2003), Complexity of the satisfactory partition problem, Note de recherche du LAMSADE, 13 p.

Bazgan C., Tuza Z., Vanderpooten D. (2003), Decomposition of graphs: some polynomial cases, Note de recherche du LAMSADE, 11 p.

Retour à la liste